2

我正在尝试为我玩的游戏开发在线地图编辑程序。
地图的数据有点大。如果我为每个正方形发送数据，则中等大小的地图数据接近 1 mb。

我认为我能做的是在地图上找到边界并以此为基础创建多边形。

目前我：

  1. 找到最西北的边界并从那里开始。对于我的示例地图，它是 (3,2)
  2. 然后，检查北、东、南，然后是西，然后转到第一个没有 1 作为数据的未访问位置。
  3. 如果没有未访问的位置，请转到历史上最远的位置。

示例地图
采取的步骤

这适用于北部地区。但是，当我到达南部地区时，它会向北检查并发现这是一个未访问的位置并前往那里。它搞砸的地方的坐标是 13,11。

显然，这并没有给我想要的边界，也没有走遍整个地图。所以，有些事情需要改变。

我考虑以与以前相同的操作顺序添加边界检查（NESW）。但是，也有可能把它搞砸。

Map2 - 边界检查

在 (13,11) 处，它会向北检查，发现它是一个未访问的位置。而这一次，那里有一个边界，所以它会认为可以去那里。

我应该怎么做才能走完整个外边界？

我确实看过这里提到的凸包算法，但我认为这不是我需要的。我可能不正确，但这是我期望的凸包结果。
凸包 虽然这确实减少了一点地图的大小，但仍有很多我不需要的数据。当我需要获取地图中项目的内部边界时，尺寸减小会丢失，因为它们也是不规则的。

那么，我如何确保我实际上是在走外边界呢？

4

2 回答 2

2

这是我在评论中建议的答案的扩展。

想象一下，如果你在一个黑暗的迷宫中。你怎么做才能确保你穿越整个迷宫？很简单，只要感觉你左边的墙；可能的话左转；被迫时右转。

好的，更准确地说：

  1. 在地图的边界上找到一个起点，我想你已经知道如何了。
  2. 确保代表您的代理的当前面貌。（上下左右）
  3. 像这样优先考虑运动的相对方向：（左，前，右，后）
  4. 如果可能，朝着优先方向移动。
  5. 走路时，记下访问过的位置作为答案的一部分。并且还要检查您是否已经回到访问过的地方以终止程序。

编辑：更正优先级。在前进之前离开，而不是相反。

于 2013-05-25T17:43:47.883 回答
0

不确定我的问题是否正确，但看起来外边界可以呈现为正交法向量数组。或者更确切地说是部分。想象一个网格，其中地图方块属于单元格。让我们从左上角开始标记我们的部分，从 0 开始。在该符号中，图片外部边框的开始。1 将是 ((3, 2), (4, 2)), ((4,2), (5,2)) 等等。

每个部分，属于两个单元格，一个是地图方块“1”，另一个不是边框。您可以遍历网格并简单地收集它们。

然后，您必须将它们分类为循环。这很容易。如果两个部分有一个共同的坐标 - 它们确实属于单个循环。如果两个循环在它们的部分下方有一个共同的坐标 - 它们是一个循环，您只需将一个数据连接到另一个。

当您有一组绝对不同的周期时，最长的一个，具有最多部分的那个，将是您的外边界。

当然，如果地图是一体的。

于 2013-05-25T17:31:53.863 回答