Comment by reitzensteinm | Hacker News Reader

Comment by reitzensteinm | Hacker News Reader

One trick I've used quite a bit in games I've written is to do a breadth-first search of the entire playfield, with no termination, resulting in data for how to get from any tile to the destination.

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.

Isn't this just flow field pathfinding?

http://leifnode.com/2013/12/flow-field-pathfinding/

Another good article about flow field pathfinding: http://gamedevelopment.tutsplus.com/tutorials/understanding-...

Nice demo video and intro here: https://www.youtube.com/watch?v=Bspb9g9nTto

Yes, though I didn't know the proper name for it until now.

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.

How often did you need to do the pathfinding in Robokill? I've tried making a game where I did pathfinding with A* every few seconds with 20 enemies tracking a player and it locked up the browser for like a second every time.

Using the technique I outlined, the pathfinding is run continuously, stepping once per frame, processing tiles further and further out. When the player changes tile, it resets.

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.

Reply on news.ycombinator.com