Posts made by 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.

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.

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.

And one from the exits

Here's one with multiple start nodes(sources)

@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.

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.