Waypoint generating algorithm for graph [on hold]

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
• 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