| View previous topic :: View next topic |
| Author |
Message |
Joel Anderson
Guest
|
 Posted: Mon Oct 27, 2008 12:49 am Post subject: How to make grid based AStar faster |
 |
|
Hi,
I'm not sure why but my post doesn't seem to have appeared so I'm
posting again.
Hi,
I have a mid sized map of 256x256 and I'm looking for ways to
dramatically speed the A* algorithm up with as little work possible (I
don't want to risk changing what is already working).
Here's the specs:
- 256x256 grid map with clusters of trees around the place (some
spread across more then half the map).
- Its classic RTS style.
- The map has about 200 units moving about at any one time. It starts
with a small number and they increase over time.
- Some places on the map currently require 5000 iterations to find the
destination. Currently have to terminate he path-finding early
because this is just to expensive.
- Units can take up more then one square (up to about 10) and they
mark area around them as to be avoided (ie increase the cost of
traveling on those cells)
- The algorithm needs to behave very accuratly for nearby units and
reasonably for far away units.
Here are some of the improvements I've implemented however they are
still not fast enough:
1) Changed the heap to use 2 lists, one sorted and one unsorted. I
only add to the sorted if its within the sorted range. When the sorted
runs out I partial sort the unsorted and move those nodes into the
sorted list.
2) The path has a limited number of steps (1000) before it reports
failure. On failure I simply choose a smaller path (ie a mid path,
then if that fails even smaller paths) and recompute the larger path
when the unit gets some way into that path. This appears to work
quite well, although I hope that I can improve the accuracy of the
large paths so this is less necessary.
3) Added lots of rejection code to try to reject nodes from the heap.
Such as rejecting costs that were too large and rejecting a node if
its worse then the worse node we've stored when we've got more nodes
in the heap then steps remaining (see 2).
A couple of observations:
- Even with these changes the algorithm spends the majority of its
time in either the std::partial sort or the std::upper_bound (for
binary insertion). -> ie the heap (al-bit modified)
- There are a lot of nodes with the same cost in the sorted list.
- Pathing fails a lot because it can't find the complete path and as
to fall back to less optimal solutions. It might be faster if I first
compute without units to see if its actually possible to get to a
location in the limited number of steps I have (although it would have
to be very fast).
I've looked around the web for some techniques such as hierarical
A*'s. However many of them seem like they might require more then a
couple of days work and are risky.
It seems to me that a lot of the computation in my A* algorithm is
going to waste. I'm wondering if there's a way to effectively save
off information learned in each path, that would lend it self well to
the ever increasing units. The approach of saving of directions in
each node to each other node is obviously not feasible without some
radical compression strategy.
The memory usage of the path-finding is 5m at the moment and I
probably have about 2m to spare.
I was thinking, what about when processing a path without unit
collisions (ie the path hasn't hit any yet)? I could remember record
nodes that where rejected (ie node A can't reach node B, i a realistic
number of steps). Sorting this in a run-length encoded array in each
node may still be to much memory and may be time consuming to
decompress. I was thinking that maybe a hash map of nodes rejections
could be maintained with a limited size (and throwing out of old
entries). However I worry that it might contain a list of entries
that are seldomly reused. Anyway if this did work I could use that
to reject nodes early and thus allow for more steps.
Has anyone else tried this?
What where your observations?
Any thoughts on how could I compress this information better?
Would there be anything better I could spend that memory on?
Any other A* path-finding optimizing suggestions?
I thought I might ask the giants so I'm not re-inventing the
wheel :)
Thanks in advance. |
|
| |
|
 Back to top |
Wolfgang Lorenz
Guest
|
| Posted: Mon Oct 27, 2008 7:52 am Post subject: Re: How to make grid based AStar faster |
|
|
I have never implemented the A* algorithm myself, but as you mention a
heap, there are some general speedups tips which may apply here.
An absolutely no-no is to call alloc/free for each node. Instead use a
sub-allocation scheme where you allocate one large block of memory and
then part it. As maloc/new consumes at least 32 bytes on modern
compilers, this will also save you some memory.
5 MB is too large to fit into the L2 cache.
In general, pointer structures to distributed memory locations are bad,
sequential arrays are about 10 times as fast.
--
http://home.arcor.de/w.lorenz65/mlbench
No mercy for the cheaters in machine learning! |
|
| |
|
| Back to top |
|
