path-finding - A* 寻路 - 最接近无法步行的目的地

Question

我已经有一个可行的 A* 实现。问题是，如果您选择无法行走的目的地，则不会返回任何路径。我希望能够得到我能得到的“最接近的”。

最好的选择是完全动态的（不仅仅是检查目的地周围的 8 个图块来尝试找到一个）。这样，即使他们点击了一个被一大块不可行走瓷砖包围的不可行走瓷砖，它仍然会尽可能靠近。

Answer 1

While the simple answers provided here MIGHT be sufficient enough, I think it depends on your game type and what you're trying to achieve.

For example, take this play field (sorry I'm reusing the same software I used to show you the fog of war :)) :

As you can see, an Angry Chicken is blocking the path between the left side and the right side. The Angry Chicken could be anything... if it's a static obstacle, then going with the lowest h node might be enough, but if it's a dynamic object (like a locked door, draw bridge, etc...) the following examples might help you find out how you want to solve your problem.

If we set the destination for our Hero on the other side

We need to think what we want the path to be, since obviously we can't reach it. Using a standard heuristic like manhattan distance or euclidian distance, you will get this result:

Which might be good enough, but if there's any way our little Hero could interact with the chicken to pass, it doesn't make sense at all, what you want is this

How can you do this? Well, an easy way to do this is to pathfind on hierarchical graphs. This sounds complicated but it isn't. First, you want to be able to build a new set of high level nodes and edges that will contain multiple grid nodes (or other representation, wouldn't change a thing)

As you can see, we now have a right blue node and a left red node. The arrow represents the edge between the two nodes. How to build this graph you ask? It's easy, simply start from an open node, expand all of its neighbors and add them to a high level node, when you're done, open the dynamic nodes that could lead to another part of the graph and do the same.

Now, when you ask for a path from our Hero to the red X, you first do the pathfinding on the high level... is there a way from blue node to red node? Yes! Through the chicken.

You can now easily know how to navigate on the blue side by going to the edge that will allow you to cross, which is the chicken.

If it was just a plain wall, you could determine very quickly, by visiting a single node, that there is NO way to reach on the other side and then handle it the way you want, possibly still performing an A* and returning the lowest h node.

Answer 2

您可以保留一个指针，该指针包含具有最低 h 值的图块，然后如果没有返回路径，则只需生成指向您所持有的图块的路径。