javascript - 游戏的图 block 填充算法

Question

背景:

我正在使用 Javascript 开发一款基于图 block 的游戏，其中 Angular 色在 map 上自由移动(无对 Angular 线 - 左/右/上/下)并在他围绕 map 移动时填充图 block map 。共有三种拼贴类型——您已填充的拼贴(蓝色)、您当前的路径(红色)和空的拼贴(黑色)。也有敌人(星星)在 map 上移动，但仅限于空白区域。目标是尽可能多地填充 map 。

map 的大小约为 40x40 个图 block 。 map 的整个外部周围有一个 1 格厚的边框，该边框已经“填充”(蓝色)。

我已经确定，泛洪填充算法将在需要时用于填充图 block 区域。但是，我的问题如下:

问题陈述: 如果 map 上没有敌人，我只想填充 map 的一部分。

我的问题: 我可以运行 flood-fill 算法，并在它到达敌人占据的地 block 时停止它——但是，这是最有效的方法(对于实时游戏)吗？
如果是，我如何以系统的方式确定从哪里开始算法，因为有多个区域需要检查，而且 Angular 色不必沿着完美的直线移动(可以锯齿形移动上/下/右/左，但不能沿对 Angular 线移动)。

图片示例1(图片解释更好):

注意:到达另一个填充区域后，红色区域会变成蓝色(填充)。在下面的示例中，包含区域中没有敌人，因此该区域被填充。

图片示例2:

在第二个示例中，包含区域内(以及外部区域 - 未显示)内有一个敌人，因此只填充了直线。

总结:进行这种填充的最佳方法是什么？洪水填充是否是确定是否填充的最佳选择 - 40x40 进行了相当大的计算。如果是，我如何确定从哪个磁贴开始？

Answer 1

让我建议用不同的方式来看待您的问题。

根据您的游戏描述，似乎用户的主要(也许只是)“动词”(在游戏设计术语中)是画一条线，将 field 的开放区域分成两部分。如果这两个部分中的任何一个没有敌人，该部分就会被填满；如果两个部分都没有敌人，则该线仍然存在，但两个部分都保持开放状态。没有其他条件决定一个部分是否被填充，对吧？

所以我认为，解决这个问题最有效的方法就是画一条连续的线，它可能会转 Angular ，但只会在水平或垂直方向上移动，依次从你的一个敌人到所有其他敌人。我们将这条线称为“探测线”。从这里开始，我们使用 Derek 建议的“光线转换算法”的方法:我们查看“探测线”穿过“边界线”的次数，如果交叉次数为奇数，则意味着线的每一侧至少有一个敌人，而且没有填充物。

但请注意，两条线重合 和两条线相交 是有区别的。想象一条从坐标 (0,10) 到 (39,10) 的探测线，以及一条从 (5,0) 向下的边界线) 到 (5,10) 然后直接到 (13,10)。如果它从那里向下走向 (13,39)，则两条线相交；相反，如果它向上朝向 (13,0)，则它们不是。

经过深思熟虑，我强烈建议您存储“边界线”，并根据线段构建“探测线”——而不是试图确定从哪些单元格开始填充了创建它们的线段。这将使它变得比它必须的更难。

最后，要注意一个奇怪的游戏设计注意事项:除非您限制用户的控制，使他无法将边界线带回其自身的一个单元格内，否则绘制一条单一的边界线用户最终可能会将字段分成两个以上部分 - 边界线可能会在其自身上循环创建部分。如果你允许这样做，它可能会使填充位置的计算变得非常复杂。查看我通过 Derek 的 fiddle 制作的下图(谢谢你，Derek!):

如您所见，一条边界线实际上创建了三段:一段在线上侧，一段在线下，一段由线本身形成。我仍在考虑这将如何影响算法，以使其成为可能。

编辑: 有了 a) 时间来思考上面的循环创建多个部分，和 b) Derek 提出的简单性模拟资源，我想我可以概述您可能获得的最简单和最有效的算法。

我将留给您一个子问题，那就是在玩家的 Action 画出一条新线后确定您的新部分是什么。我把它留给你，因为它是在调用原始问题的解决方案(如何判断这些部分中是否有敌人)之前必须解决的问题。

此处以伪代码形式呈现的解决方案假设您将每个部分的边界存储为坐标之间的线段。

Create a list of the sections.
Create a list of the enemies.
Continue as long as neither list is empty:
  For each enemy in the enemy list:
  Designate "Point A" as the coordinates of the enemy, PLUS 0.5 to both x and y.
    For each section in the section list:
      Designate "Point B" as the upper-left-most coordinate, PLUS 0.5 to both x and y.
      Count how many of the section border segments cross a line between A and B.
      If the answer is even:  
        remove this section from the section list
        skip forward to the next enemy
If any sections remain in the list, they are free of enemies.  Fill them in.

将 0.5 添加到“探测线”的坐标要感谢 Derek 的 SoS 资源；它们消除了线条重合的困难情况，而不是简单地交叉或不交叉。