I am wrting a pathfinding program in OpenGL and i am having a little trouble as to how i want to respresent Waypoints on my map. I know i could use a simple A* algorithm but i wanted to try something different so i decided to try using Waypoints and an all-pair shortest path algorithm. Basically once my waypoints are positioned on my map i will be representing them as vertices in a graph and have weighted edges between them. After the graph is setup i will run an all-pair shortest path algorithm on my graph to get the shortest paths between each pair of vertice. This will all be pre-processed before the openGL window appears so it will be an extremely fast at run time. I just have to store a table in memory for this pre-processed solution. Ok so here is the point of this thread. I am not sure about how i will be making my waypoints. Right now i made a waypoint class and it stores an x, y position and has all the regular constructors and stuff like that. But should i position them manually or write an algorithm to do it. I was thinking just to place them like a certain distance away from eachother by running a simple double for loop. I wont place a waypoint if there is an obejct in that position already. And i will have auto placements of waypoints around each obejct that i place on the map (like rocks, tree's, mountains, ect...). I think this is a good solution but i just wanted to see if anyone can see downsides to this technique? Im sure it's not the best pathfinding technique out there but i think it will be fun to do. Any suggestions or comments would be great. Thanks

Yeah i am going to be using floyd warshall all-pair shortest path algorithm. Dijkstra's algorithm is good for finding the shortest path between two vertice's but floyds find the shortest path between every pair. And if there are a large number of edges in the graph (about the same number of edges as vertice's) then floyds algorithm is faster.

When you place the waypoints automatically, you will need a way to make sure that you only connect two waypoints that are actually directly reachable from each other (i.e. there is no obstacle between them). Even then, a game object might not be able to go from one to the other directly, because the path might be too narrow. So it will be more complicated if your game has complex obstacles.

Yeah this is true. Well i have decided to manually place the waypoints and edges between them. For the weight of the edge it will be a combination of the distance (easy calculation) and the type of terrain.

Maybe i'm not understanding the issue, but if you reduce it to waypoint-to-waypoint calculations, you are still "traversing a graph of nodes" only the nodes are waypoints now and not tiles or points. So you really haven't gotten away from using something A*. It would work the same on either. Does that make sense?

One thing i did for a previous project was, at least with user-definable waypoints, you give the unit a start and end, only you move the "end" to the next closest waypoint when it reaches a waypoint. That is, when the unit reaches a waypoint target, you reset the "end" and create a new A* path, from Node2 to Node3. In between any two waypoints (nodes), you do your actual concrete maptile walk using A* again.

So essentially you have two layers of A* going on here. One for traversing the waypoints, and one for the nitty-gritty details of getting from waypoint A to B. I'm sure doing something like that would really speed things up, especially for enemy AI that doesn't have to look especially smart all the time.