Path Finding

Apprentice
Posts: 19
Joined: 2005.11
Post: #1
For my C++ class I'm attempting to make a real-time 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 path-finding. I've got a few ideas, but nothing I feel is too solid. So, I'm looking for suggestions, tips, pit-falls 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 way-point. 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 way-point paths every single time the object updates - that would seem very inefficient...

I hope I didn't bite off more than I can chew Rasp But if I did, that's what you guys are for right? Wink And it'll be a fun learning experience.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
google for "A* pathfinding" -- you'll find several good tutorials.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #3
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 each-other'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.
Quote this message in a reply
Member
Posts: 131
Joined: 2004.10
Post: #4
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.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #5
A* will always find a best solution...
Quote this message in a reply
Member
Posts: 269
Joined: 2005.04
Post: #6
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.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #7
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.
Quote this message in a reply
Moderator
Posts: 771
Joined: 2003.04
Post: #8
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 Wink )
Quote this message in a reply
Moderator
Posts: 3,577
Joined: 2003.06
Post: #9
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).
Quote this message in a reply
Member
Posts: 131
Joined: 2004.10
Post: #10
I thought you can't underestimate the cost of the path... Got to pick up my AI book again. Been a while.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #11
you *must* underestimate the cost, or it won't work. Read the links:

http://theory.stanford.edu/~amitp/GamePr...stics.html
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #12
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.
Quote this message in a reply
Moderator
Posts: 771
Joined: 2003.04
Post: #13
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 Wink )
Quote this message in a reply
Member
Posts: 304
Joined: 2002.04
Post: #14
What DoG is saying is that it may not be the shortest path distance-wise 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.
Quote this message in a reply
Moderator
Posts: 771
Joined: 2003.04
Post: #15
OK, we are using different terms then Wink
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".
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  finding a training center - Heeeelp Glauter 1 2,986 Dec 26, 2011 12:30 PM
Last Post: zenkimoto
  Finding an object by name markhula 2 4,587 Mar 29, 2011 08:08 AM
Last Post: markhula
  Drawing a path in-game GregX999 3 3,496 Dec 1, 2010 07:16 AM
Last Post: GregX999
  Kind of a noob question - finding artwork within my .app?? Nethfel 2 2,832 Mar 8, 2010 08:00 AM
Last Post: AndyKorth
  Finding the height of a point on a given list of vertexes? mikey 10 5,382 Jan 4, 2010 05:36 AM
Last Post: mikey