Dijkstra flood fill, path to all destinations

[JSwigart]

And one from the exits

[JSwigart]

one more Using walls as seed points, it can be useful to identify choke points and areas with the most open space, etc.

Imagine iteratively generating versions of this with potential wall/rampart locations seeded as well to analyze the resulting changes to path flow. There is a lot of opportunity for interesting applications.

[MrFaul]

Hmm.... thanks this was really helpful.
It helped me to solve a problem that I'm thinking about all day long.
Never did it occur once to me to use a flood fill
Sometimes the simple solutions are the best

[Calfa]

@mrfaul said in Dijkstra flood fill, path to all destinations:

Sometimes the simple solutions are the best

Calling this simple made me cry

[keenathar]

@jswigart I believe your system does still contain small bugs. For some reason there's a bunch of 6-s that should be 2-s just above the spawn in the map using walls as seed. Nice function otherwise

[Flyasd1]

@keenathar Try to look attentively, the are swamp in those places.

[keenathar]

@flyasd1 Right, but he suggested using it to recognize choke points or open areas. That would mean the terrain is not relevant, only the number of tiles away from the walls:

Using walls as seed points, it can be useful to identify choke points and areas with the most open space, etc.

[JSwigart]

You're right, I didn't pass swampCost: 1 into those queries I used as an example. Sometimes useful queries are pure proximity, sometimes, you want them to be travel time based(such as a path lookup fill). Since it uses the same API as the Pathfinder.search, you can choose how you want to utilize it. I already have mixed uses in my room building code, including an inversion boolean and a multiplier scalar as well, because I'm additively using multiple different criteria for a few situations. I'll try to get the PR up soon. I want to exercise it in my own room building code in various ways to make sure I don't leave out any obvious options.

[wtfrank]

Why not make a library with this and put it on github?

[Flyasd1]

@wtfrank I think because PathFinder is native library and have better performance then JS library.

[deft-code]

Using flood fill looks like a cool way to analyze a room. However it really should not be part of the api. The recent changes to the terrain inspection enable fast communication between JS and WASM. This could be a wasm module if you really need to call it frequently. Though honestly I expect this would be a just fine as an expensive but cacheable calculation.

[JSwigart]

There's no downside to it being part of the API. Not making it part of the API is to basically implement a much slower pathfinder on the script side, which doesn't make much sense, in either cost or memory. A flood fill is just a clone of the existing pathfinding api(A*), without the heuristic(making it Dijkstra), and with different handling of the completion criteria, and of course returning a room sized array instead of an individual path.