扫描二维瓷砖地图和检测区域?

我可以访问地图上的所有点/瓦片,最右上角的点是(0,0)。 最简单的遍历地图的方法是使用for循环,一个嵌套在另一个中以遍历x轴,然后是y(遍历行)。 但要解决这个问题,我可能需要以更智能的方式扫描地图。 重要的是要注意的是,我只能一次检查一个图块,看看它是什么types。 所以t.getCoordinates()会返回类似于(32,54)的内容,而t.senseTile()会返回:WALL,ROAD,OFF_MAP等

我想扫描整个地图,并将其划分为多个地区。 这些地区将有两种:“开放”和“path”。 对于开放区域,我只想填充整个区域,直到它开始触及边界,墙壁/障碍物等,并在适当的时候停止填充。 一个开放空间的规则是玩家应该能够从一个边缘到另一个边缘采取任何path,角度等,而不会碰到一些墙壁/障碍物。

对于path,有一定数量的区域是有限的瓦片,然后一个新的区域开始(见lightBlue和灰色)。

此外,path应该有入口/存在也存储,并连接到哪些地区。 例如,像这样扫描地图(见图),应该生成这些区域。 不知道使用哪个数据结构来连接它们,但是可能是一个树形/graphics如下所示:

Gray | LightBlue | Pink | Yellow | \ Red Black 

在这里输入图像说明

编辑:我认为Dijkstra的searchalgorithm可能是一个很好的起点,虽然我从来没有实现过。 这只能解决问题的一小部分。 它仍然不能解决如何检测区域。 另外,恐怕迪杰斯特拉在时间/performance方面的成本太高(两者都非常重要)。

对于path的自动检测是否适用于任何地图,我有点怀疑。 我提出了一个启发式的方法来寻找path,但是它会把你的黄色区域细分成不同的区域。

水平path是一条与其南北面相连的陆地。 西面和东面都有水。 这些水砖最多可以与北面和南面的其他水面砖相接。 桥不应超过最大长度。 同样适用于垂直path。

扫描您的地图的path,并将瓷砖设置为pathID。 (他们不再被认为是“土地”。)然后再次扫描地图,并用区域id填充每个开放地块的瓦片。 这会给你这样的东西,path被标记为红色:

地图与路径(微红)和地区(蓝/绿)

然后,您可以派生一个graphics与regios作为顶点和path作为边缘。

你会注意到寻找path的启发式不是很复杂。 应该有一条path将L形水面附近西部的苍白的扬声区域细分。 中央广场周围不应有path。

我认为很难find一个可以解释这种情况的令人满意的algorithm。 也许你可以有一个积极的pathalgorithm创建太多的path,然后find一种方法来join区域根据另一种启发式,但我怀疑它。

我认为最好是手工定义path,然后find区域。 或者,您必须标记可能的path位置的原始地图。