Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[jeancallisti]

Hello,

Before anything, let me state that I'm not reigniting some old, ever-repeating topics such as : "Why can't DF be multithreaded?" or "I have better pathfinding suggestions for Toadie". No.

I'm restraining the scope a lot. My question is simple: Using DFHack or other, would there be a way to "hook" some custom code on the native pathfinding call, in order to entirely replace it? I know that currently it's A* so I can imagine that it's currently done in either one of the two following ways, or a mix of both : 1) the game calculates the entire route between the starting point and the destination, or 2) It just calculates the best next tile to move to, while keeping a "best general direction" heuristic in mind.

But then again, it doesn't really matter which it is. Whre/how could one hook some custom code? Where/when should they deliver the function's result? What tricks should they keep in mind when doing so? (by tricks, I mean : some external world data that's thrown in out of nowhere into the native algorithm, whcih has access to everything all the time)


EDIT : if needed, think out of the box. For example, imagine a mod that stops every dwarf as soon as they try to move, but only lets them move one tile at a time -- and it would be the mod deciding what that target tile should be, by relying on its own algorithm.

[Quietust]

There are no explicit "hooks" available for pathfinding - the best you could do would be to locate the function responsible for pathfinding (which would have to be done manually in each version/platform/architecture) and use DFHack to patch it to call your own custom routine instead (and hope that no calls to that function got inlined), and I really wouldn't recommend trying that.

[jeancallisti]

and use DFHack to patch

Just for my personal enlightenment: how do you patch a function with DFhack? EDIT : found the article about live patching.

EDIT: I would be very interested in reading your disassembled 0.23.130.23a

[Putnam]

It would be possible to override whatever movement dwarves are doing and replace it with your own, but the pathfinding calculations will happen regardless and A* ought to find the shortest path anyway.

[strainer]

With future movement mechanics dwarfs could organically flock and form lanes, clumsy units could clash and confuse flow, cause jams, dim units get lost / choose awkward routes, sharp units refine common routes. Path creation, selection and following systems can be tantalising to think about but really hard to hack anything substantial into closed source . It does appear the current system has scope for optimisations - with a roomfull of turkeys able to cause serious lag.

[Putnam]

I think the game does "can I path here?" calculations using quadtrees or similar, if I recall--something like it caching chunks of the map and whether those chunks are connected to other chunks path-wise.

[bloop_bleep]

I was wondering how the diggingInvaders plugin manages to override the pathing so that invaders can path and thus dig through walls... I tried deciphering it but there is simply too few comments for me to make anything of it.

[jeancallisti]

the pathfinding calculations will happen regardless

Unless... Unless.........? ;-)
The destination targeted has to be stored in the stack or even as an entity attribute. What if you replace that with the coordinates where the entity is currently standing?

A* ought to find the shortest path anyway.

That's not the goal.

Quietust, would still love to see the disassembled (deprecated) documented code :-)

[Putnam]

the pathfinding calculations will happen regardless

Unless... Unless.........? ;-)
The destination targeted has to be stored in the stack or even as an entity attribute. What if you replace that with the coordinates where the entity is currently standing?

I mean, yeah, unit.path.dest

[bloop_bleep]

And apparently unit.path.path contains the path it will attempt to follow. Perhaps modifying that will work as overriding pathfinding? Not sure if the default pathfinder will change it back to the original, though. Will try some testing.

[bloop_bleep]

Did some more testing. Yes, modifying unit.path.path does cause the unit to move according to the new path, but if it isn't in the destination tile by the end of it the default pathfinder kicks back in.

[jeancallisti]

Did some more testing. Yes, modifying unit.path.path does cause the unit to move according to the new path, but if it isn't in the destination tile by the end of it the default pathfinder kicks back in.

It makes sense that DF tries to fix the path as long as the last path waypoint is not the same as the final destination.

A more important question than knowing how the game reacts when you modify unit.path is to know how it reacts when you modify unit.dest. a) How often does it overwrite it? b) At which stage in the game loop?

Let's take the following scenario:
1) game loop starts
2) at some point in the game loop, the engine decides where each entity WANTS to go -- based on the AI. This would set unit.path.dest
3) at some point in the game loop (immediately after setting unit.path.dest, or in one big batch for all units later on?), the engine recalculates every unit.path.path (by calling the pathfinding algorithm), based on unit's current position and on unit.dest --> correct?
4) that is done only ONCE per game loop for each unit --> correct?
5) the pathfinding algorithm needs to work on some data from the world and from the unit. Namely: the topology of the world, and the position and destination of the unit. If there was some pre-computing of the world (such as: turn it into abstract network nodes) performed at some point, I still count it as "data from the world". Could you try to list as thoroughly as possible what data is taken in account? Only the sheer distance? Does it "cost" the dwarf to walk up/down , to walk past something hot, etc.? Does the dwarf try to walk arpund enemies? WARNING: I'm asking these questions in the pure context of pathfinding! If those modifiers are applied AFTERWARDS in the game loop, based solely on the position of the dwarf at a given time, then we don't care. What I'm asking here is: is there data from the world weighing on the Pathfinder's nodes?
 6) the path is now calculated and unit.path has been set. The unit will reach the last node of unit.path (which also happens to be unit.dest) not in this game loop, but in a later game loop. Therefore, when exactly does the game decide that we've tampered with unit.dest or unit.path and overwrite it again? EDIT oh I get it. If the last node of unit.path.path is not unit.dest, then when its reached the engine sees that the unit is still not at unit.dest, so it runs the pathfinder again to fill the gap of missing waypoints.
7) what is the nature of waypoints in unit.path? Are they contiguous game tiles or tiles that are separated only by a straight line?

[bloop_bleep]

I don't think unit.path.path is recalculated every tick. That would be WAAAY too much a drain on performance, and completely unnecessary -- unit.path.path would be recalculated only when the unit is either waiting on a new job or has encountered some kind of obstacle in the way of his current path that wasn't there before (like a locked door.) That is, if a unit tries to move into a new tile according to his path and finds that he can't, his path is recalculated, but ONLY then. This makes it much easier to override default pathfinding, as well.

Also, I can't remember the details of it, but each "block" (16x16 area on 1 z-level) has its own internal connection graph, and the whole map has a connection graph between individual blocks, as a sort of performance measure (first the game checks if there is a path using the higher-level connection graph between blocks, and if there is, it tries to resolve it in a more detailed way using the blocks' connection graphs. If it doesn't find a path using the higher-level graph, it already knows there's no path at all, and saves time by not having to go into the more detailed connection graphs.) Burning objects and enemies are not factored into pathfinding at all -- pathfinding simply determines whether it would technically be possible for the dwarf to go from A to B. For that reason, however, water of depth 4 and magma of depth 1 do, in fact, count as blockages.

unit.path.path is just a list of adjacent tile positions, separated into three vectors, x, y, and z. The x coordinates of the positions are placed in x in order, the y coordinates in y in order, and the z coordinates in z in order. unit.path.path does indeed describe a contiguous sequence of coordinates.

[jeancallisti]

All of that sounds unbelievably promising.

I suggest the following test :
- load a world with 150+ dwarves
- measure FPS - It should be rather low?
- using your Proof of Concept script, set unit.path.dest = current dwarf position (or, if it confuses the game, set it to any arbitrary adjacent tile) for every dwarf at every game tick. This will do two bad things: 1) make the dwarf move in random directions and 2) call the pathfinding routine more often than it would normally. But it doesn't matter. We want to see if pathfinding on a distance close to zero is almost costless.
- measure the new FPS.

results?

[bloop_bleep]

I'll be happy to do this, but I'm not entirely sure we even have to. In order to override the old pathfinding routine with a new one, we would simply check for every unit every tick whether unit.path.dest has changed, and if it has, change unit.path.path to whatever we want. This way, the default pathfinding algorithm will see that unit.path.path has already been set, and simply skip pathfinding for that unit. There might be some timing issues with trying to get to unit.path.path before the default pathfinder does, but other than that it should be pretty simple.