JavaFX A* path finding

May 19, 2010 jfxworks 2 comments

Recently I’ve implemented the A* path finding algorithm in Java. And because it’s a quite popular path finding algorithm used for gaming, I thought it might be interesting to the JFX folks out there too.

This article is about the few generic A* classes I wrote, allowing people to build on top of them for their own purposes. By no means do I pretend the implementation is the best possible. It’s a basic and straightforward implementation. Which, I’m pretty sure, can be improved in many ways.

For a description of the algorithm I’m referring to the link to Wikipedia on top of this page.

Example

In a few lines you can start searching for a safe path and avoid all these weird characters who obviously never heard about chainsaws being dangerous !

def       grid = CarthesianGrid { width: 100
                                 height: 100
                                 cellFactoryFunction: CarthesianGrid.createCell };
def          a = grid.getCellAt(4, 13);
def          b = grid.getCellAt(70,87);
def pathFinder = PathFinder { grid: grid };
def       path = pathFinder.find(a, b);

The first statement creates a Cartesian grid of 100 columns and 100 rows. Cartesian here means each cell has the same size and the distance between cells is identical (ie equidistant).

The cellFactoryFunction is actually a function type. A closure really. It is implemented this way to allow the implementor to provide the way new cells are created. The grid just calls the function whenever it needs a new GridCell instance.

The second- and third statements ask for the the GridCell objects at the x- and y locations. Mind you, this is all lazy loading. Cells are only created when they’re being asked for. Otherwise large grids might end up using quite a lot of memory for nothing. We’re just interested in the cells of the path. Or those in the vicinity.

The fourth statement links the A* algorithm to the grid. Telling it to use this grid to find its way.

And finally, the fifth statement searches for a path from cell a to cell b. The result of the search is a sequence of cells starting with a and ending with b.

Visual test

I’ve provided a small program to visually demonstrate the thing at work. The really impatient can now skip to the “Running & Source code” section to see the code at work.

Grids

In this implementation the plane to search the path in is described by a grid of cells ordered in rows and columns. It is represented by the class astar.Grid. It is an abstract, mixin, class containing the basic coding for grids. The aim is to have your grid implementation extending from this class. Luckily for us JavaFX is blessed with multiple-inheritance. A mixin class can be extended by any class. You can safely use your existing code without any inheritance trickery.

And because there is a 99% probability you will use a Cartesian grid for your game, I have included it too.

A Grid is has width (columns) and height (rows). It can be asked for a particular cell at (x,y) or (column,row) with 0-based indexes. It provides two abstract functions:

getDistance( GridCell, GridCell ): Double

This function is meant to calculate the real distance between two cells. For the A* algorithm this function is only used to compute the distance between adjacent cells. Just how far is the next cell ? CarthesianGrid implements this function using the inevitable Pythagoras Theorem. In our context, for finding a path between cells a and b this comes down to:

Where Xa and Ya represent the column- and row indexes of cell a. And likewise for cell b. The equation results in the distance d.

getHeuristincDistance( GridCell, GridCell ): Double

This function does mainly the same as getDistance but it calculates an estimate of the distance between two cells. For the A* algorithm this function is used to get an estimate of the distance between a cell and the final cell the path should lead to. Usually the Pythagoras theorem is applied here too.

There is one difference though: The distance is multiplied by a modifier to make the distance slightly longer. I’m not exactly the A* guru, but much literature mentions A* will find an optimal path providing the heuristic distance is longer than the real distance. At least, that what I make of it…

What I also noticed is that playing with that modifier introduces some inefficiency of the path. Being inefficient is important: Instead of straight and efficient paths – which are obviously computed – you can end up with a path only a snail would follow. It brings some illusion of live and individual initiative in the game. Just by tweaking one variable.

Factory method

An other blessing of JavaFX are the function types and closures. This means you will finally be able to implement the factory method pattern as a single function. The variable cellFactoryFunction accepts a function-typed value that is a function with two integer arguments and returning an instance of GridCell. The arguments are the x- and y coordinates of the required cell. This function will only be called when a new instance of GridCell is required. For our CarthesianGridCell this is implemented as

public function createCell(x: Integer, y: Integer): GridCell {</pre>
  return CarthesianGridCell {x: x, y: y };
}

Assign createCell to the cellFactoryFunction variable of a Grid will allow it to execute that function without knowing where it comes from or the class it is part of.

Cells

Each Grid is composed of a raster of Cells. The base is provided by the abstract, mixin, class GridCell. Once again, because it is a mixin class, you can have your existing code extend from it without much hassle.

Each cell is characterized by

x,y The coordinates (x,y) or (column,row).

grid The Grid object this GridCell is part of.

closed The A* lingo for “already visited”. Already processed cells are to be ignored by the algorithm.

previousCell This is a reference to the previous cell in the path currently being computed. Once the algorithm completed, simply follow the backreferences from the final cell back to the starting cell. That’s the path to follow, in reversed order.

g The agreed A* term for the real distance of the cell back to the starting cell. Following the path that is.

h The agreed A* term for the estimated distance (heuristic) from the cell to the target cell.

f The agreed A* term for the addition of g and h. (The final path will be the succession of cells with the lowest f values.)

cost A personal modification. It’s a cost to add to f for including the cell into the path. Open space has a cost of zero. While obstacles have a cost of 10,000. (Running into an obstacle might be very costly indeed) As a result the path will curl around obstacles.

newAttr That’s a typo in the screenshot I just noticed.

Fiddling with the cost of cells is also a funny thing to do. Instead of hard obstacles you might think about sand and water. You’d rather walk on sand than on water. But if you really have to cross the river, use the depth of the water as the cost. A* will find you the safest path across. Again, bringing some illusion of independent initiative in the game. Making it somewhat less efficient will give the illusion of less intelligent opponents too.

A subclass of GridCell is required to provide the implementation of one function

getNeighbors(): GridCell[]

Because not all grid systems have 3, 5 or 8 neighboring cells for each cell. There are hexagonal grids, cylindric, etc… CarthesianGridCell implements it the basic way: 3 neighbors for the corner cells, 5 for those on the borders and 8 for the remainder.

Path finder

Finally the A* algorithm is implemented into the PathFinder class.

To find a path create a new instance of this class, assign a grid and call the findPath function. This function will come back with a sequence of GridCell representing the path or will throw an exception when no path could be found. The latter might take quite a while to come, depending on the size of your grid. A* will throw this exception when it ran out of unvisited cells.

Testing

In order to encourage a little TDD here, I’ve included some tests. This way you’ll notice it’s really handy to have tests at hand when tweaking code. To test the code run the class MainTestSuite.

IDE-integrated JavaFX test runners are a bit basic these days. So it’s back to the good ‘ol JUnit we used to make back in … Is it that long ago already ?

Running

The source code is provided as a Netbeans project. Unzip the archive and run the VisualTest class to play with the code. If you’re not interested in downloading the whole lot of Netbeans, download and install the JavaFX SDK and proceed as follows:

Open a command prompt window.
Make sure the javafx executable is in your path.
Unzip the source code archive to a directory of your choice.
Change to chosen-directory/AStar/dist.
Run the command javafx -jar AStar.jar.

It will start by setting obstacles at random. From there, click on the starting position and on the end position. The path between the two positions will appear. Depending on the complexity of the path it might take a few seconds. (And I’m pretty sure it can be made faster.) Click again to generate a new set of obstacles. Click a start- and end position. And so on …

Granted, it’s not exactly the prettiest demo I’ve ever written, but it serves its purpose: It finds its way. And it does so quickly !

Source code

The source code can be downloaded here

Click to download the source code

Improvements

No doubt there’s room for improvement. Even while I’m writing this I do realize I could have done it otherwise, better.

There is no need for PathFinder to have a separate Grid instance. For as long as the a and b GridCell objects belong to the same grid, one findPath function is enough. But then I might have included this into the Grid class. Eliminating PathFinder alltogether. Etc …

I’ve avoided to use Java collections to keep the dependency with Java to a minimum. Sequences were used instead. Maybe this incurs some performance cost.

Cost has been implemented a naive way. Cost might be dependent on whether it applies when entering- or leaving the cell. Dependent on going up- or downslope. Etc..

The cost might have been implemented as a function closure too. Leaving it up to you to decide how expensive things are.

Grids are not resettable. Once A* ran, all the visited cells are left as they were. The grid can not be reused. On the other hand, I would not recommend this for large grids though. If your grid is large you’ll increase its size with every search you do. A* only needs the cells it visits. (The only good memory is the one you don’t use !)

A* gives a path from one cell to the other. Even if the path would be a straight line from a to b. Maybe that’s what you want. But maybe you’re using A* to compute a curve representing the path. In that case you’ll probably want to reduce the curve to a minimum number of points. The Douglas-Peucker algorithm might be helpful. The only Java implementation I’m aware of is the one of JTS.

References

A* algorithm at Wikipedia. I used the pseudo code as the base for the implementation. No doubt there are many variants to be found out there. Mind you, searching Google with “A*” won’t bring you very far. Usually you’ll need to look for “a-star” or “astar”.

The Douglas-Peucker algorithm at Wikipedia. I don’t know the algorithm that well but it did wonders in a private experiment I did to find navigable paths for boats using using real-world data.

The Pythagoras theorem at Wikipedia. An absolute when dealing with distance calculations in Cartesian math.

JTS (Java Topology Suite) homepage. Vividsolutions maintains this mean suite able to solve all your geometry problems. As long as it’s 2D Cartesian math, that is. Hopefully we’ll see it go 3D some day.

Netbeans homepage. The IDE used for this article.

JavaFX homepage. The JavaFX headquarters.

JFXWorks homepage. The homepage of the bunch of JavaFX geeks I’m belonging to. This article is published there.

java.artisan @ gmail.com. Your humble servant’s email address. For your remarks, questions, suggestions, rants, taunts and spam.

I hope you had a happy lecture !

Jan Goyvaerts @ JFXWorks

Categories: Uncategorized

Data Binding With JavaFX Composer

May 17, 2010 jfxworks Leave a comment

Data Binding With JavaFX Composer

http://netbeans.org/kb/docs/javafx/data-binding.html

Categories: Uncategorized

JavaFX Tutorial: Getting Started with JavaFX Composer

May 12, 2010 jfxworks Leave a comment

http://netbeans.org/kb/docs/javafx/quickstart-javafxcomp.html

Categories: Uncategorized

Netbeans plugin download for slow networks

April 23, 2010 jfxworks Leave a comment

Obviously many people out there are taking Netbeans 6.9 beta release for a spin. Downloading a plugin won’t work any more without network timeouts. Alas, the timeout rolls back the already downloaded plugins too.

At first I thought this release had proxy issues because I could download the plugin with a browser. But once in while something came through. Fortunately there something you can do: Modify the network timeout settings. In the file ${netbeans.home}/etc/netbeans.conf prepend the property netbeans_default_options with -J-Dsun.net.client.defaultConnectTimeout=60000 -J-Dsun.net.client.defaultReadTimeout=60000. See the before/after examples underneath.

Now Netbeans seems to be downloading the plugins. Painfully slow, but it looks like it is working. 🙂

Before

# ${HOME} will be replaced by JVM user.home system property
netbeans_default_userdir="${HOME}/.netbeans/6.9beta"

# Options used by NetBeans launcher by default, can be overridden by explicit
# command line switches:
netbeans_default_options="-J-client -J-Xss2m -J-Xms32m -J-XX:PermSize=32m -J-XX:MaxPermSize=200m -J-Dnetbeans.logger.console=true -J-ea -J-Dapple.laf.useScreenMenuBar=true -J-Dsun.java2d.noddraw=true"
# Note that a default -Xmx is selected for you automatically.
# You can find this value in var/log/messages.log file in your userdir.
# The automatically selected value can be overridden by specifying -J-Xmx here
# or on the command line.

# If you specify the heap size (-Xmx) explicitely, you may also want to enable
# Concurrent Mark & Sweep garbage collector. In such case add the following
# options to the netbeans_default_options:
# -J-XX:+UseConcMarkSweepGC -J-XX:+CMSClassUnloadingEnabled -J-XX:+CMSPermGenSweepingEnabled
# (see http://wiki.netbeans.org/wiki/view/FaqGCPauses)

# Default location of JDK, can be overridden by using –jdkhome <dir>:
netbeans_jdkhome="/u01/app/jdk"

# Additional module clusters, using ${path.separator} (‘;’ on Windows or ‘:’ on Unix):
#netbeans_extraclusters="/absolute/path/to/cluster1:/absolute/path/to/cluster2"

# If you have some problems with detect of proxy settings, you may want to enable
# detect the proxy settings provided by JDK5 or higher.
# In such case add -J-Djava.net.useSystemProxies=true to the netbeans_default_options.

After

# ${HOME} will be replaced by JVM user.home system property
netbeans_default_userdir="${HOME}/.netbeans/6.9beta"

# Options used by NetBeans launcher by default, can be overridden by explicit
# command line switches:
netbeans_default_options="-J-Dsun.net.client.defaultConnectTimeout=60000 -J-Dsun.net.client.defaultReadTimeout=60000 -J-client -J-Xss2m -J-Xms32m -J-XX:PermSize=32m -J-XX:MaxPermSize=200m -J-Dnetbeans.logger.console=true -J-ea -J-Dapple.laf.useScreenMenuBar=true -J-Dsun.java2d.noddraw=true"
# Note that a default -Xmx is selected for you automatically.
# You can find this value in var/log/messages.log file in your userdir.
# The automatically selected value can be overridden by specifying -J-Xmx here
# or on the command line.

# If you specify the heap size (-Xmx) explicitely, you may also want to enable
# Concurrent Mark & Sweep garbage collector. In such case add the following
# options to the netbeans_default_options:
# -J-XX:+UseConcMarkSweepGC -J-XX:+CMSClassUnloadingEnabled -J-XX:+CMSPermGenSweepingEnabled
# (see http://wiki.netbeans.org/wiki/view/FaqGCPauses)

# Default location of JDK, can be overridden by using –jdkhome <dir>:
netbeans_jdkhome="/u01/app/jdk"

# Additional module clusters, using ${path.separator} (‘;’ on Windows or ‘:’ on Unix):
#netbeans_extraclusters="/absolute/path/to/cluster1:/absolute/path/to/cluster2"