相关疑难解决方法(0)

什么是最有效的算法找到适合空白区域的最大面积的矩形？

假设屏幕看起来像这样('#'代表填充区域):

....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............

一个可能的解决方案是:

....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...

通常我会喜欢找出解决方案.虽然这次我想避免浪费时间自己摸索,因为这对我正在研究的项目有实际用途.有一个众所周知的解决方案吗？

Shog9写道:

您的输入是一个数组(如其他响应所暗示的那样),还是一个以任意大小的定位矩形形式的遮挡列表(在处理窗口位置时窗口系统中可能就是这种情况)？

是的,我有一个跟踪屏幕上放置的一组窗口的结构.我还有一个网格,可以跟踪每条边之间的所有区域,无论它们是空的还是填充的,以及它们左边或顶边的像素位置.我认为有一些修改后的形式可以利用这个属性.你知道吗？

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

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

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

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

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

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

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

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

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