An idea to make the pathfinder quicker

I came up with this idea during the Dev stream about the pathfinding optimisations. I don’t know whether it has already been suggested or if it is already in the game’s code, or how well it will work, but here it is anyway.

Imagine you have ordered your hearthlings to dig a block down. They are done, and without a ladder they are stuck there. Every hearthling cannot go to any space outside that hole. Let’s call this hole a subworld (for simplicity), a closed in space in which all creatures are stuck.

For any subworld the following will count:
-all creatures can go to any place within this subworld, unless a barrier is created, but that would split the subworld into two, for both of which this rule still works.
-no creature can leave the subworld, unless a walkable connection is made, which merges the two subworlds into one, for which this rule still works.
-the place where you place your banner at the start is also a subworld, despite being not very enclosed.

My suggestion is to keep track of all subworlds that have a creature in it (as those are the only relevant ones). This is useful because you can say to the pathfinder, that any place outside this subworld can never be accessed. Thus the pathfinder will only have to search within the subworld a creature is in. Hearthlings will not seek paths to things outside the hole they are stuck in, and levels of elevation that don’t have a ladder to it, will also be ignored by the pathfinding. See the picture:

Basically hearthlings will not bother trying to find a path to things they cannot get to.

2 Likes

Do you only mean hearthlings? Because we already were told that there will be flying entities (from which I conclude also flying enemies), which would transition between the subworlds with ease and break the rule that there is no access between them.

Good point, I didn’t know about the flying creatures, and did not take them into account while thinking about it. And by hearthlings I also meant any walking creature, as those have the same walking restrictions as heartlings do (or at least I think so)

As for this suggestion, on the biomes mod thread I once suggested a disjoint set forest* approach, which is basically what you’re hinting at. There are algorithms for clustering space with O(1)** search time, such as union-find. The greatest challenge I see there is that whenever there’s a new partition in space (some place becomes unreachable) it is expensive to figure out if this really is a partition.

One way I can think of is to, at world construction time, attribute a partition number for each cell. That cell would have the same number as the adjacent reachable cells. Whenever a new path is dug that joins two cells, their regions are analyzed and may become the same.

The costly thing is when a new partition happens, like when you dig an area two levels down and separate space. I’m thinking a potential way is to detect such separation and trigger a pathfinding from the new region to the old one. Marking all blocks in the path as children of the starting point. If it reaches the old region, mark the starting point as child of the old region and you’re done. If you cannot find a path, then you make a flood-fill algorithm in the neighborhood, Marking every neighbor as child of the starting node. This is the most expensive operation in this, but it is necessary unfortunately, as far as I can think.

As for flying critters, they can just bypass this optimization, and most of the time fly in a straight line, so their pathfinding can be specialized and much simplified. And can bypass this check altogether.

The devs would be the proper people to tell if this is doable in the way things are structured right now.

@Tom and @Ponder, do you guys think this is a reasonable way? Sorry if I’m out of place calling you out, just thought this might help. I could not catch the stream, so I don’t know what you’re aiming at.

*Disjoint-set data structure - Wikipedia

**O(1) here actually being the inverse-Ackerman function, but close enough.

Moreso, items could also know the partition they’re at, so the pathfinding only happens for people in the same partition as a target object.

Another optimization still is keeping lists of things connecting regions, like stairs or bridges. If a bridge is the only connection between two regions (it could be it’s own region in the algorithm, though the path squashing mechanism would have to be revisited). So if a bridge goes down, the link automatically goes down. This could degenerate the algorithm in O(n) for the worst case scenario. But I don’t think that’s ever likely, and the person who exploits this is doing it on purpose :stuck_out_tongue:

One could also link the Job priority list (the code that decides what job a hearthling must do) into this.

“A building has to be build outside my subworld. I can’t reach it, so that is not my business”

1 Like

Well, I thought of it, you could let creatures do the work of finding out what is reachable and what is not. Almost every time the subworld change, there is a creature near to notice, and often that creature is to blame for the subworld changes. On the game load, tha map has to be analyzed, but after that, any change in subworlds are due to a hearthling / other creature making a connection or a barrier.

If a hearthling digs a tunnel to join up two subworlds, the game has to have its attention, as it has to add every accessable place to that subworld. The game can do that by checking all directly adjacent blocks. When the hearthling breaks through, and stands on the border of the subworld, the game will realise that one of these adjacent blocks is part of a different subworld, thereofre this heartling has successfully travelled in between, and thus these subworlds should merge.
If a heartling creates a barrier, then the game will know something is placed down that can obstruct the pathfinder, so it could try to path to the other side of the barrier, if it works, then do nothing, if it doesn’t, make a partition. Kanneblei’s idea with keeping track of links between areas can be put into this as well.

There are a few exeption where no creature is around to test/see that the subworlds change, these are when instabuilding or when goblin camps spawn. For the latter, you could have the goblins actively seeking changes, as with instabuilding, but with instabuilding you could also let the heartlings think they can path to it, and you only need one to find out that it doesn’t.

If that is necessary, I think that is a good idea. Ideally though, it wouldn’t be necessary, as my idea was to let the
job-search code, the destination-search code and the pathfinder just stop searching at the borders of a subworld. Items outside the subworld would thus not be visible, or even checked for their existence. You basically cut away parts of the world the game knows are unreachable. I have no idea if it works though.