HTML and CSS Reference
In-Depth Information
while
while the open list is not empty
current node = node from open list with
with lowest cost
iif current node == goal then
path complete
else
else
move current node to the closed list
examine each node adjacent to the current node
for
iif node is not on the open list
and node is not on the closed list
and node is not an obstacle
then
move node to open list and calculate cost of entire path
}
Nodes can contain obstacles (like our blue walls) or other terrain, such as water or grass. For
our purposes, the blue tiles can never be passed, but we will add in a grass tile in later ex-
amples that, while not easily passable, is not impassable like the blue tiles. We are not going
to use the available chapter space to create our own version of A* in JavaScript. Rather, we
are going to use a version created by Brian Grinstead .
NOTE
Brian's A* algorithm in JavaScript can be found at this site .
We will be using both the graph.js and the astar.js files that Brian created and has supplied
for download at his site. The one caveat to using an algorithm that we did not create is that
we will need to make some minor modifications to our display code. Brian's code expects a
tile map made up of columns of rows, while our tile map is made up of rows of columns. For
example purposes, you can treat one of our tile maps from Chapter 4 as being turned on its
side if it's to be used with Brian's code. (That is, we simply swap the x and y components.)
However, it is easy to compensate for this. Let's get into the first example, and then we can
describe what we mean and how the JavaScript and Canvas code is affected.
You will need to have downloaded the example files for this chapter from the topic's website
to use the use the first example. We have provided a new, very simple tile sheet called
tiles.png , as well as the astar.js and graph.js files from Brian Grinstead's algorithm library.
Figure 8-9 shows the tiles.png tile sheet that we will use as the source graphic material for the
A* examples throughout the rest of this section.
Search WWH ::

Custom Search