Approximate Cell Decomposition Demo

This program demonstrates 4 different approximate cell decomposition path finding methods. In particular, it demonstrates basic grid decomposition, Quadtree decomposition, hierarchical rectangloid decomposition, and probabilistic cell decomposition. I wrote this program for a 1 semester class, of which it was only a part. Because of this, I wrote much of it under a sever time constraint, so don't expect a whole lot of documentation. The source code is, of course, available (under the LGPL).

You can run it with Java Web Start to try it out. You can also download a zip file containing the cellpath jar files needed to run it. Just unzip it, change into the directory, and run cellpath.jar (java -jar cellpath.jar).

Quick-Start Guide (copied from README)

Open up worlds by using the File menu (worlds/premade has some good wolrds).
Add obstacles by clicking on the "+" sign on the toolbar, then click on the
editor area to add points in the path. When you are done, right-click or click
on the point you started with.
To delete obstacles, click on an obstacle. It should be selected now (there
will be a red out-line around it. Then hit the "-" button in the toolbar.
Move the init. and goal position to free space in the world. Press the mouse
button and hold over one of the dots (init or goal), then drag the mouse to move
it.
Choose a path finding algorithm by selecting it from the drop-down box. It
may take a few seconds, but the path will appear (if one was found) and the
corresponding decomposition will be overlaid over the world.
The "Opacity" slider at the bottom of the editor controls the opacity
(transparency) of the decomposition overlay. At 0, the decomposition is not
visible at all (though the path still is!).
Bump up the resolution by adjusting the "Resolution" slider. Further to the
right indicates smaller resolutions. 1/64 or 1/128 are both good values.
Overlay the adjacency graph on the editor by clicking on the graph button at
the bottom. This will draw a line between 2 cells iff there is an edge in the
adjacency graph between them. The opacity slider controls its opacity as well.
Save your world by hitting the Save item in the menu bar. Save it as a .world
or .txt file.

If you want some worlds to play with, here are a few. I also have a random maze generator. I've made other random world generators as well, but I'll release those later.

I'm not going to go into how these algorithms work, but here are some pictures to demonstrate, if you are getting wary about clicking that Web Start link.

Grid Decomposition

The path found by grid decomposition

The decomposition used to find the path

Quadtree Decomposition

The path found by quadtree decomposition

The path found by grid decomposition

The decomposition used to find the path

Probabilistic Cell Decomposition

The path found by probabilistic cell decomposition

The path found by PCD

The decomposition used to find the path

Hierarchical Rectangloid Decomposition

The path found by Hierarchical Rectangloid decomposition

The path found by HRD

The decomposition used to find the path

Source Code

The actual program itself is made up of several separate projects. The cellpath program itself loads the algorithms as plug-ins, so each plug-in is a separate project. They also all depend on a simple A* implementation I wrote, as well as the JGraphT graphing library. Now, for the source:

All of the implementations only require one interface to be defined in order to be used. Namely, they all have their own Environment interface. These are usually pretty simple. For instance, Probabilistic Cell decomposition's only requires 2 methods, one that returns the size of the world and one that returns true if a point is not contained in any obstacle, and false otherwise. On the other hand, Hierarchical Rectangloid decomposition's environment interface is fairly complex (well, the implementation will be).

The cellpath GUI program uses the java.awt.geom.Area class for the obstacles and I've only provided implementations of the decomposition algorithms environments that use this (found in each implementations gui sub-package). It is not particularly fast, and there is huge rooms for improvement here. However, my project was not to make the quickest point queries, or projection queries, so I did not focus on that. This is also a very slightly out-of-date version of the code. The most current version pushes the path finding out of the Swing event thread, so the GUI is actually usable during the path finding process.

TomSwitzer.com Tom Switzer's Blog