|
|
By Patrick Lester ( Updated April 11, 2003)
This
article is a sidebar for my main article, “A* Pathfinding for Beginners.”
You should read that article, or understand A* thoroughly, before proceeding
with this article.
One of the slowest parts of the
A* pathfinding algorithm is finding the square or node on the open list with the
lowest F score. Depending on the size of your map, you could have dozens,
hundreds or even thousands of nodes to search through at any given time when you
are using A*. Needless to say, repeatedly searching through a list this big can
slow things down a lot. The amount of time it takes to do this, however, can be
greatly influenced by the way you choose to save your open list items.
Sorted
and Unsorted Open Lists: A Simple Approach
A really simple way to save the
open list is to save each item as needed, and go through the whole list each
time you need to grab something off of the list, looking for the lowest cost
item. This provides fast insertions into the list, but the slowest possible
removal time, since you need to check each item on the list to make sure you
have the lowest F cost item.
You can generally improve your
performance by keeping your list sorted. This takes a little more up-front work,
however, because every time you add an item to the list, you need to insert it
in the proper place. Removing items, however, is fast. You just grab the first
item off of the list, which will have the lowest possible F cost.
There are lots of ways to keep
your data sorted (selection sorts, bubble sorts, quick sorts, etc.) and you can
find articles on these on the internet by simply searching on those terms in
your favorite search engine. But we can at least touch on some ideas here. A
really simple approach would be to start at the beginning of your list every
time you need to add a new item, and then successively compare the F cost of the
current node you are adding to the list with each item already on the list. Once
you find a node on the open list with an equal or higher F cost, you could
insert the new item before that item on the list. Depending on the computer
language you are using, linked lists using classes or structs (types in Blitz) are probably a
good method here.
This approach could be improved
by keeping track of the average F cost of items already on your list, and using
that to decide whether to start at the beginning of the list (as described
above) or to start at the end of the list and work toward the front of the list.
In general, insertions of new items with lower than average F costs would start
at the beginning of the list and work forwards, while insertions of new items
with higher than average F costs would start at the end and work backwards. This
approach will cut your search time in half.
A more complicated, but faster
approach could be to take this idea to the next level and use a quick sort,
which basically starts by comparing the F cost of the new item to the item at
the middle of the list. If the new item has a lower F cost, you would then
compare it to the item 1/4 of the way through the list, if lower than that you
would compare it to the one 1/8 of the way, and so on, successively dividing
your list in half and comparing the new item to the current items on the list
until it finds its proper spot. This is a pretty generic description, so you
will want to look up quick sorting on the internet to find out more about how it
works. Suffice it to say, this will generally be quicker than any of the
techniques described so far.
Binary
Heaps
Binary heaps are very similar to
the quick sort method just described, and they are often used by people who are
serious about keeping their A* functions as fast as possible. In my experience,
using a binary heap will speed up your pathfinding by 2-3 times on average, and
more on larger maps with lots of nodes (say a map 100 x 100 nodes or more). Fair
warning, however -- binary heaps are a bit tricky, and may not be worth the
headache unless you are using a map with lots of nodes, where speed gains are
crucial.
The rest of this article is
devoted to explaining binary heaps and their use in A*. There is also a Further
Reading section at the end of the article which will provide you additional
perspectives, if mine leaves you totally mystified.
Still interested? Okay, here goes
...
In a sorted list, every item on
the list is in its proper order, lowest-to-highest or highest-to-lowest. This is
helpful, but is actually more than we really need. We don’t actually care if
item number 127 is lower than number 128 on the list. All we really want is the
lowest F cost item to be easily accessible at the top of the list. The rest of
the list can be a jumble, for all we care. Keeping the rest of the list properly
sorted is just extra unneeded work until, of course, we need the next lowest F
cost item.
Basically, what we really need is
something called a “heap” or, more specifically, a binary heap. A binary
heap is bunch of items where either the lowest or highest value item (depending
on what you want) is at the top of the heap. Since we are looking for the lowest
F cost item, we will put that at the top of our heap. This item has two
children, each of which has an F cost equal to, or a little higher than it, and
each of these children has two children of its own that has an F cost that is
equal to, or a little higher than it ... and so on. Here is what one heap could
look like:
Notice that the lowest item on
the list (10) is at the top and the second lowest (20) is one of its children.
After that, however, all bets are off. In this particular binary heap, the third
lowest item on the list is 24, which is two steps down from the top, and lower
than 30, which is only one step from the top on the left side. Simply put, it
doesn’t matter what the value of other items are in the heap, each individual
item in the heap needs only to be equal to or higher than its parent, and equal
to or lower than both of its children. Those conditions are met here, so this is
a valid binary heap.
All right, you are probably
thinking, this is modestly interesting, but how do you actually use it in any
practical sense? Well, one of the interesting things about a heap is that you
can save it in a simple, one dimensional array.
In this array, the item at the
top of the heap would be in the first position of the array (position 1, not
position zero, which is possible in an array). Its two children would be in
positions 2 and 3. The four children of these two items would be in positions
4-7.
In general, the two children of
any item in the heap can be found in the array by multiplying the item’s
current position in the array by two (to find the first child) and by two and
adding one (to find the second child). So, for example, the two children of the
third item in our heap (with a value of 20), can be found in positions 2*3 = 6,
and 2*3 +1 = 7 of the array. In this case, the numbers in those positions are 30
and 24, respectively, which makes sense when you look at the heap.
You don’t really need to know
this, but it is worth noting that there are no holes in this heap. With 7 items,
it completely fills out every row of a three-level heap. This isn’t necessary,
however. For our heap to be valid, we only need to fill out every row above the
bottom level. We can have any number of items on the bottom level itself,
however, and new items are added from left to right on that level. The
method described in this article does that, so you don’t really need to worry
about it.
Adding
Items to the Heap
We will need to consider a few
more things before we can actually use a heap for pathfinding purposes, but for
now let’s just learn the basics of using a binary heap in general. I’d
suggest skimming through this part to understand the basics. I will give you a
formula that takes care of all of this for you a little later on in the article,
but it is still important to understand what is going on.
In general, to add an item to the
heap, we place it at the very end of the array. We then compare it to its
parent, which is at location (items in heap)/2, rounding all fractions down. If
the new item’s F score is lower, we swap these two items. We then compare the
new item with its new parent, which is at (current position in heap)/2, rounding
fractions down. If its F value is lower, we swap again. We repeat this process
until the item is not lower than its parent, or until the item has bubbled all
the way to the top, which is in position #1 in the array.
Let’s say we were adding an
item with an F score of 17 to our existing heap. We currently have 7 items in
the heap, so the new item would be placed in position number 8. This is what the
heap looks like. The new item is underlined.
10 30
20 34 38 30 24 17
We would then compare this item
it to its parent, which is in position 8/2 = position 4. The F value of the item
currently in position 4 is 34. Since 17 is lower than 34, we swap them. Now our
heap looks like this:
10 30
20 17 38 30 24 34
Then we compare it with its new
parent. Since we are in position 4 we compare it to the item in position number
4/2 = 2. That item has an F score of 30. Since 17 is lower than 30, we swap
them, and now our heap looks like this:
10 17
20 30 38 30 24 34
We then compare it to its new
parent. Since we are now in position #2, we compare it with the item in position
number 2/2 = 1, which is the top of the heap. In this case, 17 is not lower than
10, so we stop and leave the heap the way it is.
Removing
Items from the Heap
Removing items from the heap
involves a similar process, but sort of in reverse. First, we remove the item in
slot #1, which is now empty. Then we take the last item in the heap, and move it
up to slot #1. In our heap above, this is what we would end up with. The
previously last item in the heap is underlined.
34
17 20 30 38 30 24
Next we compare the item to each
of its two children, which are at locations (current position * 2) and
(current position * 2 + 1). If it has a lower F score than both of its
two children, it stays where it is. If not, we swap it with the lower of the two
children. So, in this case, the two children of the item in slot #1 are in
position 1*2 = 2 and 1*2+1 = 3. It turns out that 34 is not lower than both
children, so we swap it with the lower of the two, which is 17. This is what we
end up with:
17 34
20 30 38 30 24
Next we compare the item with its
two new children, which are in positions 2*2 = 4, and 2*2+1 = 5. It turns out
that it is not lower than both of its children, so we swap it with the lower of
the two children (which is 30 in slot 4). Now we have this:
17 30
20 34 38 30 24
Finally we compare the item with
its new children. As usual, these children would be in positions 4*2 = 8, and
4*2 +1 = 9. But there aren’t any children in those positions because the list
isn’t that big. We have reached the bottom level of the heap, so we stop.
Why
is a Binary Heap so Fast?
Now that you know the basics of
insertion and removal from a heap, you should begin to see why it is so much
faster than, say, an insertion sort. Imagine that you have an open list with
1000 nodes on it, which is not impossible on a sizable map with a lot of nodes
(remember, a map just 100 x 100 nodes has 10,000 nodes on it). If you were to do
a simple insertion sort, started at the beginning of the list, and proceeded
until you found the proper spot to insert the new item, you would on average
need to make 500 comparisons before inserting it in the right place.
Using a binary heap, you would
only need to make an average of 1-3 comparisons to insert it in the right spot,
starting from the bottom. You would also need to make an average of about 9
comparisons to remove an item from the open list and reorder the heap
appropriately. In A*, you generally remove one node on every pass (the lowest F
cost item), and usually add anywhere from 0 to 5 new nodes (using the 2D approach
described in the main article). This can total up to about 1% of the time it
takes to do an insertion sort on the same number of nodes. The difference
becomes geometrically more important the larger (i.e. more nodes on) your map.
Smaller maps, by comparison, gain less and less of an advantage, which is why
binary heaps become progressively less worth the trouble the smaller your map,
and the fewer nodes you use.
By the way, just because you are
using a binary heap doesn’t mean that your pathfinding algorithm will be 100
times faster (or whatever). There is some overhead involved, which is described
below. Plus, there is more to the A* algorithm than simply sorting the open
list. Nevertheless, in my experience using a binary heap will still make your
pathfinding algorithm 2-3 times faster in most cases, and even more on longer
paths.
Creating
the Open
List Array
Now that we know what a heap is,
how do we use it? The first thing we need to do is dimension our one-dimensional
array properly. To do this, first we need to figure out how big it can possibly
get. In general, the list can’t get any bigger than the total number of nodes
on our map (assuming a worst-case scenario where we search the whole map for a
path). In a square, two-dimensional map like the one I described in the main
pathfinding article, we won’t have more than mapWidth x mapHeight nodes. So
that is how big our 1 dimensional array should be. For the sake of this example,
we will call this array openList().
Using
Pointers
Now that we have a
one-dimensional heap/array that is the right size, we are almost ready to start
using it for pathfinding purposes. Before we go any further, however, let’s
look at our original heap again, before we added or subtracted anything.
Currently, it is just a list of F
values, and they are arranged properly. But we are missing an important element.
Sure, we have a bunch of F values arranged in binary heap order, but we have no
clue what squares on our map they are associated with. Basically, what we have
right now just tells us that 10 is the lowest F score in the heap. But which square
on our pathfinding map does that refer to?
To fix this problem, we need to
change the values of the items in the array. Instead of storing the F value in
the array, we need to store a unique identifying number that tells us what
square it is referring to. My approach is to create a unique ID associated with
each new item added to the heap called squaresChecked.
Every time we add an item to the open list, we increase squaresChecked by one and use this as the unique ID for the new item
added to the open list. The first item added to open list will item #1, the
second item is item #2, and so on.
Finally, we need to save the
actual F cost of that square in a separate one dimensional array, which I call Fcost().
As with the openList array, we will dimension it to the size (mapWidth x
mapHeight). We will also store the x and y coordinates of the node on the map in
similar one-dimensional arrays, which I will call openX()
and openY(). Visually, this looks like
the following illustration:
While this looks a little more
complicated, it is the same heap we used in the earlier illustration. We just
have a lot more information now.
Item #5, with the lowest Fcost of
10, is still at the top of the heap, and in the first column of our one
dimensional array. But now we are storing its unique ID number of 5, rather than
its F cost in the heap. In other words, openList(1) = 5. This unique number is then used to look up the
item’s Fcost, and x and y locations on the map. The Fcost of this item is
Fcost(5) = 10, its x location on the map is openX(5) = 12, and its y location on
the map is openY(5) = 22.
This top item in the heap has two
children, items number 2 and 6, which have Fcosts of 30 and 20 respectively and
are in slots 2 and 3 in openList(),
and so on. Basically, we have exactly the same heap we had earlier, just with a
lot more information about where the item is on the map, what its Fcost is,
etc.
Adding
New Items to the Heap (Part 2)
Okay, so let’s actually apply
this technique to sorting our open list in a way that is usable in an A*
pathfinding algorithm. In general, we use exactly the same techniques that were
described earlier.
The first item we add to the open
list, which is generally the starting node, is assigned a unique ID number,
which is 1, and then put in position #1 in the open list. In other words,
openList(1) = 1. We also keep track of the number of items on our open list,
which is also 1 for now. We record this number in a variable called numberOfOpenListItems.
As we add new nodes to the open
list, first we figure out their G, H and F scores, as described in the main A*
article. Then we add them to the binary heap as described earlier in this
article.
First we assign the new item a unique ID#, which is the purpose of the squaresChecked variable. We basically add 1 to this every time we add a new node to the open list, and we assign this number to the new node. We then add 1 to numberOfOpenListItems. Then we add it to the bottom of the open list. Basically, all of this translates into the following:
squaresChecked = squaresChecked +1 numberOfOpenListItems = numberOfOpenListItems+1 openList(numberOfOpenListItems) = squaresChecked
Then
we make successive comparisons with its parent until it rises to its proper spot
in the heap. Here is some code that will do that
m = numberOfOpenListItems
While m <> 1 ;While item hasn't bubbled to the top (m=1)
;Check if child is <= parent. If so, swap them.
If Fcost(openList(m)) <= Fcost(openList(m/2)) Then
temp = openList(m/2)
openList(m/2) = openList(m)
openList(m) = temp
m = m/2
Else
Exit ;exit the while/wend loop
End If
Wend
Deleting
Items from the Heap (Part 2)
Of course, we don’t just build
a heap, we also need to delete items from the heap when we don’t need them
anymore. Specifically, in A* pathfinding we need to delete the lowest F cost
item from the top of the heap after we have checked it and switched it to the
closed list.
As was described earlier in the
article, you start by moving the last
item in the heap over to first position, and then reduce the number of items in
the list by one. In pseudocode, this would be: Next we need to do successive
comparisons between this value and each of its two children. If it has a higher
F score than one or both of the two children, we swap it with the lower of the
two children. Then we compare the item with its two new children (since
it is lower in the heap). If it has a higher F score than one or both of its two
children, we swap it with the lower of the two. We repeat this process until the
item has found its proper place in the heap, which may end up toward the bottom,
but not necessarily. Here is what the pseudocode would look like:
Please note the bolding (in red) of u and v in two lines of the code. On the
second line, you want to use v, not u, which may not be immediately obvious.
This ensures that you end up swapping with the lower of the two children.
Failing to do that will give you an invalid heap, and screw up your pathfinding
completely. Resorting
an Existing Open List Item As is described in the main
article, occasionally you will find that the F score of an existing open
list item can change. When that happens, you don’t
need to take the item out of the list and start all over. Simply start in its
current location, and compare it to its parent using its new (lower) F score. If
its F score is low enough to warrant a swap with that parent, then you need to
do so (or you will have an invalid heap, and everything will break down). In
general, you use the same code described in the “Adding an Item to the Heap”
section of this article, with the following additional consideration: Unfortunately, because your data
is in a giant, seemingly unordered heap, you need to go through the whole heap
to find the existing open list item. Basically you will be looking for the
square with the correct x and y coordinates, as indicated by openX(openList())
and openY(openList()). After you find it, however, you can proceed normally,
making the necessary comparisons and swaps starting from that point in the heap. Final
Notes Okay, I am hoping that if you are
still reading at this point, you aren’t totally confused. If you aren’t
intimidated, and want to code up a binary heap for your own pathfinding
algorithm, then this is what I would suggest. First, forget about binary heaps
for a while. Focus first on getting your A* pathfinding algorithm working
correctly and bug free using a simpler sorting method. You don’t really need
it to work fast at first, you just need it to work. Second, before you add a binary
heap to the code, try coding a stand alone binary heap function that does what
you want, adding and subtracting items from the heap in an appropriate way. Make
sure you write the program so you can see what it is doing at each step in the
process, perhaps printing the results to the screen as you go. You should also
include some escape key code in the program that allows you to break out of the
whole thing if necessary. It is very easy to get trapped in an endless loop if
you don’t write a binary heap correctly. Once you are confident that you
have both programs working smoothly, save working backup copies of both, and
then start working on putting the two together. Unless you are much smarter than
me, you will probably have problems at first. Tell tale signs are error messages
and/or seeing pathfinding critters bug out in all sorts of weird directions.
Eventually, however, you will get it all working. Further
Reading As always, there are lots of
other good articles out there on the web that describe this topic. Here are some
to get you started. The first one explains things graphically. The second shows
how to implement binary heaps using a simple array (if my explanation was
baffling). The third discusses the use of heaps in pathfinding, generally. Finally, you might want to
consider looking at my pathfinding code, which can be found here. It
mirrors the pseudocode in this article, is heavily commented, and is written in
both C++ and Blitz, a Basic language that is easier to understand than most. All you coders who don't use C++ should find the Basic version easy to understand. Well, that’s it. I welcome
comments on this (admittedly) complex topic, and I can be reached at:
Until then, as always, good luck
openList(1) = openList(numberOfOpenListItems)
numberOfOpenListItems = numberOfOpenListItems - 1
v = 1
;Repeat the following until the item sinks to its proper spot in the binary heap.
Repeat
u = v
If 2*u+1 <= numberOfOpenListItems ;if both children exist
;Select the lowest of the two children.
If Fcost(openList(u)) >= Fcost(openList(2*u))then v = 2*u ;SEE NOTE BELOW
If Fcost(openList(v)) >= Fcost(openList(2*u+1))then v = 2*u+1 ;SEE NOTE BELOW
Else If 2*u <= numberOfOpenListItems ;if only child #1 exists
;Check if the F cost is greater than the child
If Fcost(openList(u)) >= Fcost(openList(2*u))then v = 2*u
End If
If u <> v then ; If parent's F > one or both of its children, swap them
temp = openList(u)
openList(u) = openList(v)
openList(v) = temp
Else
Exit ;if item <= both children, exit repeat/forever loop
End if
Forever ;Repeat forever
