Skip navigation
Help

A* algorithm

warning: Creating default object from empty value in /var/www/vhosts/sayforward.com/subdomains/recorder/httpdocs/modules/taxonomy/taxonomy.pages.inc on line 33.

I recently did a complete rewrite of my graph-based A* pathfinder example because I received a lot of questions on how to implement path-finding using the new ds library. So here is the updated version which works with ds 1.32:

I’m transforming the point cloud with delaunay triangulation into a graph structure. Then the system computes and draws the shortest path between two selected points.

Compile instructions

Running and examining the example is really easy:

  1. Use the automated installer to install haXe from http://haxe.org/download.
  2. Download the latest haXe nightly build and overwrite the existing ‘haxe.exe’ and ‘std’ folder with the downloaded version.
  3. Install the polygonal library by opening the command prompt and typing:
    haxelib install polygonal.

Sources should now be in {haxe_install_dir}/lib/polygonal/1,18/src/impl/sandbox/ds/astar, where {haxe_install_dir} is usually C:/Motion-Twin/haxe on Win7.
The demo can be compiled with:
cd C:\Motion-Twin\haxe\lib\polygonal\1,18\build
haxe.exe compile-ds-examples.hxml

Extending the Graph class

You have basically two options to extend the functionality of the Graph object: by composition or inheritance. While I highly recommend to use composition whenever possible, I’ve also included a version using inheritance – just so you see the difference.

The composition version looks like this:
astar using composition
The Graph object manages GraphNode objects, and each GraphNode holds a Waypoint object, which defines the world position of the waypoint as well as intermediate data used by the A* algorithm. Notice that GraphNode and Waypoint are cross-referencing each other as a Waypoint object has to query the graph for adjacent nodes. As a result, you have a clean separation between the data structure (Graph, GraphNode) and the algorithm (AStar, Waypoint) and don’t need object casting, which is good news because casting is a rather slow operation.

Now let’s look at the version using inheritance:
astar using inheritance
Here, Waypoint directly subclasses GraphNode. Since the Graph is defined to work with GraphNode objects, we need a lot of (unsafe) down-casts to access the Waypoint class. Furthermore, the use of haxe.rtti.Generic will be very restricted or even impossible (implementing this marker interface generates unique classes for each type to avoiding dynamic).

3
Your rating: None Average: 3 (1 vote)

Well I finally got Ogre to compile. Bugger knows how I’m going to graft Openframeworks libraries into it. I only really need sound and the VideoGrabber, but those are still tall orders.

If you want to play with Ogre on a PC you’ll need the following:

Visual Studio 9. Trying to get it to work with Code Blocks is more trouble than it’s worth, especially as it breaks Openframeworks when you get the bare minimum working. Plus VS9 is pretty damn good. I’m amazed that Microsoft made it.
The Ogre SDK
DirectX Runtime

Then you’ll want to read the following:

Installing the Ogre SDK
Setting up an application. No the Ogre Application Wizard doesn’t work on VS9. This means we have to do some twiddling with project settings to get it to work. But despite this being a pain, it teaches you how to set up projects properly and will help you in the long run.
My thread in the Ogre Forum about trying to get VC9 to compile Ogre. I didn’t quite read the instructions in the previous link thoroughly, but those instructions also assumed some knowledge I didn’t have. Most of the difficulty of getting Ogre to compile is down to correct project settings and correct file placement. So you have to use your initiative a little to figure it out. Now I’m at the following stage:

Ogre Tutorials

I’m going to settle in to this stuff now to put off the nightmare that combining Ogre and Openframeworks will be.

Bruce Sterling on the future of interaction design
Magic Pen
Artificial Stupidity
Fruit Mystery game
Cat with Bow Golf game
Floating Head
The Control Master (a Run Wrake film)
Metal Gear Solid 4 game play demo

C++ optimisation strategies
Processing for Javascript

As a side note I got a new phone recently. So I downloaded the latest Mobile Processing and spent one Sunday writing a new and more clever game of Snake vs the Computer for it. It uses the new A* algorithm I built and shows the Snake’s thoughts about which path to take ahead of it.

Snake AI 2

0
Your rating: None