I've got a graph filled with 'walkable' nodes that I want to generate waypoints for. I've searched for some articles on this but have come up empty-handed. There's over 2 million tiles (walkable nodes) in my graph that I have to find the shortest path to each for, so it seems like implementing waypoints into my pathfinding will speed things up drastically.

I'm unsure how to generate them though. There's plenty of articles on how to traverse waypoints using A*, but none of them talk about how to generate those waypoints in the first place. Do you just have to create them manually? Do you link each tile node to a waypoint node? How would the whole concept work?

put on hold as unclear what you're asking by Doc Brown, GlenH7 yesterday

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • A* generates a path, which is a sequence of nodes to traverse. In your case, is there a difference between those nodes and waypoints? In other words, is there anything special about a waypoint [by your definition], compared to a node which a path finding algorithm had found? – Nick Alexeev Apr 23 at 17:54
  • In the context of your situation, what exactly is a waypoint and how does it differ from a regular node? – Dan Pichelman Apr 23 at 18:15
  • 1
    So this is what I meant: theory.stanford.edu/~amitp/GameProgramming/… I assumed that 'waypoints' was common terminology in pathfinding because of this article. So, to clarify: a waypoint in the context I'm trying to use is a point that you know is reachable, but you want to add it instead of the tiles to speed up the pathfinding performance. So 10 tiles could be represented as a waypoint. Then you'd just have to traverse to that waypoint (in the waypoint sub-set) to get to any of those 10 tiles. – Jeff smith Apr 23 at 18:50
  • @Jeffsmith From the article you linked: "...As with a grid, we have a choice of using polygon centers, edges, or vertices as navigation points." – Pikalek Apr 23 at 19:33
  • Voting to close as "unclear", as it seems OP has abandoned the question and doesn't show any effort to give an understandable explanation. – Doc Brown May 23 at 20:10

Let me know if I understand your problem correctly:

You have a large graph for which you want to compute shortest path between arbitrary pair of nodes in short times. In order to be able to do that you state that to go from node A to node B, one first have to find the path to the pre-defined waypoint of node A follow the pre-computed path between the pre-defined waypoint of node A and the pre-defined waypoint of node B and then find the path from the pre-defined waypoint of node B and node B.

Your question is then, how should I decide which node should be a waypoint, and for every node which node is selected to be its waypoint?

The first thing that you would need to do is cluster your graph (how you want to do that is another question in itself). Then for each cluster, compute the distances between every pair of nodes of the cluster. Then select the node which minimize the maximum distance to another node of the cluster to be the waypoint of all other nodes that are part of the cluster.

Then "all you have to do" is pre-compute the paths between your waypoints.

  • So I think you've got the concept I'm trying to explain. I guess I did a poor job, so I'll try to re-write it. The part now that I still can't answer (and my main question) is how do i do the "Then for each cluster, compute the distances between every pair of nodes of the cluster." How do I do this computation? What is a good algorithm to do this? – Jeff smith Apr 23 at 19:40
  • @Jeffsmith each of your cluster should contains a reasonable number of nodes (in the range 10-100 given the size of your problem I guess). You can then easily use the Floyd-Warshall algorithm to compute the shortest path between every pair of nodes of the sub-graph defined by the cluster. – Renaud M. Apr 23 at 19:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.