Back to General and Gameplay Programming

A* path finding

General and Gameplay Programming Programming

Started by Lode October 25, 2007 12:56 PM

15 comments, last by beepmaster 16 years, 5 months ago

Lode

1,003

Author

October 27, 2007 06:16 PM

Quote:Original post by Kylotan
The first thing I would do is to add a lookup table to see if a node is on the closed list. At the moment, imagine that you've explored half your 16x16 map, so there are about 128 nodes on the closed list if your map has plenty of obstacles. Every new node you explore generates 8 neighbours, and for each of those neighbours, you have to compare it with 128 nodes on the closed list. That's looping over 1024 existing nodes every time you investigate a new one. And it gets worse as the search approaches the goal and the closed list keeps growing. Really you want to get this to be an O(1) operation so that it's just 8 instant comparisons.

I'd probably just implement this lookup table as an array of chars, (World_Width * World_Height / 8) in size. (Round up to nearest whole char.) std::fill it with zeros at the start, and set the bits as you add nodes to the closed list. If you have a little inline function to set and check individual bits, this is great.

Although to be honest, with a world as small as yours, you can just use an array of bools. But if your world gets bigger you'll probably find that packing it into a structure eight times smaller helps.

I did this and used an std::vector<bool> as 2D array. std::vector<bool> is "special" (if not somewhat evil) and will actually use only 1 bit per value, is this correct?

It's a lot faster now, even on a much older PC I don't actually see the lag shock anymore when placing new towers. Well ok, a little bit, when the path gets longer (and compiled without -O3).

Thanks! I'll have to think better about what data structures to use in the future :)

Homepage | LodePNG

Kylotan

10,510

October 29, 2007 05:40 AM

Yes, I believe std::vector of bool implements the bit-packing scheme I mentioned automatically (yay!) but ends up being a non-conformant container as a result (boo!) Luckily, the latter is unlikely to be a problem for you here.

kirkd

505

October 29, 2007 10:31 AM

Give IDA* a try. Essentially, you perform a depth first search up to a certain level of depth. If you don't find your goal, you start over with a slightly increased depth maximum. Here's some pseudo-code:

root = start nodethreshold = root’s g()		perform a depth-first search starting at rootif goal not found,    set threshold = minimum g() found that is higher than current threshold    repeat depth-first search starting at rootdepth-first search(node):    if node = goal        return goal found    if node’s f() > threshold        return goal not found    else        for each child of node, while goal not found, depth-first search(child)

I found that despite the fact that you're repeating the search during each iteration, I saw a massive speed up. For the domain I'm working in it increased the search speed by about 1000X. Seriously.

-Kirk

EDIT: By the way, use the same heuristics and scoring that you're using with A*. f() = g() + h() works the same.

drakostar

224

October 29, 2007 01:47 PM

I'm not sure about the implementation of vector<bool>, but the standard bitset class is appropriate for this kind of situation.

Kylotan

10,510

October 30, 2007 11:59 AM

Quote:Original post by kirkd
Give IDA* a try. Essentially, you perform a depth first search up to a certain level of depth. If you don't find your goal, you start over with a slightly increased depth maximum.

Hmm, this algorithm is much simpler than I'd been led to believe (which doesn't surprise me, considering how some AI people tend to only talk in greek letters and calculus). However, don't you run the risk of getting a slightly sub-optimal path if you increase the maximum depth by too much, meaning you end up finding the first solution at this depth level, rather than the best solution at this depth level? I'm well aware that this is rarely a big deal in pathfinding situations however, given the small degree of this error.

kirkd

505

October 30, 2007 04:16 PM

The pseudo-code as it is may have an issue, but you can overcome that by doing a complete depth-first search at each iteration. You would just have to accumulate all the instances you reach the goal and compare their path costs. The additional cost would probably not be much.

Another variation is Fringe Search in which you retain the search path just beyond your threshhold and then rather than repeating the entire search tree with the new threshhold, you step directly into the fringe and start there. I've found this version to be slighly faster still - maybe 1-5% or so.

-Kirk

beepmaster

116

October 31, 2007 04:05 AM

My little advice about your project :
Think to cut the map of your project in sectors of different size, from bigger sector size to smaller ones...

When you find a solution with big sector size to reach destination: just eliminated sectors that can't reach the goal point, and reduce sector size.

I make A* programm in JAVA that work fast and fine, with C++ you can make faster solution :)

Good luck

A* path finding

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A* path finding

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines