[danblick]

I'd recommend thinking a little about the algorithms involved in efficiently assigning a nearby task to each dwarf and then planning a path for each dwarf to its destination.

It gets interesting pretty fast and a PhD would not hurt. :)

e.g. https://arxiv.org/abs/1906.08291

Would you maintain a roadmap telling you how to get from place to place, or just constantly replan? What happens when you change the available paths by building a wall or locking a door?

[izend]

That's not even the most complex algorithm Tarn has implemented, I believe the ones he created for fluid dynamics are much more complex.

[hoseja]

Does it still do the thing where if you take a bit of water from a full reservoir, the hole just goes crazy, tanking FPS?

[setr]

Pathfinding is largely not that bad — hierarchal A* for long distance pathing, flow field for dense agent areas (eg your fort). With sufficient density, it’s worth recalculating the field repeatedly. Partitions can also be used for resource-lookup, threat caching, etc. Brogue’s djikstra maps[0], and Dave Mark’s modular influence maps[1] are very interesting possibilities as well..

Your paper is dealing with a completely different problem — collision avoidance is hard, and you really shouldn’t care about it in a game like DF anyways. Simply treat existing dwarves as a wall, or allow multiple dwarves to be on the same tile momentarily (with a very strong preference to stand on their own tile).

Task assignment is DF/rimworld/etc is also pretty dumb — they’re fairly obviously simple greedy algorithms. you don’t need to be anything close to optimal to be effective. There exists a list of open tasks (place building, move x59 stone, fight baddie. User actions generally corresponds to multiple tasks). When a dwarf is idle, he takes the task-list, merges it with his needs (food, water, self-preservation, etc). Filter this list by permitted activities for the dwarf, prioritize the list (needs first, then by user-defined job priority, then by random roll). Lock any relevant object (eg x59 rocks in a move task) and execute.

As far as I know, there’s no attempt at global coordination in DF beyond simple locks — which I’m not sure are actually that strict. In DF I’m pretty sure two dwarves can go for the same pile of x50 rocks, and it’s simply first one wins. In rimworld it’s quite clear only one entity can hold a claim. DF in that case is much simpler and error-free (don’t need to care about dwarves dying while holding a lock) but rimworld’s would be more consistent and make better progress over time (eg a far away entity doesn’t keep getting screwed trying to grab resources from the base).

Pathfinding is largely a solved problem. Resource allocation doesn’t need to be smart.

I’m fairly positive DF’s biggest hurdles are largely in finding game-sufficient and efficient estimate models for complex processes: planet, fluid, wind (a kind of fluid), plant growth, etc. These models are all fairly well defined (to our gaming needs) by their respective communities, but they’re also far more involved than what we need — we just need to be roughly correct, and ideally have a self-stabilizing sim.

The difficulty of gamedev generally is simplifying the problem to find only what actually matters.

[0] http://www.roguebasin.com/index.php/The_Incredible_Power_of_...

[1] http://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter30_Mod...