Print

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

[Alrenous]

This is probably a question for Toady, but perhaps someone else knows too...

Do dwarves have a computation budget? As in, does DF ever skip calculating things if a dwarf is already making lots of calls to the CPU? Or, is the code designed so that dwarves rarely exceed a certain amount of per-dwarf processing power, because, for example, you can't have a dwarf fighting off goblins with an axe AND figuring out if and where to haul that bolt of cloth? (Complex pathfinding calls being one exception I know about that can't be avoided once the map requires it.)

If not, I think they should. It's even somewhat based in reality; humans, once a certain amount of thinking is being done, start simply ignoring low priority tasks.

I thought of this because I want to see reach added to DF combat, but that would require a fair amount of extra processing to be done when two units close on each other, as they'd have to step through each unit of reach, essentially breaking up the final tile into as many tiles as there are reach categories. (Modulo some optimizations.) Then I realized one could steal the processing by dropping other processes on that dwarf either as a soldier or during combat, and then I generalized it...why not do this heuristically on every dwarf?

Related; perhaps there are lots of things about coding that I don't know that would utterly change my thinking about this, not being particularly experienced myself. Please let me know, if so.

P.S. actually I'm going to contradict myself. There should be more CPU-efficient but path-inefficient path-finding algorithms that a dwarf could switch to if it detects that pathfinding calls are getting onerous. This is also realistic; actual dwarves wouldn't have clairvoyance and aren't likely to pick the fastest route over complicated geometries. I'm not especially suggesting Toady do this...just thinking about the theoretical boundaries. (New personality trait! "Can find his/her way around well...corresponds to using more CPU-intensive pathfinding, with better paths.  Perhaps sober dwarves could all find their way around less well...)

[Ampersand]

I'm pretty sure most of the things like Reach and all that combat related stuff, as of right now, are more or less abstractions. When it comes down to it, it's a roll of the dice fed into an equation. In the end the combat boils down to simple arithmetic with a bit of randomness added in. While obviously when there's a lot of this going on at once, it'll cause some excess CPU load, that's true for the combat system as it is right now. I wouldn't worry too much.

[SolarShado]

P.S. actually I'm going to contradict myself. There should be more CPU-efficient but path-inefficient path-finding algorithms that a dwarf could switch to if it detects that pathfinding calls are getting onerous. This is also realistic; actual dwarves wouldn't have clairvoyance and aren't likely to pick the fastest route over complicated geometries. I'm not especially suggesting Toady do this...just thinking about the theoretical boundaries. (New personality trait! "Can find his/her way around well...corresponds to using more CPU-intensive pathfinding, with better paths.  Perhaps sober dwarves could all find their way around less well...)

Sorry to de-rail already, but this sounds very cool. It might get annoying at times though...

[macdonellba]

P.S. actually I'm going to contradict myself. There should be more CPU-efficient but path-inefficient path-finding algorithms that a dwarf could switch to if it detects that pathfinding calls are getting onerous. This is also realistic; actual dwarves wouldn't have clairvoyance and aren't likely to pick the fastest route over complicated geometries. I'm not especially suggesting Toady do this...just thinking about the theoretical boundaries.

Aside from steering, I don't think there's such a thing as a more efficent pathfinding algorithm than A* for the given problem domain. Tile-based pathing isn't really something you can fuzz to save CPU time, especially on an arbitrarily complicated map.

[Alrenous]

Call A* once to find -a- route from z-level -1 to z-level -3.

All dwarves use this route if they're at -1 or above and need to get to -3 or below. Since the way DF is structured means A* has to be called at least once per z-level, this will drastically reduce CPU load if there's lots of dwarves traversing these levels. If you have or make multiple stairs, to fully optimize you have to call A* to each stair and then call it again a z-level down to each target stair. This would skip all that except for the first time.

There's one CPU optimization that, for certain dwarves, kills path optimization. Similarly single levels can be broken up into modules that dwarves just string together, although this is a pretty drastic step against path optimization. That's actually the kind of pathfinding that WoW uses - the coders pre-definite path segments and then the mobs play spider across the web. (Except evade mode, which appears to go all ATV.)

[macdonellba]

Call A* once to find -a- route from z-level -1 to z-level -3.

All dwarves use this route if they're at -1 or above and need to get to -3 or below. Since the way DF is structured means A* has to be called at least once per z-level, this will drastically reduce CPU load if there's lots of dwarves traversing these levels. If you have or make multiple stairs, to fully optimize you have to call A* to each stair and then call it again a z-level down to each target stair. This would skip all that except for the first time.

Not all areas on each Z-level are connected, and the idea that DF just propagates to the first/each downstair seems to greatly underestimate Toady's intelligence (a downstair just needs to be a node with an extra connection in the graph, since A* is just a variant of a tree-search algorithm.)

Similarly single levels can be broken up into modules that dwarves just string together, although this is a pretty drastic step against path optimization. That's actually the kind of pathfinding that WoW uses - the coders pre-definite path segments and then the mobs play spider across the web.

Someone was trying on getting that to work automatically, but it's not as easy a heuristic to write as people think. If anyone wants to create one, it's probably an undertaking worthy of a master's thesis, and would be welcomed as a massive improvement over the current state of the art.