Try the A* pathfinding algorithm with HTML5 canvas

http://www.matthewtrost.org/projects/astar/

by coderdude • 15 years ago

114 43 15 years ago

5hoom2• 15 years ago

As I am currently trying to implement the A* pathfinding algorithm in C++ this is both timely & very cool.

Most interesting is the selectable distance heuristic function (never thought about doing that in my own limited experience) which could mix things up a bit with a pathfinding game AI or similar.

Kudos for sharing this little gem :)

[edit] implementing A* on my own for educational purposes, but here's a good reference implementation in C++ on google code:

http://code.google.com/p/a-star-algorithm-implementation/

gradstudent9• 15 years ago

There are about a zillion implementations of vanilla A* on the internet. What's particularly interesting about this one? Do you have some cool new heuristic function or some nice insight into how the search works? The as-is version is pretty crappy. I mean, I can't even see the nodes expanded!

coderdude3• 15 years ago

As far as I can tell there is nothing particularly interesting about this implementation. It's cool because it lets you play with it and because the code is pretty short which makes it easy for anyone unfamiliar with the algorithm to grok how it works. It also has some nice documentation: http://www.matthewtrost.org/projects/astar/documentation.htm...

For the Python programmer here is a very short implementation of A* that someone on Stack Overflow posted: http://stackoverflow.com/questions/4159331/python-speed-up-a...

gradstudent9• 15 years ago

Actually, I found the documentation reasonably poor. It does a good job of explaining the API but does little to provide a would-be user with any insights into why the search works, how it works or how efficient it is. It doesn't even discuss why (or when) I might choose one of the three given heuristic functions over the others.

i.e. despite its length, it's not actually a very useful document.

StavrosK4• 15 years ago

What sort of cool new heuristic function could one have? All you need is the three shown there.

gradstudent9• 15 years ago

Excuse me? The study of better heuristics to guide search is a very active area of AI research. See, for example, Sturtevant et al's 2009 work on True Distance Heuristics or their 2011 work on compressed heuristic functions presented at AAAI last week.

AlexC04• 15 years ago

Even if it's not the best implementation, it could be considered as scaffolding upon which to improve.

While you clearly have enough experience with A* to tell the difference between a good and bad implementation, I've not got the same background (I've been reading about it, looking at flash implementations and trying to figure out how the heck I was going to do it in JS+Canvas).

Maybe there's a short list of glaring inefficiencies or places where this implementation is behind the curve. What's it missing?

I'm sure that for the OP this is a reasonably significant achievement, to me it's voodoo... and to John Carmack it's something else.

I doubt Carmack would be so derisive of someone's professional development. Would you tell an 8 year old that their finger paintings were pretty crappy too?

Criticism can be valid and encouraging if delivered in the right way.

gradstudent9• 15 years ago

Perhaps we have different expectations of what we think should appear on Hacker News.

I come here to find out about cool new stuff that hackers elsewhere in the world are working on. To me, an individual learning a fundamental AI algorithm isn't all that interesting. Particularly as the OP in this case has nothing to add to the discussion; he's just crowing to the world: "Look! I implemented someone else's idea!"

MortenK• 15 years ago

Where is your A* implementation?

MasterScrat• 15 years ago

I had made something similar some time ago, with a few more features (async searches with priorities) and the ability to see what paths are tested:

http://www.gravytea.com/labs/ariane/

andrewljohnson• 15 years ago

Here's a-star I implemented on iPhone/iPad - the actual a-star algorithm wasn't mine, just the game code around it. XCode project on GitHub: https://github.com/trailbehind/The-World/tree/master/TheWorl...

5hoom2• 15 years ago

Outwit the A* pathfinding ninja!

That's really nice, thanks for sharing.

baxter2• 15 years ago

It's so strange, I was just playing with pathfinding algorithms in CoffeeScript this weekend and thought about putting something like this together, but you have beaten me to it :) Really nice work.

swah• 15 years ago

What is strange is that we don't do things because other folks have already done it and miss a great learning experience :)

baxter2• 15 years ago

That's an excellent point! Perhaps I will put something together anyway. Thanks for this :)

xedarius• 15 years ago

One of the heuristics I implemented in my A, was to link information from the AI back to the routing grid. For example A will always pick the shortest route, however this isn't the best route. Imagine you have the AI pinned down in a building and the route finder picks a route out of the building, well it's likely to pick the shortest route (out the front door). So all the player has to do is put the cross hair over the door and keep shooting.

Now sure you could write some code to 'fix' this issue. Or you could let the problem fix itself. If when an AI pawn is killed at a certain point, I added a penalty to the surrounding nodes. This made the route more and more expensive over time, after a short while the AI decided to use the back door and walk around the building.

The important part of this is the player perception. To the player it looks like the AI is flanking the player, and they're like 'woooo cooool', which is the effect you're after.

palish2• 15 years ago

Brilliant!

That seems very similar to real life heuristics, actually...

"Holy crap, that guy in front of me just got blown away!" runs out the back door

shoo• 15 years ago

a few other tricks:

- increase the cost of traversing nodes that are within known enemy firing zones

- in some circumstances if the destination is unreachable it might be desirable to still compute a "best effort" path to the node that is the minimal heuristic distance from the unreachable destination

biot• 15 years ago

That sounds like a weighted graph, with different factors contributing to the weighting. Kills, terrain type, etc. can all play into that to account for each unit type's strenths and weaknesses plus historical factors such as number of kills. If you want to get clever, you could implement kill weighting while taking into account whether or not information about those kills has been communicated through direct observation, message relaying, sound, and so on. If you get really clever, you could end up with enemies who remove evidence of their kills to maintain the element of surprise, who hunt down last survivors to prevent the information from being communicated, and other emergent behavior.

mcculley• 15 years ago

I have a Java implementation at http://www.stackframe.com/software/PathFinder which has a similar demo applet.

ioquatix2• 15 years ago

If you are interested in a slightly more step by step visualisation you can try my original implementation: http://www.oriontransfer.co.nz/learn/a-star-maze-solver/inde...

bgrins2• 15 years ago

I really like that visualization! It would be awesome to see that same visualization side by side with Dijkstra's algorithm (same as astar, but with fixed heuristics) to see how much better it can perform.

ioquatix2• 15 years ago

Thanks - if I get some time I may consider augmenting it - that visualisation was put together as a proof of concept and as my first <canvas> experiment - it needs some more work ^_^.

kunley• 15 years ago

Folks are saying here how choosing a right heuristics is important. That's right but there's another catch:

For something more real (ie. graph containing more edges) A* needs priority queue for openset to extract the node with minimum f() in log time at most; also note such structure needs to delete previously stored entry by node not by f(), which is not something priority queue has by default - another area to fine tune in order to avoid time explosion.

humanfromearth• 15 years ago

Check out my golang implementation of astar: https://github.com/humanfromearth/gopathfinding

matthewtoast• 15 years ago

Hi, Matthew Trost (author) here. I'm actually a bit mortified that this found its way onto Hacker News, as now my admittedly bush-league JavaScript code is getting the brickbats. :-) In truth, I made it mainly as a practice exercise: code, UI, documentation .... So, please check out the links offered by others here, as many talented folks out there deserve attention for their far-more-sophisticated work!

In any case, I love this discussion. Programming is fun.

bgrins2• 15 years ago

Hey Matthew, great job on this! I had fun learning this algorithm, too. My implementation is here: https://github.com/bgrins/javascript-astar/blob/master/astar..., and I have a demo here: http://briangrinstead.com/files/astar/

I have added in a few optimizations: in my first run at it (https://github.com/bgrins/javascript-astar/blob/master/astar...) I used a standard array for the open and closed lists, and I found it slowed down quite a bit as the graph size got larger. I switched the implementation to a binary heap, which made it much faster for larger graphs. Try the original demo then the new one at 100x100 to see what I mean :)

steve_b• 15 years ago

I recently learned about the A* algorithm from the book Eloquent Javascript. Makes it very easy to understand. http://eloquentjavascript.net/chapter7.html

kaib• 15 years ago

If you are interested in a production quality open source pathfinding library take a look at Recast/Detour. It's used in a number of AAA game titles and is probably one of the most robust implementations out there: http://code.google.com/p/recastnavigation/

Full disclosure: the author works with me on Tinkercad, a web based solid CAD.

peterbraden• 15 years ago

I made something similar a while back - http://peterbraden.github.com/maze.html

It generates a random maze and uses a few different algorithms to find a path through it. Refresh the page to get a new maze.

SeanLuke• 15 years ago

In the back of my mind, I seem to recall that path-finding A * algorithms like these actually aren't quite A * .

IIRC, this is a constrained version of A * under the assumption that the heuristic h() is not only admissible but also monotonic, whereas A * only requires admissibility. The additional monotonicity constraint guarantees that the g() values of previously visited nodes never change, right? Otherwise if you find a better g() path you may have to do a lot of costly book-keeping. I presume the book-keeping is not part of the algorithm on display here.

Try the A* pathfinding algorithm with HTML5 canvas

Related Stories