 |
|
| Computers Forum Index » Computer - Games Programming (Algorithms) » Fast A* Pathfinding, Precomputing in mid sized map... |
|
Page 1 of 1 |
|
| Author |
Message |
| Joel Anderson... |
 Posted: Sun Oct 26, 2008 2:09 am |
|
|
|
Guest
|
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 I have to terminate the 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 |
|
|
|
| Miss Elaine Eos... |
| Posted: Sun Oct 26, 2008 6:16 am |
|
|
|
Guest
|
In article
<3bc011ab-8923-4c4a-86b7-071c72006e08 at (no spam) e38g2000prn.googlegroups.com>,
Joel Anderson <hohums at (no spam) gmail.com> wrote:
Quote: 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).
[...]
Thanks in advance.
To begin with, strip the problem down to the bare minimum case. You can
make it a "worst case", if you like, (long path, big unit, complex
terrain), but optimize for one unit. Once you have the one-unit path
optimized, adding others will still be optimized.
One of the best debugging/optimization tricks I've ever seen is
deceptively simple: Have the computer display on the screen what *IT*
thinks it's doing. Too often, a developer convinces himself of what HE
thinks the computer is doing, and wastes a lot of time chasing down
non-problems and looking in wrong-corners. Have a "debug" mode whereby
your A* draws out the squares it's considered, their various values,
color squares added to the "closed" heap a different color, etc. An
even better version of this allows you to "single step" through the
algorithm to watch what's going on . Depending on where the problem
area is, a 10-step and 100-step button might be handy, too.
The point of all this is: there's probably some weird edge-case that you
hadn't considered that the computer is running into. You're not fixing
it because you're not aware of it. Once you see it on screen, you'll
have that "WTF?!" moment, then it will dawn on you why this particular
case is giving you grief. Then you can start to optimize around it.
Good luck!
--
Please take off your pants or I won't read your e-mail.
I will not, no matter how "good" the deal, patronise any business which sends
unsolicited commercial e-mail or that advertises in discussion newsgroups. |
|
|
| Back to top |
|
|
|
| Paul E. Black... |
| Posted: Tue Oct 28, 2008 10:39 pm |
|
|
|
Guest
|
On Sunday 26 October 2008 00:35, Miss Elaine Eos wrote:
Quote: In article
3bc011ab-8923-4c4a-86b7-071c72006e08 at (no spam) e38g2000prn.googlegroups.com>,
Joel Anderson <hohums at (no spam) gmail.com> wrote:
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).
[...]
[... PEB] Have the computer display on the screen what *IT*
thinks it's doing. Too often, a developer convinces himself of what HE
thinks the computer is doing, and wastes a lot of time chasing down
non-problems and looking in wrong-corners. ... [PEB] there's
probably some weird edge-case that you
hadn't considered that the computer is running into. You're not fixing
it because you're not aware of it.
I agree. Often just seeing something like this run, I think of an
improvement.
Here are some things you might try:
Use a better distance estimate for A* (you didn't say what you use).
Summarize distant calculations by pre-computing 16 x 16 blocks. That
is, what is the shortest distance to get from side to side, from top
to bottom, from each corner to opposite sides. That way once you get
to the edge of a surrounding block, you can quickly estimate a lowest
cost to distant points.
Use priority queues instead of partial sort.
If a few of the destinations are popular (e.g., many units try to get
to home base), you can cache best paths to them.
Try iterative deepening A*. It goes through more checks, but avoids
the need to maintain a priority.
Russell and Norvig mention a Simplified Memory-Bounded A*, which "is
optimal if enough memory is available to store the shallowest optimal
path. Otherwise, it returns the best solution that can be reached
with the available memory."
-paul- |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Sat Nov 28, 2009 11:30 pm
|
|