PathFinding.js
qiao.github.io
qiao.github.io
This has a few nice advantages:
* Breadth first is trivially broken up to iterate over multiple frames, amortizing the cost of visiting each tile
* It reduces the worst case as the number of enemies scales up but the destination counts are low.
* The implementation in general is very simple
* You can still early terminate if you keep track of the farthest distance a pathfinding layer needs to satisfy.
* No pathological, worst case situations where a playfield becomes very expensive to pathfind. An open field is the worst case.
I first used this in Robokill, a flash game which often had 20+ enemies on the same screen tracking the player. I estimated at the time that it cost about as much as doing A* on ~5 enemies.
In games, the worst (common) case is basically all that matters - a constant 60fps is significantly better than 100fps dropping to 30fps occasionally.
This results in a relatively small per frame cost, with a constant worst case (for a 21x21 tile grid, it would be at most 80 tiles processed in one frame, i.e. 21x4 - 4, the number of tiles in the outside border).
As outlined above, this is exactly what you want in a game, because it makes the sharp edge cases you're describing impossible. Throw a hundred enemies in there in a pathological maze environment, moving the player around continuously, breaking walls, and it (the pathfinding aspect) will run just fine.
Try to do that with A* in the browser, and my crystal ball predicts the addition of a well worn copy of Web Workers for Dummies on a book shelf near you :)
One gotcha is that if you don't stop moving, half of the screen that's too far away from the player will not be updated, but enemies in those squares just use the out of date information. In Robokill, I couldn't even notice the error this causes when I was testing.
Nice demo video and intro here: https://www.youtube.com/watch?v=Bspb9g9nTto
I knew it wasn't a novel technique (it's too basic for that), but had not seen it discussed before on HN, so I thought I'd share my experiences.
Edit: Reading the linked article, their particular algorithm is not incremental, and not breadth first, which in my view leaves a lot of value I was talking about above on the table.
It also uses a list lookup when marking the tiles - please don't do this in real world code! Though it was probably to simplify the blog post code.
BTW, I actually found this when I was looking at his other repo for visualizing midi files @ http://qiao.github.io/euphony/#36 code @ https://github.com/qiao/euphony
In any case, playing with this visualization helped me poke holes in some of the simplified approaches I had in mind.
Can you show a few cases where Manhattan loses by a landslide?
Based on those definitions, I would guess that “Chebyshev” distance is almost always the most accurate heuristic to use when you check “Allow Diagonal”, because it will always be perfectly accurate if there are no walls in the way, unlike the others. Similarly, when “Allow Diagonal” is unchecked, “Manhattan” distance is the most accurate. And “Euclidean” distance is always the least accurate in this demo, because in this demo, paths are always constrained to 45° or 90° turns so that they stay on the grid, whereas Euclidean distance assumes that it is possible to move at arbitrary angles like 18.2° right from east.
Here's a cute and furry demonstration of biological pathfinding: https://www.youtube.com/watch?v=HRd5WYrnML4
It is worth mentioning though, that this approach probably isn't so good if the map level is very large, since the BFS is way more likely to catch something around the player first.
http://www.redblobgames.com/pathfinding/a-star/introduction....
I also used a method to create discrete path between cells, to straighten the path when possible.