Need help with a flood fill algorithm for pathfinding

Join Date: 2012-02-28
Post Count: 1672

#221205919Thursday, July 13, 2017 12:09 PM GMT

I'm slowly advancing with my RTT game, but right now I'm kinda stuck on the pathfinding. The algorithm I am using is the Flow Field specifically meant for cases like in RTT in which you have multiple instances trying to get to the same location from different places. It is a combination of a flood field algorithm which fills the whole grid and vectors. Now I am trying to optimize the flood fill as much as possible. Currently I'm using a sloppy algorithm which checks if neighboring nodes were already checked and it's really damn slow. It takes around 1.6 seconds for a 64x64 grid without generating the vector field, and my maps will probably be at least 128 units wide and long.

nooneisback

Join Date: 2012-02-28
Post Count: 1672

#221211414Thursday, July 13, 2017 2:20 PM GMT

bump

nooneisback

Join Date: 2012-02-28
Post Count: 1672

#221214676Thursday, July 13, 2017 3:19 PM GMT

Bump

nooneisback

Join Date: 2012-02-28
Post Count: 1672

#221216413Thursday, July 13, 2017 3:54 PM GMT

I rewrote the whole thing, did as much optimisation I could and now it runs in less that 0.05 seconds.

nooneisback

Join Date: 2012-02-28
Post Count: 1672

#221337810Friday, July 14, 2017 10:15 PM GMT

Last update, I tried using Dijkstra's algorithm for flood fill, but I actually used a simple brute force search algorithm. It's very similar, but it skips the weight checks and just does its job exactly as I want it to do.