Dijkstra flood fill, path to all destinations
-
I would like to request a method that can provide the paths to all goals passed into the function.
Existing functions such as findClosestByPath take multiple goals and do a search that aborts and returns a path for the first goal it reaches. I would like to have a function that leverages that same single Dijkstra search so that a path to all the goals can be returned. The alternative is to do individual searches from the source to each destination, which is many times more expensive, in order to get a path to each. A single Dijkstra with no abort condition(or with an abort condition when all goals are touched), is a much more performant way to perform queries when you want more than just the path to the nearest of a set.
One option to implement this would be to make a findPathToGoals function that takes multiple goals and then returns an object with key destinations and value paths to each one.
I would like to suggest a more broadly useful pathfinder function that provides this functionality and much more.
New Object interface PathSearchState { getGCostAt(x: number, y: number, roomName: string): float; getParent(x: number, y: number, roomName: string): RoomPosition; buildPath(x: number, y: number, roomName: string): PathFinderPath; }
New Function(s) Pathfinder.floodfill(source position, callback)
This function would invoke the flood fill at the source position and explore the room. Each iteration of the Dijkstra search would call the provided function and pass the position and g cost of the node at that position. The callback could return true to continue iterating, or false to abort the flood fill.
At the conclusion of the search, whether aborted early or not, the function would return the full search state in the form of the PathSearchState object, which acts as a cache for the pathfinding search state that is enough to ask questions like what is the path cost to any node that the flood fill touched, or to build a path to any position the flood fill touched.
This function is more generic in its implementation to allow a much more diverse set of use cases. Ideally this PathSearchState would also be serializable as well.
-
I'm not sure that I can imagine use cases when such methods will be really useful.
An inter-room flood fill sounds insanely expensive on the heap while an intra-room version can be easily implemented by a player.
-
@o4kapuk There are some useful use cases. A flood fill allows a number of opportunities that have uses in AI
- Static path lookup table for a given source position(s). Simply index into the resulting array and one can follow the decreasing cost edges to the goal.
- Tactical decision making can use the same fast index lookup to assign out the best creeps for a given target, taking into account each of their travel cost, saving a bunch of individual path lookups.
Think of it this way, if you basically had an O(1) lookup table of path distances to important landmarks in the room, from anywhere in the room, like to each source for example, some interesting higher level tactical options become more feasible, such as GOAP style action planning. When you don't have to invoke a full pathfind for each query of travel time, you can explore options that take into consideration several layers of actions.
I definitely would limit it to a single room though, for perf and memory reasons.
I put together a flood fill function in the pathfinding module myself today and here's the first visualization of it with a basic flood fill from the room controller and drawing the costs and lines that represent the flow map towards that source. I'm going to extend it to allow an array of positions to be passed as start locations, so that it can also build a flow map. For example, you could pass in all source positions to generate a room lookup table that represents 'nearest source'.
It's true this could be done purely on the player side, but it would be rather slow in comparison I think. The nice thing about doing it in the pathfinding module itself is that the uses are also expanded by being able to take advantage of the other functionality that the pathfinder already provides, like the cost matrix functions and such.
-
Here's one with multiple start nodes(sources)
-
And one from the exits
-
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.
-
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
-
@mrfaul said in Dijkstra flood fill, path to all destinations:
Sometimes the simple solutions are the best
Calling this simple made me cry
-
@jswigart I believe your system does still contain small bugs. For some reason there's a bunch of
6-s that should be2-s just above the spawn in the map using walls as seed. Nice function otherwise
-
@keenathar Try to look attentively, the are swamp in those places.
-
@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.
-
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.
-
Why not make a library with this and put it on github?
-
@wtfrank I think because PathFinder is native library and have better performance then JS library.
-
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.
-
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.