算法帮助 : Walking the boundaries of a map

Question

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

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

目前我:

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

Steps Taken

这对北部地区来说效果很好。但是，当我到达南部区域时，它会检查北部并发现它是一个未访问过的位置并前往该区域。它搞砸的坐标是 13,11。

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

我考虑过按照与之前相同的操作顺序添加边界检查(NESW)。然而，也有可能把它搞砸。

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

走完整个外界怎么办？

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

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

Answer 1

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

Imagine if you're in a dark labyrinth. what do you do to make sure you traverse the whole labyrinth? Simple, just feel the wall to your left; turn left whether possible; turn right when forced to.

好的，更准确地说:

1. 在 map 的边界上找到一个起点，我想你已经知道怎么做了。
2. 确保代表您代理的当前面向。 (上、下、左、右)
3. 优先考虑移动的相对方向:(左、前、右、后)
4. 如果可能，朝优先方向移动。
5. 边走边记下访问过的位置作为答案的一部分。并检查您是否已返回访问过的地方以终止程序。

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