Home > Uncategorized > JavaFX A* path finding

JavaFX A* path finding

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”.
  • 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.
  • 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

Advertisements
Categories: Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: