javascript - 实时多人游戏-区域广播

Question

我正在编写一个实时多人游戏(使用 Nodejs、socket.io)，希望请您帮助优化一个点。

我实现了一个权威服务器，其更新循环60次/秒和广播循环20次/秒、客户端预测和插值。 然后，在广播循环中，我尝试了导致性能问题的区域广播。

为了简约，服务器具有以下数组:

• 玩家实体(ID + 位置)
• 食品实体(id + 位置)

让我们在一个大 map (就像agar.io)中生成 1000 种食物，位于服务器的server.foods数组中。玩家只需要知道其视口(viewport)中食物的状态(假设200 个可见食物)。因此，服务器仅向玩家发送包含 200 个可见食物(id + 位置)的一个数据包。然后，为了让服务器知道，我们将 200 个可见食物推送到 Player 对象的数组中 (player.foods)

但是玩家可以移动，所以必须发送其他数据包:

• initFoods 是要初始化的食物数组(id+位置)(仅当新食物对玩家可见时:distFoodPlayer < 500)

• removeFoods 是要删除的食物数组(id+位置)(仅当新食物对玩家不可见时:distFoodPlayer > 600)

要了解这些信息，我会这样做:

for (var i = server.foods.length; i--;) {
    //Edit: added the next line
    if (distPlayerFood < 900) {
        var food = server.foods.entities[i];
        var inPlayerFoods = false;
        for (var j = player.foods.length; j--;) {
            if (food.id === player.foods[j]) {
                inPlayerFoods = true;
                if (distPlayerFood > 600) {
                    removeFoods.push(food.id);
                    player.foods.splice(i, 1);
                }
            }
        }
        if (distPlayerFood < 500) {
            if (!inPlayerFoods) {
                player.foods.push(food.id);
                initFoods.push([food.id, food.state]);
            }
        }
    }
});

对于 1000 种食物和 1 名玩家，性能还可以(服务器更新循环保持约 58FPS)。但对于 5000 种食物和 1 名玩家(或 1000 种食物和 5 名玩家)来说，由于这种双循环(服务器最大速度约为 25-40FPS)，性能非常糟糕，但带宽却被最小化。 性能测试是在我的计算机(本地主机)上完成的。也许使用更大的服务器，我不会遇到这些问题？

你认为我的做法好吗？你有更好的主意吗？

非常感谢。

编辑:我更改了代码以仅检查不太远的食物。服务器最高可达约 35-50FPS

Answer 1

你的算法的复杂度是 O(n!)，这就是为什么它会因为大量的食物而变慢。除非你的目标是让玩家在一个大世界中移动，否则你的方法看起来不错。对我有用的优化实现的一种方法是将您的世界划分为图 block ，每个图 block 都包含对其内部食物的引用。然后，您可以快速获取可能在范围内的食物列表，这样您就无需检查玩家与距离太远的食物之间的距离。