Path Finding
For my C++ class I'm attempting to make a realtime strategy game  just the basic fundamentals. It'll be 2d. I've got a lot of ideas on how to do certain things that I'm going to attempt to do except pathfinding. I've got a few ideas, but nothing I feel is too solid. So, I'm looking for suggestions, tips, pitfalls to avoid... etc. I'm not the greatest programmer, computer science isn't even my major, this is just a hobby, and I know I've set my goals high.
My teacher was recommending a system of waypoints: so if say I create a building, at each of the four corners it would also put down a waypoint. And then when an object is given a move order, it draws a line from its position to it's destination, and if that line intersects any objects it then starts looking at waypoints to find another way around. And from there I see many pitfalls. Performance being a big one  I'm afraid in a map with lots of obstacles, there'd be so many waypoints, my object would trace hundreds of waypoints.
Another problem being, say it starts tracing the waypoints, and it gets to its first waypoint and it sees that it still can't make a straight path to the destination. So then where does it look next?
Or what happens if another unit suddenly moves in the way of it's already chosen path? I don't think I'd want to be evaluating waypoint paths every single time the object updates  that would seem very inefficient...
I hope I didn't bite off more than I can chew But if I did, that's what you guys are for right? And it'll be a fun learning experience.
My teacher was recommending a system of waypoints: so if say I create a building, at each of the four corners it would also put down a waypoint. And then when an object is given a move order, it draws a line from its position to it's destination, and if that line intersects any objects it then starts looking at waypoints to find another way around. And from there I see many pitfalls. Performance being a big one  I'm afraid in a map with lots of obstacles, there'd be so many waypoints, my object would trace hundreds of waypoints.
Another problem being, say it starts tracing the waypoints, and it gets to its first waypoint and it sees that it still can't make a straight path to the destination. So then where does it look next?
Or what happens if another unit suddenly moves in the way of it's already chosen path? I don't think I'd want to be evaluating waypoint paths every single time the object updates  that would seem very inefficient...
I hope I didn't bite off more than I can chew But if I did, that's what you guys are for right? And it'll be a fun learning experience.
google for "A* pathfinding"  you'll find several good tutorials.
A* pathfinding on a static map is pretty easy, don't worry.
You're right when you worried that it will be inefficient though. Even with A*, the computation time will be between n and n^2 computing time depending on how complicated the path is where n is proportional to the distance between the points.
That said, it's not that complicated of a problem, and computers are fast. Just don't do something silly like try to find 10,000 paths a second because you run the pathfinding for every unit every time you update the world. Compute a path for a unit once initially and only update the path if there is a change.
Handling other units moving into eachother's paths could be a bit tricky to handle well. To start out, you could just find a new path if a unit gets blocked on it's next move. The units might take a while to untangle themselves though, not that that isn't common in RTS games.
You're right when you worried that it will be inefficient though. Even with A*, the computation time will be between n and n^2 computing time depending on how complicated the path is where n is proportional to the distance between the points.
That said, it's not that complicated of a problem, and computers are fast. Just don't do something silly like try to find 10,000 paths a second because you run the pathfinding for every unit every time you update the world. Compute a path for a unit once initially and only update the path if there is a change.
Handling other units moving into eachother's paths could be a bit tricky to handle well. To start out, you could just find a new path if a unit gets blocked on it's next move. The units might take a while to untangle themselves though, not that that isn't common in RTS games.
Scott Lembcke  Howling Moon Software
Author of Chipmunk Physics  A fast and simple rigid body physics library in C.
Maybe not totally appropriate to the task but it usually comes up when dealing with finding the shortest path between two points; Dykstra's algorithm. It doesn't hurt to read up on it at least.
A* is one of a few bases on simulated annealing. It may find a solution but it may not find the best solution or it may end up being stuck.
If you are feeling brave and don't care too much about speed or wasted effort, genetic algorithms and breeding to find the best solution. But this is totally overkill. Dykstra's would be better than this.
A* is one of a few bases on simulated annealing. It may find a solution but it may not find the best solution or it may end up being stuck.
If you are feeling brave and don't care too much about speed or wasted effort, genetic algorithms and breeding to find the best solution. But this is totally overkill. Dykstra's would be better than this.
A* will always find a best solution...
http://theory.stanford.edu/~amitp/GameProgramming/
Really good A* resource.
There's different things you can try to speed up pathfinding, but there's no point for just a school class. Just use A* and be done with it.
Really good A* resource.
There's different things you can try to speed up pathfinding, but there's no point for just a school class. Just use A* and be done with it.
Plain old vanilla A* always finds the best path. There are further heuristics that I've seen that trade path quality to keep running time closer to an O(n) bound, but those are not A*.
Scott Lembcke  Howling Moon Software
Author of Chipmunk Physics  A fast and simple rigid body physics library in C.
Yes, as long as the heuristic used never overestimates the cost of a path, A* is guaranteed to find the best solution. On a 2D map, a commonly used (and simple) heuristic that gets you an estimation less than or equal to the true cost is Manhattan distance (or just regular distance )
I agree A* is best for this scenario. I would just mention that you could go exotic and use a basic genetic algorithm as well. It wouldn't necessarily provide the best solution every time but genetic algorithms are pretty neato to learn about if you're struggling for a solution in search of a problem (I'm thinking academic project here).
I thought you can't underestimate the cost of the path... Got to pick up my AI book again. Been a while.
you *must* underestimate the cost, or it won't work. Read the links:
http://theory.stanford.edu/~amitp/GamePr...stics.html
http://theory.stanford.edu/~amitp/GamePr...stics.html
A* star does not find the absolute shortest path. It finds the optimal solution based on the heuristic you give, which indirectly also accounts for performance/search width.
No, it does.
Any heuristic that doesn't overestimate the cost will give you the absolute shortest path (the path from A to B with least cost, if distance is all that is involved, then it would be the shortest distance).
The worst possible heuristic, that won't overestimate the cost is assuming that the cost will always be zero. That will still give you the absolute shortest path, since then the A* is equivalent to Dijkstra's algorithm. The heuristic only serves to avoid searching in pointless branches, therefore speeding up the search.
Check the link OSC posted. Or the Wikipedia article (which says almost exactly what I posted above). Or (my source), "Artificial Intelligence: A Modern Approach" (aka the AI bible )
Any heuristic that doesn't overestimate the cost will give you the absolute shortest path (the path from A to B with least cost, if distance is all that is involved, then it would be the shortest distance).
The worst possible heuristic, that won't overestimate the cost is assuming that the cost will always be zero. That will still give you the absolute shortest path, since then the A* is equivalent to Dijkstra's algorithm. The heuristic only serves to avoid searching in pointless branches, therefore speeding up the search.
Check the link OSC posted. Or the Wikipedia article (which says almost exactly what I posted above). Or (my source), "Artificial Intelligence: A Modern Approach" (aka the AI bible )
What DoG is saying is that it may not be the shortest path distancewise but the 'best' by some other standard (travel time, damage, etc...) Imagine you are travelling from point to point over a field of hot coals and your heuristic is to minimize the blistering on your feet, you may get a path that is much longer than a short direct path, but by giving you a path on the cooler tiles minimizes your damage. Most times you are talking about the shortest path, or the shortest time, but the heuristic can be anything.
OK, we are using different terms then
I would call that the "cost" function, not the heuristic. In the example you mention, "hot coals" would have a higher cost. A* with either an heuristic or none (h() = 0 for every path) will give you the path with the lowest cost, the better the heuristic the faster, but it will always give you the exact same answer (unless there are several paths with the same cost, in which case it doesn't really matter). If the cost is defined simply as distance, then it will give you the shortest path geometrically, otherwise shortest path as in "the one that requires less effort".
I would call that the "cost" function, not the heuristic. In the example you mention, "hot coals" would have a higher cost. A* with either an heuristic or none (h() = 0 for every path) will give you the path with the lowest cost, the better the heuristic the faster, but it will always give you the exact same answer (unless there are several paths with the same cost, in which case it doesn't really matter). If the cost is defined simply as distance, then it will give you the shortest path geometrically, otherwise shortest path as in "the one that requires less effort".
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
finding a training center  Heeeelp  Glauter  1  3,722 
Dec 26, 2011 12:30 PM Last Post: zenkimoto 

Finding an object by name  markhula  2  5,280 
Mar 29, 2011 08:08 AM Last Post: markhula 

Drawing a path ingame  GregX999  3  4,055 
Dec 1, 2010 07:16 AM Last Post: GregX999 

Kind of a noob question  finding artwork within my .app??  Nethfel  2  3,382 
Mar 8, 2010 08:00 AM Last Post: AndyKorth 

Finding the height of a point on a given list of vertexes?  mikey  10  6,634 
Jan 4, 2010 05:36 AM Last Post: mikey 