查找 Paper.io 游戏的内部部分算法

Question

看看这款游戏：http://paper-io.com/

我坚持在从这个游戏移动后找到内部零件的算法。

看看我的照片。玩家的原始土地是红色的。球员运动是橙色的。新的土地是绿色的。

我的问题是如何指定绿色部分。我想在完成移动后，这里可能有两个部分可以选择为绿色（绿色部分和外部网格部分）。

选一个开始然后找墙才知道哪个部分是结果浪费时间。

感谢阅读。

Answer 1

从外边缘上非红色或橙色的每个点开始进行颜色填充。

停在红色或橙色方块处。

这会给你不会填写的区域，所以只需填写剩下的部分。

经过多次 100%ed paper.io，我可以验证这与它所做的是等价的。

您也可以从新墙的两侧同时进行洪水填充。如果一个填充找到外边缘，则丢弃那个并保留另一个。如果一个在找到外边缘之前停止，则保留那个并丢弃另一个。

Answer 2

比方说，您要求的是栅格算法，但让我们尝试概括这个问题。

假设我们总是记住占用（红色）区域的电路并将其存储在一个看起来像循环链表的图形中。每个节点都有坐标(x, y)。所以我们有这样的东西：

  A2 -- A3 -- A4
 /             \
A1             A5
 \             /
  A7 -------- A6

同时我们记住起始区内的一个点。

这个游戏的每一轮都从电路的某个地方开始，要么在现有节点上，要么在现有节点之间的新节点上，并在检测到运动矢量和电路的交点时结束。这些节点是 P 和 R。本轮绘制的整条路线创建了电路的新部分。运动矢量是 "head" 在每个时间滴答中迈出的一步。

起始节点 P 将边 A3 - A4 分成两条边 A3 - P 和 P - A4 并添加到图中。边 A3 - A4 已从图中删除。

移动的每一步都会添加下一条边：P - B1、B1 - B2、...最后我们将边 A6 - A7 与 A6 - R 和 R - A7 交换.

每一轮之后的图形如下：

                B1 -- B2 -- B3
               /             \
  A2 -- A3 -- P -- A4         B4
 /                  \         |
A1                  A5        |
 \                  /         B5
  A7 ------ R --- A6         /
             \              /
              B7 --------- B6

现在是遍历图形并将访问节点收集到新电路中的时候了。此步行在一系列多边形联合算法或 here（步骤 3 和 4）中进行了描述。

当我们有一个新的电路时，我们可以绘制它并从记住的点开始填充。

查找 Paper.io 游戏的内部部分算法

Find inside part algorithm for Paper.io game

algorithm

greedy