Pathfinding Oppinions
Author
Greetings All =)
For a while now, i have been using Dijkstra's algorithm for plotting paths on our tile maps, however it has turned out to be a large bottleneck for us especialy as path lengths and number of enemies increases, so, we need to choose somthing new.
Now, after some reading and some thinking, I discovered that ususaly a single pathfinding routine will not be optimal in all cases, and in choosing a routine you sacrifice path accuracy(shortest) for speed.
So, the two routines i have experimented with thus far have been
Dijkstra's and Best-First
aparently A* combines both of these but allows tuning through use of a Herustic(sp?), however looking over some A* psuedo code, it seems that it requires lots of list searching and list sorting, which seems it would slow things down.
our maps are large 200x200 tiles, and contain many obstacles.
we are looking to speed things up as much as possible, but get better paths than what common Best-First gives us.
could I get some oppinions on what we should be using?
thanks =)
P.S. I should probably mention that for blocked tiles (such as doors), I don't even take them into account, that is I never add them to the open list *since they arn't open* is this part of my problem? should they instead be added with a maximum cost?
[Edited by - EDI on March 29, 2005 8:29:48 PM]
If you're generating paths to a single specific goal then optimized A* is about as fast as you can get short of building a shortest path lookup table. You're going to need Dijkstra's if you are trying to generate path to the nearest x(x being possibly many goals of a certain type).
If your environment isn't dynamic then you could generate a lookup table. It uses nodes^2 memory and just stores an index to the next point in the path.
If your tiles never go above 256 in number you could use a single byte for the index, and at most have a 256 * 256 * 1 = 64kilo-bytes of usage for the lookup table. Then it would be as simple as:
unsigned char nextTile = table[currentTile][goalTile];
200x200 really isn't that big of a tile map, even with alot of obstacles. A* should be able to smoke through a path query on a map like that. Generally Dijkstra expands into more nodes since it only takes into account given cost, while A* takes given cost as well as heuristic.
If your environment isn't dynamic then you could generate a lookup table. It uses nodes^2 memory and just stores an index to the next point in the path.
If your tiles never go above 256 in number you could use a single byte for the index, and at most have a 256 * 256 * 1 = 64kilo-bytes of usage for the lookup table. Then it would be as simple as:
unsigned char nextTile = table[currentTile][goalTile];
200x200 really isn't that big of a tile map, even with alot of obstacles. A* should be able to smoke through a path query on a map like that. Generally Dijkstra expands into more nodes since it only takes into account given cost, while A* takes given cost as well as heuristic.
Hi,
I'm using A* in my turn-based strategy game. I know it's quite a different approach, but in the resources I've found there's some explanation of how you can tune your heuristic for better performance.
Usage of heuristics in A*.
I believe A* can handle the task fairly well, even for the situation you described. I wish you best of luck!
Son Of Cain
Author
It seems like A* is going to be my best bet, especially with the ability to implement a strategy pattern for the huerustic to allow for different levels of accuracy.
Where might I find a working C++ implementation of A*? I found a few online but most were cluttered with game specific stuff and hard to understand.
thanks =)
Where might I find a working C++ implementation of A*? I found a few online but most were cluttered with game specific stuff and hard to understand.
thanks =)
Hi EDI,
In the same site I referenced, there are implementations in C++ for the A* - though I never checked them, because I'm using a java variant of it.
It's fairly simple, really; By its pseudo-code you can guess how does it works, and even tune it to your specific needs. STL is a good try with A*, but as DrEvil said, you can use a byte and lookup tables.
If you would like to see java code, browse our CVS here. It's under net.java.dev.bta.engine package.
Hope to have helped you,
Son Of Cain.
Edit - just found one:
Path.h
Path.cpp
In the same site I referenced, there are implementations in C++ for the A* - though I never checked them, because I'm using a java variant of it.
It's fairly simple, really; By its pseudo-code you can guess how does it works, and even tune it to your specific needs. STL is a good try with A*, but as DrEvil said, you can use a byte and lookup tables.
If you would like to see java code, browse our CVS here. It's under net.java.dev.bta.engine package.
Hope to have helped you,
Son Of Cain.
Edit - just found one:
Path.h
Path.cpp
Though you decided to switch over to A* now...
Remember one thing (if you haven't already done that. Else sorry)
Never do path finding for more than a few units at a
time. Instead put them in a queue and spread them out
over several game cycles...
Remember one thing (if you haven't already done that. Else sorry)
Never do path finding for more than a few units at a
time. Instead put them in a queue and spread them out
over several game cycles...
Have you considered looking into other algorithms that aren't specifically designed for pathfinding? Well, I'm thinking of something like Tabu Search.
Now the reasoning behind that is that you have a very discrete space where every tile has a fixed number of neighbors. A* is good and nice for many situations, but sometimes, it may be interesting to explore other options.
Tabu search is typically used for combinatorial optimization problems, and in a discrete search space its just simply trying to get from candidate solution A to candidate solution B with the fewest moves possible without being trapped at a local optimal.
So, for the current case, tabu search can be seen as a modification to the Next Best method, or in academic terms, steepest descent hill-climbing. The biggest feature of tabu search is that it uses a tabu list of a certain length to prevent back-tracking to positions already visited unless a certain criterion is met. This may greatly help reduce over-head computational-wise and just add a small storage overhead for each entity (a short-term memory). You may not be guaranteed the best possible answer, but you may get movement that is more realistic.
If you're interested I can post pseudocode for an implementation of Tabu Search that may satisfy your needs. Or you can simply find stuff on tabu search lying around on the web, since its been around for a long time, mainly in the field of operations research.
Now the reasoning behind that is that you have a very discrete space where every tile has a fixed number of neighbors. A* is good and nice for many situations, but sometimes, it may be interesting to explore other options.
Tabu search is typically used for combinatorial optimization problems, and in a discrete search space its just simply trying to get from candidate solution A to candidate solution B with the fewest moves possible without being trapped at a local optimal.
So, for the current case, tabu search can be seen as a modification to the Next Best method, or in academic terms, steepest descent hill-climbing. The biggest feature of tabu search is that it uses a tabu list of a certain length to prevent back-tracking to positions already visited unless a certain criterion is met. This may greatly help reduce over-head computational-wise and just add a small storage overhead for each entity (a short-term memory). You may not be guaranteed the best possible answer, but you may get movement that is more realistic.
If you're interested I can post pseudocode for an implementation of Tabu Search that may satisfy your needs. Or you can simply find stuff on tabu search lying around on the web, since its been around for a long time, mainly in the field of operations research.
Forget it...I'll just post it anyways....while I'm at it...
-Set a fixed tabu list size, maybe 5 - 10 would be good.
1. Starting position (calculate distance to target with possibly obstacles inbetween as penalty, etc.)
2. look at all neighboring spaces and calculate their fitness/distance to target
3. eliminate the neighboring spaces that are in the tabu list from consideration
4. choose the neighboring space with best fitness and move there
5. If no neighboring spaces are left, then choose best one that violates a tabu entry
6. push the last space that you were just at into tabu list and pop out any entries if necessary to keep list within length setting
7. repeat 2 - 6 until goal is reached
That's the basic algorithm for the tabu list. There are many variations to it to improve performance, but you can probably figure the rest out.
-Set a fixed tabu list size, maybe 5 - 10 would be good.
1. Starting position (calculate distance to target with possibly obstacles inbetween as penalty, etc.)
2. look at all neighboring spaces and calculate their fitness/distance to target
3. eliminate the neighboring spaces that are in the tabu list from consideration
4. choose the neighboring space with best fitness and move there
5. If no neighboring spaces are left, then choose best one that violates a tabu entry
6. push the last space that you were just at into tabu list and pop out any entries if necessary to keep list within length setting
7. repeat 2 - 6 until goal is reached
That's the basic algorithm for the tabu list. There are many variations to it to improve performance, but you can probably figure the rest out.
Author
I ended up going with an A*-like system, that is currently using Manhattan Distance for it's 'heurustic'.
things seem to be working good, but there is one issue that I would like some feedback on solving.
supposed I am in a large room, and i try to go into a small room, but there is no entrance into that room, it's door is closed and it is unreachable.
this seems to end up making the search try every possible way of gettting into that room, which isn't really good.
are there any strategies I can use to avoid this? somthing like an 'early out'?
thanks =D
things seem to be working good, but there is one issue that I would like some feedback on solving.
supposed I am in a large room, and i try to go into a small room, but there is no entrance into that room, it's door is closed and it is unreachable.
this seems to end up making the search try every possible way of gettting into that room, which isn't really good.
are there any strategies I can use to avoid this? somthing like an 'early out'?
thanks =D
Do you want the search to end at the door? Or just not even execute?
Well, one way I can think of is to make the algorithm "give up" after a while. In any case, you will still need a memory structure to remember that you've searched certain places, or else, you'll just keep back-tracking along the walls bordering the two rooms.
Well, one way I can think of is to make the algorithm "give up" after a while. In any case, you will still need a memory structure to remember that you've searched certain places, or else, you'll just keep back-tracking along the walls bordering the two rooms.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
