Sign in to follow this  
EDI

Pathfinding Oppinions

Recommended Posts

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]

Share this post


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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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 =)

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
I would rather there be a way to early-on decide if
'there is no way to get to this point from that point'
but i get the feeling that there is no such thing (short of trying to get in every possible way).

however, this has got to be a common problem among pathfinding, so I am wondering how other people solve this issue?



Share this post


Link to post
Share on other sites
Well, this may sound wierd, but you could go with a "magnification" like design. I just made this up, so it might have a nice. Without further ado...

So lets say you have several wings to a building, and each wing has several rooms. How do you get from room a in wing 1 to room z in wing 500? Well, you go to the highest level: wings. You find what wings are attached. If you cant make it, then the journey is impossible. If you can make it, then you search the wings that you used and do rooms. Then, using the rooms that you go through, you create the path with walking spaces or whatever using A*. This should provide early out problems, and also significantly cut down on searching space.

So lets say, in your case, you are trying to get to a room within the same wing. You simply cut out the top level (it would return immediately, anyway), and use room to room: using "open" direction values for doors, or something clever like that. If you cant get in the room, you dont bother doing the last search...unless you want the person to get as close to the room as possible and stop. And if that is the case, you simply alter the "final spot" location to right outside the door.

The only issue would be the tolerance level for A*.

That might work. Maybe its too complicated for what you need it for.

Share this post


Link to post
Share on other sites
One option is to start an A* search from both ends at the same time. In other words, have the destination start searching for the beginning and the beginning start searching for the destination. If either one runs out of nodes, there is no path. If they ever reach the same node in the search, then you've found your path. I wish I could remember the computer science term for this type of A* search so you could google for an example. (All I can remember is "iterative deepening A*" but that has to do with only searching out one node away the first time, then trying two nodes, then three nodes, etc)

Share this post


Link to post
Share on other sites

Hi,

You can consider a room as an A* Node. To this approach there are variants: You can first query if the Entity's goal is in another room, and then use a pre-computed path from the point it is standing to the goal (the room). Before picking this "best path" you query if the room has access; In case it has not, you do a simple A* from the current node to the nearer Node of the room that is available - that is - its door.

In case the goal Node is not in another room, you use A* normally, searching your own ground.

Never tried it out though, just assuming it would work.

Son Of Cain

Share this post


Link to post
Share on other sites
I ended up using an 'abortcount'

for a given path, i get the manhattan distance from the start to the end, then I square it. This is the max number of nodes I will open before I give up.

while this somewhat defeats the purpose of pathfinding, it works in most cases, and only fails for _really_ complex and winding paths.

lukily in our game most of our paths are fairly straight and fairly short, so It seems as if it will work out fine.

Son-Of-Cain:
I found your java code very usefull, in fact, especialy how you would extract the best node from the open list. I had a system before that would jump through some hoops to store them sorted, but switched to yours since it simplified things, and it doesnt seem to hurt performance.

so it seems that my pathfinding troubles are over (for now *gulp*),
thanks to everyone who helped me =)

Share this post


Link to post
Share on other sites
Well, even though its over, but I just wanted to throw this out.

Wouldn't a simple Scenegraph with connectivity solve your problem? Basically have each room be a node and all connected rooms be a child node. You then don't really need to do an A* on that or anything, just take the hild node and ask if the current node you're in is a parent. As simple as that, can almost be done in constant time, but most likely linear at worst.

Share this post


Link to post
Share on other sites
Glade to hear your problem is solved. When you got extra cash check out AI Game Programming Wisdom by Charles River Media. Its got a bunch of articles and ideas on speeding up the path planning process as well as some other AI tidbits.

Share this post


Link to post
Share on other sites
Quote:
Original post by WeirdoFu
Well, even though its over, but I just wanted to throw this out.

Wouldn't a simple Scenegraph with connectivity solve your problem? Basically have each room be a node and all connected rooms be a child node. You then don't really need to do an A* on that or anything, just take the hild node and ask if the current node you're in is a parent. As simple as that, can almost be done in constant time, but most likely linear at worst.


yes, that would work, however, having that dataset is another thing entirely =)

we are 90% done with our game (it's taken about 3 years),
plus I don't think we would have liked to specify what a 'room' is via our map editor, I guess there would be ways to automate that.

but yes, if each major area had a node or 'waypoint' in it, then it would be simple to pathfind from your position to the waypoint, then follow the waypoint out, and it would be also simple to have the doors in the room be able to 'shut off' a waypoint, however data structures of that complexity and magnitude would be somthing you would have to develop ahead of time.

at the moment all we know is that there is a grid of tiles, and some of them are not traversable, when a door is closed it makes the tiles it encompases immovable, and vica-versa.

=)

Share this post


Link to post
Share on other sites
Hello everyone. I,m a chinese, and my English is very poor, I just can fellow a little what you said. But I suggest that may be Breadth-First Search is not bad for your situation.

Share this post


Link to post
Share on other sites
If you have many open areas (ie sections of walkable straight lines, squares, or even just 'blobs' of walkable tiles), it is easy to have an extremely fast A* search. Basically, instead of setting each walkable tile as a node, you use a preprocessing step to group tiles. The groups are made so that each tile in the group can get to every other tile in a group by walking a straight line(ignoring dynamic obstacles). Then, you search using these groups as nodes and only search the nodes inside a group once the character is standing inside that group and needs to get to the next group in the path. Really, if there are no dynamic obstacles inside a group, you don't even need to search inside it (just go toward the nearest node to the next group on the path since you're guaranteed to be able to move in straight lines inside a group since they're made that way).

As for how to pick which nodes go in which groups, I'd probably use a variant of a genetic algorithm and randomly pick some nodes to each put in their own group, then start adding random nodes to the proper group or two a new one if they can't fit an existing group (because every node in a group has to have a straight walkable line to every other). Do it 10-20 times for each level, and pick the one that ends up with the fewest groups. This would be done perhaps on level save in the level editor, so it wouldn't make loading much slower (beyond loading the few KB extra data from the level file).

Also, one (or all?) of the Game Programming Gems books has some information about speeding up A* even further, but they're lower level optimizations that would speed up the algorithm using groups or not.

Also, A* doesn't require much in the ways of searching and sorting, and much of it can be optimized away by imposing some constraints (like limiting the system to one search at a time, or N searches at a time with N*X*Y bits of memory usage {for 200*200, that'd be ~5KBytes per N)). The rest of the needs can easily be met by STL in a manner that is fast enough for all but extremely taxing cases (which I don't think you'd have, having seen some images of your game).

[Edited by - Extrarius on April 2, 2005 7:18:23 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster


Use A* with suggestions :


Hierarchical ... coarse/fine pathfind shortens lengths...

Use Heap Q to optimize openlist sorts (tree like sort functionality)

Inline functions -- guy I talked to more than a year ago on USENET game AI group
used MSC++6 professional (inlines worked) ran 3X as fast as me recompiling his code
on MSC++6 Standard ($@#$%& no optimization including NO inlining.

Squareroot approx abs_dX abs_dY dist = longest_side + 1/2 of shortest_side

Share this post


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


If this is a frequent problem, you have several options depending on your access patterns:

1) Cache results of previous searches.

2) Create a separate 'connected components' graph. Associate each of your pathing space nodes with a node in the component graph. Before doing a search for a full path, do a search over your connected components graph to verify that a path actually exists (optionally, you may be able to make this into a table if your world is static and the number of islands is low).

[Edited by - BrianL on April 8, 2005 10:23:33 AM]

Share this post


Link to post
Share on other sites
Both Extrarius' and BrianL's suggestions equate to finding a maximal clique graph from the natural connectivity graph. Certainly this is a good optimisation that can be performed offline IF your maps are static.

However, if your maps are static, given the trivially small size of your search space, I think you'd find a simple flood fill algorithm, such as the Distance Transform Algorithm, far more efficient for your needs. It also has the aesthetic side effect of being able to easily predict when a destination is unreachable.

Furthermore, suboptimal paths are trivially found by permitting an erroneous transition of states with a small probability (the probability being proportional to the level of supoptimality).

There are also some lovely optimisations one can do when using contiguous memory to represent the map that really speed the algorithm up.

Just my 2 cents worth...

Cheers,

Timkin

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