Forums » Code » Flood fill path-finding (same path for all entities)

Hey,
while building my current game (a tower defense) I had to build a path-finding solution.
At first I used the A* plug-in available but it is not efficient in my case. It calculate a path for every entities while I need only 1 path for all my entities.

The flood fill path-finding consist of storing in each tiles, the distance to the exit. The monsters check the tiles neighbors and go to the one with the lowest distance value.
It's way more efficient but it concerns only games where all entities are going to the same destination.

It doesn't support diagonals.

Demo: http://doobdargent.com/alpha/distanceMap/
Sources: https://github.com/doobinay/Impact-DistanceMap/

Very cool. I was looking for something like this too.

Nicely done. Be sure you post it over at POIJS also. ;)

Really nice plugin!

I built a little prototype with the plugin to see how it worked.
And it works great!

Have a browser demo here:
http://morgondag.nu/td/index.html

I also tried it out the same demo on iPad 3 with Ejecta
And got a solid frame-rate of 60fps.


Added a build tower function, and a custom tower.
Pause and resume function, some standard stuff.

There was some errors initially sutch as missing tiles.png
And some Weltmeister errors in the creep file. (sortEntitiesDeferred)
But all you have to do is:

if(!ig.global.wm) {
    ig.game.sortEntitiesDeferred();
}

Just spawning creeps endlessly in the demo to test

Give it a spin:
http://morgondag.nu/td/index.html