Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 


Submitted by James Matthews, posted on October 08, 2001




Image Description, by James Matthews



Here is a screenshot of the latest version of A* Explorer (v1.1). It shows all of its features, including:
  • Dynamic search space indication (red/blue squares)
  • Node highlighting (blue square w/magenta arrows)
  • A* Stepping
  • Breakpoints (Red circle between O and D of Flipcode)
  • Open/Closed list viewing
  • Drawing your own large maps.
  • A* Explorer should be one of the most comphrensive A* learning tools out there. A* is very important to AI game developers, so I thought you'd all appreciate this. Plus the source code is available for download, along with the binary and help files at http://www.generation5.org/ase.shtml.

    Comments and improvement suggestions are very welcome!

    Later,
    James.
    http://www.generation5.org/


    [prev]
    Image of the Day Gallery
    www.flipcode.com

    [next]

     
    Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
     
    Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
     
    Nieuw

    October 08, 2001, 10:31 AM

    A* explorer and Generation5 0wn =)

     
    Tobias Franke

    October 08, 2001, 11:19 AM

    Gotta look that A* Explorer up, I'm on my way implementing it for my little, yet stupid bots =)

     
    lycium

    October 08, 2001, 11:30 AM

    Neat :)

    How does this compare to using REST (rapidly expanding search trees, a much simpler algorithm), computationally and performance-wise (ie. shortest distance, etc)?

    I still have yet to code a nice windowing system...

     
    meZmo

    October 08, 2001, 12:33 PM

    Very nice app!!!!

    Both fun AND educational. ;-)

     
    Nathaniel

    October 08, 2001, 12:34 PM

    Cool stuff, I'll have to give it a try!

     
    NinjaCross

    October 08, 2001, 12:43 PM

    Nice app, good work :) !

     
    psykotic

    October 08, 2001, 12:47 PM

    How does this compare to using REST (rapidly expanding search trees, a much simpler algorithm)

    I remember Cuban (Adrian Perez) describing RESTs on his website as something new. Believe me, it's not. Look in any undergraduate AI textbook and there should be a description of bidirectional breadth-first search. That is what RESTs are basically. The problem with any kind of BFS on large search spaces is that you need a ridiculously amount of memory. That's why iterative deepening search algorithms were invented (among other reasons). To answer your question: I am quite confident that A* will beat RESTs in practically all cases unless you intentionally choose a crappy heuristic and a horrible state space representation. RESTs will expand a lot of useless partial paths whereas A* will tend to move directly towards the goal without wasting CPU or memory on dead-ends. By the way, RESTs aren't really that simpler. If you have the state space presented as a graph and you already have a priority queue implementation at your disposal, it's a breeze. The problem is coming up with a (good) way of representing the world as a graph (uniform grids or visibility graphs are common choices) as well as a good heuristic (admissable heuristics are not always the best ones in practical scenarios). Just my two cents. By the way James, great work. I really like it.

     
    BOMB

    October 08, 2001, 01:50 PM

    Nice app for understanding A*

    I made an A* test-app a while ago, too..

    I noticed that your program has some problems with diagonals..your algorythm 'thinks' that diagonals are as long as the straight way..which is not true. You can solve this 'problem' easily, if you assign a cost for example of 1.4 for diagonals and 1 for the straight way.
    What heuristic-algorythm do you use? (You can optimize A* immensely by not using square-route (any approximation..)and it will work as good as square-route)
    A* is not really easy to implement in a RTS-game nowadays because comps are still too slow to calculate the ways for a couple of units(if you don't invent a lot of optimization..like creating quad-trees to prevent the algorythm of doing 'senseless' calculations on ways that can't be passed)
    In the worst case it took my (unoptimized) application 10 seconds to calculate a path (worst case = big U-formations).

    Anyway..i like a*, because i hate bad paths =)

    If i had that app, when i took a look at a* it wouldn't have had headaches on it that long ;)

    Good Work!

     
    n1c_V

    October 08, 2001, 04:19 PM

    How did that get out of my computer. Hmm i thought i didn't release that.


    Or i'm just kidding, kewl app :))

     
    lycium

    October 08, 2001, 06:59 PM

    i'd really like to know what happened to www.cubonics.com, i loved his rants/news (along with the ray tracing stuff of course). i should ask aggrav8ted sometime (he co-authored a dx7 book with him).

    anyway, i was just interested to know how my crap REST implementation compares against "professional" algos like a*. so much for that :)

     
    Max

    October 08, 2001, 07:06 PM

    "i'd really like to know what happened to www.cubonics.com [...]"

    Adrian has been working at Bungie since the beginning of the summer. I think he said he hasn't had time to deal with the hosting issues for his site, which is why it's down.

    Max

     
    fatbuddha

    October 09, 2001, 08:45 AM

    Nice work - it's always nice when somebody takes the time to predigest all of the complicated stuff for me. Nice interface too.

    I've gotta say though that you do need to sort out the whole diagonal movemement problem to stop the calculated path from 'bouncing' along the top of 'flipcode' like in your demo.

    Keep up the good work dude!

     
    James Matthews

    October 09, 2001, 03:19 PM

    Thank you for all the encouraging comments!

    You know, I'd never thought about the diagonal thing but it makes perfect sense now that you all mention it. I'll definitely add that to the next release.

    BOMB: A* is very useful for RTS games. There are a few chapters in the upcoming AIWisdom book that go into depth about this. The optimizations aren't all that complicated and produce some very efficient paths without a speed hit. A* Explorer also uses a Manhattan distance function like you mentioned, not the standard Eucledian one.

    Again, thanks for all the comments - and keep checking for future releases of A* Explorer for improvements. :)

    Regards,

    - James.

     
    This thread contains 13 messages.
     
     
    Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.