Try the A* pathfinding algorithm with HTML5 canvas
matthewtrost.org
matthewtrost.org
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.
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
- 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
This is actually very important, especially in RTS games! If you have a unit selected, and he's standing near the edge of a cliff, and you right-click off the edge (intersecting lower-elevation terrian), then the naive Astar algo would make the unit run away from your mouse cursor, because it would search the whole map for a valid way to get there --- however the player very likely wanted to get as close as possible to the edge, e.g. to attack an enemy he spotted.
(In other words, when pathing to different elevations, the the player almost always wants the unit to "run up as close as possible" to the edge, not try to find a valid path all the way around the map.)
It's actually a very tough/interesting problem, because it's probably impossible to "always do what the user intends in every situation" by merely looking at his mouseclicks.
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:
Full disclosure: the author works with me on Tinkercad, a web based solid CAD.
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.
In any case, I love this discussion. Programming is fun.
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 :)
That's really nice, thanks for sharing.
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...
i.e. despite its length, it's not actually a very useful document.
I don't mean to be a hater but this fails at contributing something novel (which it doesn't), it fails as a learning resource which teaches something interesting (which it doesn't) and it fails as a well documented programming hack (which it isn't).
Harabor and Grastien had a nice AAAI 2011 paper on speeding up heuristic search -- which is specific to 2D grids.
You can see the difference in performance by comparing different heuristic functions; for example the special case of AStar where h(n) = 0 (i.e. Dijkstra's algorithm) vs the Manhattan distance heuristic. The latter is more informed and the search proceeds faster.
The paper to which I refer builds a database of costs between every node and certain landmark points. Given such information you can now better estimate the distance between two points by computing a distance differential.
Bottom line: their search is several times faster than vanilla AStar using a plain-jane Octile or Manhattan heuristic. More generally, the more landmarks you use, the better the heuristic. However, with better performance comes the need to store more costs which can introduce a significant memory overhead.
The details are in the papers I mentioned if you want to know more.
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.
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!"
All I'm saying is this: if you've learned something cool, and you want to tell the world about it, you need to present it in a way such that your learning contributes something to the learning of others. For example: explaining a complicated idea in really simple terms that anyone can understand (such as this cute example of the Halting Problem proof: http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html).
Another way to make your learning interesting to other people is to present an implementation that provides insight into the subject. The author tried to do this but I argue his execution is poor. I learned nothing from his app and nothing from his documentation. No implementation insights, no analysis, no beautiful code, nothing. Nada. Zip. Zilch. It's just a web-based A* implementation. Of which there are zillions.
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.
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.