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?

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.

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)

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

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 =)

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.

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.

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.

=)

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.

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]