有效地找到2D网格中最大的周围方形

Question

在具有2D网格地图的游戏中,我面临以下情况:

我需要找到围绕玩家位置(红点)的最大边界方块.或者至少是最大尺寸的边界,因为可能会有更多.注意:方形,而不是矩形.

在这种情况下,很容易看到最大的正方形是8x8:

如果我在地图中添加障碍物,最大的可能性现在是5x5:

我正在寻找一种快速有效的方法来找到包含玩家位置的(或者)最大正方形.

我目前正在做的是一种蛮力:

• 始终可以使用1x1的方格(玩家位置本身).
• 然后我尝试所有可能的2*2方格包含播放器,这是4个可能的不同方块,并为每个我做2*2循环,检查所有网格单元是否清晰(不是墙壁或障碍物).
• 如果可能是2*2的方格,那么我会尝试围绕玩家的所有可能的3*3方格(这是9个不同的方格),并为每个我做3*3循环,以检查是否没有碰撞.
• 等等,直到尺寸为N*N,没有正方形是可能的.

它的工作原理很简单,但感觉非常低效.显然我在这里做了很多冗余检查,我想知道是否有更聪明/更快的方法来做到这一点.有谁知道有效地做到这一点的算法？

(编辑)重要补充:除了玩家四处移动外,还会动态添加或移动障碍物或墙壁,因此这里的缓存或预先优化很难实现.

Answer 1

我认为你可以通过在每个阶段检查现有"最大方块"的有效边界来改进算法.这可能更容易以图解方式解释......但基本上.你应该做的就是

 **Growth Algorithm**
 repeat
   search the bounding sub-squares on the valid sides of the largest valid square found so far
   increase size of square on 'valid' sides and mark newly blocked sides as invalid
 until all sides invalid

 then check if largest valid square can be translated 1 unit diagonally in any of 4 directions
 if so repeat the growth algorithm on each new square until none get bigger

通过这种方式,您只需要测试一次最终有效方块的每个子方块.因此,如果square为n,则为^ 2进程.IO不要认为你可以做得更好,因为你需要检查每个子广场的有效性.