A* pathfinding with ds

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 an updated demo that works with ds 1.32:

Interactive demo: A* pathfinding with ds

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.
  4. 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 then 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:
A* 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:
A* 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).

22 Comments

  1. Pretty cool implementation.
    OTOH, after adding 21+ waypoints nothing is displayed anymore, everything re-appears when I hit the space bar.

  2. Yordan Yanakiev

    Thank you so much.
    You and your team really rox !

  3. Yordan Yanakiev

    anyway where is the source separate from haxe ?

    1. sorry, no AS3 version this time – but it’s very easy to port since syntax is almost identical.

  4. Hi,

    completely unrelated but: what tool are you using to draw your UML diagrams? They look cool.

    Thank you
    Sven

  5. Maxim Orgon

    Hi, I can not open the project on Flash CS3. Please help me.

    1. it’s haXe only. you have to port the pathfinder to as3 on your own (basically it’s just GraphAStar.hx and Waypoint.hx), and use the as3/swc version of ds.

  6. Maxim Orgon

    have download it. but seems like it have 2 folders which have same files inside.
    which shall i use ?

  7. Maxim Orgon

    I triest with they both but none worked on Flash CS3. Full of errors into the code.
    Please did someone succeed to translate it to Action Script 3 ?

  8. Yordan Yanakiev

    I havent succeed with thanslating to Action Scrip 3 too. Trying with Flex, but seems like it use different structures, which i am not familiar with.
    If someone have succeed with the translation, please post the sourcecode or the files.

    Thanks in advance.

  9. ?????as3????
    i need AS3 version,pls

  10. This is a much sought after component for games in flash. Please can someone convert to AS3.

  11. Thanks for the great post and all the work you have done on the ds library. I was working on porting a bit of the code from this sample to AS3 and I hit a dead end at the Delaunay triangulation. Porting the algorithm to Haxe or AS3 is beyond my level. I found a port of it here: http://indiemaps.com/blog/2008/05/delaunay-triangulation-in-actionscript-3/

    However, it seems to have bugs when triangulating for large data sets with similar points e.g. a grid.

    I was wondering what algorithm you used to do the Deaunay triangulation in your code. I have been unable to locate it in the Haxe AS3 swc files.

    Thanks,

    –jason

  12. Oh! So cool. Thank you so much. This stuff is like gold :)!!

    Keep up the great work. I am a huge fan.

    -jason

  13. William Markus

    lol. Hexe ?
    No Actionscript ? omg.
    this Haxe is like creating something which noone need :D

    This project will go nowhere without Actionscript, because the main users of the library, which actually using it is Actionscript developers.

    It will be just the same result as Microsoft abandone windows and start produceing calculators for instance :D

    Why should someone use Hexe, where there is so many, SOOO MANY platforms and developing environments out there ?

    For instance we can do a small test C# vs Haxe produced game.. shall we bet who will win ?

    It is just pointless.
    I would suggest – stick heavy to AS3 and JS. this is your power, this is your value !
    On theese 2 fronts you are only valuable, and even can actually sell products.

  14. Hi, I need the as3 port too, I’ll be checking the comments of this post until someone post the as3 port =D tanks.

  15. By the way, your AS3 code from your other example is the most beautifull code I have ever touched in all my sad developer life. Good luck!

  16. I too would highly appreciate the AS3 code. Michael would it be possible to simply publish this path finder as a SWC?
    If not would it at least be possible to make the haxe source available in a zip or something?

    Cheers!

    1. the pathfinder has been included in my library. see package de.polygonal.ai.pathfinding. you can build a swc on your own with : “haxe -swf pathfinder.swc -cp src/lib de.polygonal.ai.pathfinding.AStar” hope that helps.

Trackbacks/Pingbacks

  1. […] July, 2011mongoAS3 – An ActionScript 3.0 MongoDB Driver17. July, 2011arc experiment18. July, 2011A* pathfinding with ds22. July, 2011- jonas© Jonas Jaeger – 2009 var […]

Get Adobe Flash player