C++ 带星号的寻路，优化

Question

我想知道我是否可以稍微优化我的寻路代码，让我们看看这张 map :

+ - wall, . - free, S - start, F - finish
.S.............
...............
..........+++..
..........+F+..
..........+++..
...............

人类会看着它说这是不可能的，因为终点被包围了......但是 A-star 必须检查所有字段以确定没有可能的路。好吧，这不是小 map 的问题。但是当我有 256x265 map 时，检查所有点会花费很多时间。我认为当终点周围有封闭节点时我可以停止搜索，我的意思是:

+ - wall, . - free, S - start, F - finish, X - closed node
.S.............
.........XXXXX.
.........X+++X.
.........X+F+X.
.........X+++X.
.........XXXXX.

我想在这种情况下完成(没有进入“房间”的入口)。我想检查 h，虽然没有打开的节点越来越近，然后完成...但我不确定是否可以，也许有更好的方法吗？

感谢任何回复。

Answer 1

首先这个问题用breadth-first search 更好地解决了，但我假设您有充分的理由改用 a-star。但是我仍然建议您首先使用某种搜索(广度优先或深度优先搜索)检查 S 和 F 之间的连接性。这将解决我们的问题。