Sign in to follow this  
gpr1me

Pathfinding Suggestions

Recommended Posts

gpr1me    122
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

Share this post


Link to post
Share on other sites
Sabonis    169
A good algorithm for finding the shortest path is dijkstra's algorithm.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

A good way to set waypoints is maybe to specify your start point and endpoint. Now you should add to your data structure whether you can traverse a specific node (node as in vertice in a tree... or it could be a piece of your map, depending on how it's set up) or not, depending if there's trees etc. Then since you already have a graph set up, finding the shortest path should be easy as pie!

Hope this helps

Share this post


Link to post
Share on other sites
gpr1me    122
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.

Share this post


Link to post
Share on other sites
Barius    325
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.



Share this post


Link to post
Share on other sites
gpr1me    122
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.

Share this post


Link to post
Share on other sites
leiavoia    960
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this