Using Floodfill To Calculate Water In Pipes

General Grid graph
#1

I’m building a top-down RTS where players lay water tanks and water pipes on a grid. The water can only travel so far from the tanks along the pipes, so I’d like to calculate how far any given pipe section is from the nearest water tank (there can be multiple water tanks on a circuit). Every pipe section occupies one grid tile.

I’m thinking the easiest way to do this is to floodfill the graph from each water tank (constrained to just the nodes that have a pipe on them), and assign a value to each node based on how many steps it took to get there. I can then use that value to sort pipe sections based on distance from a tank.

I’ve used A* for agent pathfinding but I’m struggling to find a tutorial or guidance on how to achieve this. My question is twofold - is this the best approach? And if so are there any examples of similar systems I can use as reference to get me started?

Thanks for the help!

#2

Hi

This sounds like it would be better solved using a custom Dijkstra search. If you have the connectivity information already, you can probably do it in less than 20 lines of code. Start the search simultaneously from all tanks, that will give you the distance in just a single search.

#3

I’ve spent the day trying custom Dijkstra searches and tutorials but tbh it seems that making this from scratch is a bit beyond my capabilities :slightly_frowning_face:

I’d like to use the A* grid graph for connectivity information if possible as it already has the nodes + connections set up and a tag applied to nodes that are traversable. Are there any in-built functions that could achieve this (even if it’s a bit less efficient than Dijkstra)? Alternatively if a custom Dijkstra search is a quick job for someone familiar with pathfinding algorithms would you be open for commissions?

#4

Hi

The easiest approach in this package is probably to use the FloodPath together with the FloodPathTracer type. It’s definitely not as optimized as a custom dijkstra search would be, but it is probably good enough for your use case, unless your pipes are really long.

https://arongranberg.com/astar/documentation/beta/floodpath.html

You’d start a FloodPath from each water tower, and then for each water tile you’d need to start a FloodPathTracer to get the distance.

#5

Got that working, thanks very much for the help! :grinning:

P.S. It’s maybe worth adding to the documentation that if you use a GraphMask to constrain the FloodPath to a specific graph the FloodPathTracer also needs a FloodPathConstraint using the same GraphMask in order to find the FloodPath (by default it’ll just revert to the first graph in the list). Took me a long time to figure out where I was going wrong :sweat_smile:

1 Like