7 ms·

I wish there was a more technical explanation on how the various Dwarf Fortress algorithms work. The major thing I still can't wrap my head around yet is how th

I wish there was a more technical explanation on how the various Dwarf Fortress algorithms work. The major thing I still can't wrap my head around yet is how the dwarves/NPCs schedule tasks and balance that with their needs. Somewhere I saw a blog post about Prison Architect, a game inspired by and with similar mechanics to Dwarf Fortress, that described one aspect of the task system: Instead of giving NPCs task lists, tasks are assigned to objects - say, a door that is not installed yet. The door would contain the instructions: "(1) move me to location [x,y] (2) install me at my current location", and idle NPCs would lookup objects with fitting tasks to their abilities/priorities and then execute the instructions. But how to combine this with needs is unclear to me, I would love to see a good explanation of this. Here is the insane list of needs a Prison Architect NPC has: https://github.com/originalfoo/Prison-Architect-API/blob/master/main/data/needs.txt https://github.com/originalfoo/Prison-Architect-API/blob/mas..., and Prison Architect, while already displaying emergent behavior, seems to still only have a fraction of the detail and complexity and emergence that Dwarf Fortress has. All the hype is about neural networks now, but these don't display this kind of emergent, social and constructive behavior, resource awareness and https://en.wikipedia.org/wiki/Homeostasis https://en.wikipedia.org/wiki/Homeostasis that these NPCs can.

coumbaya 3y ago
I don't know if this is this specific system in DF, but there is a recent video by Game Makers toolkit explaining The Sims AI which is kinda similar regarding objetcs and needs, pretty interesting https://youtu.be/9gf2MT-IOsg https://youtu.be/9gf2MT-IOsg
- 7373737373 3y ago
  Thank you! This makes me wonder why there is no open source implementation of/framework for such a mechanic (or why i haven't heard of one) yet - it seems to be the (potential) basis of many games - one other popular game using it is Rimworld. Also, why games like Minecraft have not long implemented such smart and interesting NPCs yet!
  - tialaramex 3y ago
    Although Microsoft/ Mojang does still actively work on Minecraft, a large fraction of real input to Minecraft's evolution is driven by the independent (Java) modding community. Today vanilla Minecraft has bees, but for many years modded Minecraft had bees, and in fact it had so many bees that people would routinely "nope out" of bee stuff because "Oh MY GOD. No more fucking bees". Jaded Cat's original Agrarian Skies has custom bees, which I think were pink or purple - and within a year or two everybody was sick enough of bees that they didn't want even the normal ones. As with other creative communities there are some distinct threads, like some people are into very heavily survival focused, up-against-it packs, where e.g. gravity works properly, mobs understand the game rules and will climb up to get you, or set fires, they will upgrade their gear, etc. while people like me prefer ascend-to-godhood type gameplay where you quickly dispense with monsters and become untouchable not far into play. In the latter style there's not a desire for "smart and interesting NPCs", in fact it's often played alone or in small groups, intentionally. In the former style the NPCs are somewhat smart, but they're a threat so if you make them too clever they'll just always kill the players which isn't much fun after a while. I think NPCs with the type of independence of a Dwarf Fortress dwarf wouldn't be attractive to either of the sorts of player I mentioned, it may be that such people just don't play Minecraft. But it's also possible somebody has implemented it and I've never run into it. There are a lot of Minecraft mods. Curseforge lists literally thousands of them, there could be hundred like you describe and I wouldn't have noticed. Packs might typically have a few hundred of those thousands, I might play four or five packs per year, but often the same mods recur because they're so useful or well-liked, like Just Enough Items gets used a lot, so does Refined Storage, but some weird dwarf intelligence mod could easily go under the radar not because people don't like it but because they didn't know it existed. I reckon a lot of people had never really used Compact Machines for example until Compact Claustrophobia took off, and in that the machines are absolutely mandatory and you use them from the first minutes so you have to get very familiar with them.
    - ehnto 3y ago
      Honestly it really was too much fuss about bees, in already very dense modpacks! I'm trying to get this space program off the ground so I can get back to my moonbase damnit. The reactor is melting down, I haven't got time for bees!
- cpeterso 3y ago
  This video is a nice introduction to “Utility AI” systems and includes examples from games like The Sims and Total War. (The Sims section starts around time 6:50.) https://youtu.be/p3Jbp2cZg3Q https://youtu.be/p3Jbp2cZg3Q A utility system is basically a codification of Maslow’s hierarchy: the system continuously re-evaluates possible behaviors’ utility functions and then chooses the top-scoring behavior. https://en.m.wikipedia.org/wiki/Utility_system https://en.m.wikipedia.org/wiki/Utility_system
hinkley 3y ago
At this point I think some transparency would be good. One of the complaints about the game is how as time goes on the simulation gets more and more detailed and eventually the game just grinds to a halt. A little more visibility into how all of this stuff works, and someone might be able to suggest that there's an algorithm that does this or that bit with a much lower order of complexity. A few of those and you can let a game run maybe twice as long.
- minsc_and_boo 3y ago
  If it's any consolation, a big CPU suck is friend-or-foe checks being done by characters on everyone in sight, in every tick. That came out last year-ish and making smaller taverns can (slightly) improve processing.
  - treeman79 3y ago
    Might be more fun to only check so often ir somewhat random ally. Human nature often it takes a moment to realize something is off. Bear walks into tavern. Some panic, others are slower to react / notice. A very drunk dwarf might never notice, or offer a beer to the bear.
    - hinkley 3y ago
      Different tick intervals based on perception would be funny. And practical.
      - JohnFen 3y ago
        And realistic. Our perception of time is constantly varying IRL.
polytely 3y ago
for more behind the scenes stuff on Dwarf Fortress I recommend listening to the occasional 'bay12 talks' podcast episodes hosted by BlindIRL (long time dwarf fortress streamer) he periodically talks with Tarn, and more recently Putnam (longtime modder and first external programmer on DF) about the state of the game and asks them player questions. https://youtu.be/BY4jwUuvy4E https://youtu.be/BY4jwUuvy4E
- 7373737373 3y ago
  Unfortunately these interviews tend to be full with fun anecdotes, but tend to lack technical details
  - polytely 3y ago
    now that putnam is here you can glean some details because they talk about working on the code more and about the stuff putnam is optimizing
deleted 3y ago
[deleted]
RugnirViking 3y ago
there is a menu in the game where you can see all the tasks that are scheduled in the queue including stuff like "wash self" and "replace clothing", with targets and who is currently assigned. I believe personal tasks like "have a mental breakdown" are spawned already assigned and locked in to the dwarf they are relevant to. iirc its the (j)obs manager, the same place you assign automated orders like making more beds/beer if the stockpile ever has less than 4 etc
asfarley 3y ago
Based on your description, you could describe “need fulfillment” as a task associated with the NPC object. Then you just maintain your original operations while adding NPCs to your object list.
serf 3y ago
>But how to combine this with needs is unclear to me, I would love to see a good explanation of this. some inefficient ways off the top of my head: create a threshold filter on the object with logic something like "only agents with need > X allowed", or iterate through the agents until you find one with the greatest need score that is pertinent to the object, or a combination of the two to reduce the list size that must be iterated. sprinkle in agent range from object and specific traits preferably before the list generation to further reduce iterations needed. i've thought about all of this a lot because i'm addicted to games with agency and emergent behavior. rimworld is a lot of fun in that regard because it's easy to jump into modding it, which makes agency experimentation a lot of fun.
m463 3y ago
lol, bladder/bowels right up there. Bladder 9 Bowels 9 Sleep 8 Food 8 Safety 7 Hygiene 7 Exercise 6 Family 6 ... I found it interesting that maslow's heirarchy of needs shows much more detailed heirarchy: "physiological", "safety", "belonging and love", "social needs" or "esteem", "self-actualization" and "transcendence" ...and the physiological needs are broken down further and slightly differently: Physiological needs include: Air Water Food Heat Clothes Urination Excretion Shelter[2] Sleep https://en.wikipedia.org/wiki/Maslow's_hierarchy_of_needs https://en.wikipedia.org/wiki/Maslow's_hierarchy_of_needs
chaostheory 3y ago
> Instead of giving NPCs task lists, tasks are assigned to objects - say, a door that is not installed yet. I believe that’s how Will Wright designed The Sims too
sk0g 3y ago
Have you heard of Goal-Oriented Action Planning (GOAP)? I've tried implementing it from scratch and it's really easy to get interesting, emergent behaviour. It can also be difficult to debug however, or reason about why things are happening -- or how to make things you want actually happen. I have a feeling commercial products would have much better tooling to ease some of those pains.
- 7373737373 3y ago
  I've seen this great video about it! https://www.youtube.com/watch?v=PaOLBOuyswI https://www.youtube.com/watch?v=PaOLBOuyswI
noirscape 3y ago
Basically when you make a task in dwarf fortress that requires a character in the game to do something, it gets added to a global jobs list. Dwarves will, assuming they don't have other jobs at the time, pick a job from that list as long as they're allowed to do so by their labor selections + workshop availability (if that is possible). Do note that this doesn't actually account for pathfinding or if the job is even possible. The game will gladly tell you over and over that a job is being cancelled if for whatever reason the items needed for it are inaccessible/don't exist. Just a small note. If the dwarf in question has no current jobs, the first priority will be for them to check their needs and try to fulfill them. Needs more or less are in two categories - "essential" and "non-essential". Non-essential needs used to be more obvious - it was the On Break part of a dwarfs schedule. Basically every once in a while, a dwarf goes "On Break", effectively making them unable to do anything except take care of their essential needs. Nowadays it's a set of activities derived from the unique identity of the dwarf (On Break doesn't exist anymore) - religious dwarves will want to play, while dwarves that seek musical entertainment will try to do so with a musical instrument. Essential needs on the other hand are things like drinking/eating and sleeping. These pretty much come in two degrees, "want" to do and "need" to do. Want to do means the dwarf will immediately get a job to fulfill the need once the criteria are hit - if a dwarf gets hungry while hauling a rock, they'll grab a bite to eat after. When a need progresses to "need to do", it just will straight up interrupt any non-need job they're currently doing[0] (the game even tells you this) and create a new job to do it. Its how a dwarf will fall asleep on the spot if they're extremely tired. Mental breakdown and tantrums are similarly "essential" needs, just with their own triggers that can't be interrupted by the player. [0]: With the notable exception of military duties, which is one of the reasons militias in Dwarf Fortress have to be on a rotating schedule - dwarves will not eat or drink if they're on active duty, no matter what. They will sleep in a barracks though.

coumbaya 3y ago

I don't know if this is this specific system in DF, but there is a recent video by Game Makers toolkit explaining The Sims AI which is kinda similar regarding objetcs and needs, pretty interesting https://youtu.be/9gf2MT-IOsg https://youtu.be/9gf2MT-IOsg

7373737373 3y ago
Thank you! This makes me wonder why there is no open source implementation of/framework for such a mechanic (or why i haven't heard of one) yet - it seems to be the (potential) basis of many games - one other popular game using it is Rimworld. Also, why games like Minecraft have not long implemented such smart and interesting NPCs yet!
- tialaramex 3y ago
  Although Microsoft/ Mojang does still actively work on Minecraft, a large fraction of real input to Minecraft's evolution is driven by the independent (Java) modding community. Today vanilla Minecraft has bees, but for many years modded Minecraft had bees, and in fact it had so many bees that people would routinely "nope out" of bee stuff because "Oh MY GOD. No more fucking bees". Jaded Cat's original Agrarian Skies has custom bees, which I think were pink or purple - and within a year or two everybody was sick enough of bees that they didn't want even the normal ones. As with other creative communities there are some distinct threads, like some people are into very heavily survival focused, up-against-it packs, where e.g. gravity works properly, mobs understand the game rules and will climb up to get you, or set fires, they will upgrade their gear, etc. while people like me prefer ascend-to-godhood type gameplay where you quickly dispense with monsters and become untouchable not far into play. In the latter style there's not a desire for "smart and interesting NPCs", in fact it's often played alone or in small groups, intentionally. In the former style the NPCs are somewhat smart, but they're a threat so if you make them too clever they'll just always kill the players which isn't much fun after a while. I think NPCs with the type of independence of a Dwarf Fortress dwarf wouldn't be attractive to either of the sorts of player I mentioned, it may be that such people just don't play Minecraft. But it's also possible somebody has implemented it and I've never run into it. There are a lot of Minecraft mods. Curseforge lists literally thousands of them, there could be hundred like you describe and I wouldn't have noticed. Packs might typically have a few hundred of those thousands, I might play four or five packs per year, but often the same mods recur because they're so useful or well-liked, like Just Enough Items gets used a lot, so does Refined Storage, but some weird dwarf intelligence mod could easily go under the radar not because people don't like it but because they didn't know it existed. I reckon a lot of people had never really used Compact Machines for example until Compact Claustrophobia took off, and in that the machines are absolutely mandatory and you use them from the first minutes so you have to get very familiar with them.
  - ehnto 3y ago
    Honestly it really was too much fuss about bees, in already very dense modpacks! I'm trying to get this space program off the ground so I can get back to my moonbase damnit. The reactor is melting down, I haven't got time for bees!
cpeterso 3y ago
This video is a nice introduction to “Utility AI” systems and includes examples from games like The Sims and Total War. (The Sims section starts around time 6:50.) https://youtu.be/p3Jbp2cZg3Q https://youtu.be/p3Jbp2cZg3Q A utility system is basically a codification of Maslow’s hierarchy: the system continuously re-evaluates possible behaviors’ utility functions and then chooses the top-scoring behavior. https://en.m.wikipedia.org/wiki/Utility_system https://en.m.wikipedia.org/wiki/Utility_system

hinkley 3y ago

At this point I think some transparency would be good. One of the complaints about the game is how as time goes on the simulation gets more and more detailed and eventually the game just grinds to a halt. A little more visibility into how all of this stuff works, and someone might be able to suggest that there's an algorithm that does this or that bit with a much lower order of complexity. A few of those and you can let a game run maybe twice as long.

minsc_and_boo 3y ago
If it's any consolation, a big CPU suck is friend-or-foe checks being done by characters on everyone in sight, in every tick. That came out last year-ish and making smaller taverns can (slightly) improve processing.
- treeman79 3y ago
  Might be more fun to only check so often ir somewhat random ally. Human nature often it takes a moment to realize something is off. Bear walks into tavern. Some panic, others are slower to react / notice. A very drunk dwarf might never notice, or offer a beer to the bear.
  - hinkley 3y ago
    Different tick intervals based on perception would be funny. And practical.
    - JohnFen 3y ago
      And realistic. Our perception of time is constantly varying IRL.

polytely 3y ago

for more behind the scenes stuff on Dwarf Fortress I recommend listening to the occasional 'bay12 talks' podcast episodes hosted by BlindIRL (long time dwarf fortress streamer) he periodically talks with Tarn, and more recently Putnam (longtime modder and first external programmer on DF) about the state of the game and asks them player questions. https://youtu.be/BY4jwUuvy4E https://youtu.be/BY4jwUuvy4E

7373737373 3y ago
Unfortunately these interviews tend to be full with fun anecdotes, but tend to lack technical details
- polytely 3y ago
  now that putnam is here you can glean some details because they talk about working on the code more and about the stuff putnam is optimizing

deleted 3y ago

[deleted]

RugnirViking 3y ago

there is a menu in the game where you can see all the tasks that are scheduled in the queue including stuff like "wash self" and "replace clothing", with targets and who is currently assigned. I believe personal tasks like "have a mental breakdown" are spawned already assigned and locked in to the dwarf they are relevant to. iirc its the (j)obs manager, the same place you assign automated orders like making more beds/beer if the stockpile ever has less than 4 etc

asfarley 3y ago

Based on your description, you could describe “need fulfillment” as a task associated with the NPC object. Then you just maintain your original operations while adding NPCs to your object list.

serf 3y ago

>But how to combine this with needs is unclear to me, I would love to see a good explanation of this. some inefficient ways off the top of my head: create a threshold filter on the object with logic something like "only agents with need > X allowed", or iterate through the agents until you find one with the greatest need score that is pertinent to the object, or a combination of the two to reduce the list size that must be iterated. sprinkle in agent range from object and specific traits preferably before the list generation to further reduce iterations needed. i've thought about all of this a lot because i'm addicted to games with agency and emergent behavior. rimworld is a lot of fun in that regard because it's easy to jump into modding it, which makes agency experimentation a lot of fun.

m463 3y ago

lol, bladder/bowels right up there. Bladder 9 Bowels 9 Sleep 8 Food 8 Safety 7 Hygiene 7 Exercise 6 Family 6 ... I found it interesting that maslow's heirarchy of needs shows much more detailed heirarchy: "physiological", "safety", "belonging and love", "social needs" or "esteem", "self-actualization" and "transcendence" ...and the physiological needs are broken down further and slightly differently: Physiological needs include: Air Water Food Heat Clothes Urination Excretion Shelter[2] Sleep https://en.wikipedia.org/wiki/Maslow's_hierarchy_of_needs https://en.wikipedia.org/wiki/Maslow's_hierarchy_of_needs

chaostheory 3y ago

> Instead of giving NPCs task lists, tasks are assigned to objects - say, a door that is not installed yet. I believe that’s how Will Wright designed The Sims too

sk0g 3y ago

Have you heard of Goal-Oriented Action Planning (GOAP)? I've tried implementing it from scratch and it's really easy to get interesting, emergent behaviour. It can also be difficult to debug however, or reason about why things are happening -- or how to make things you want actually happen. I have a feeling commercial products would have much better tooling to ease some of those pains.

7373737373 3y ago
I've seen this great video about it! https://www.youtube.com/watch?v=PaOLBOuyswI https://www.youtube.com/watch?v=PaOLBOuyswI

noirscape 3y ago

Basically when you make a task in dwarf fortress that requires a character in the game to do something, it gets added to a global jobs list. Dwarves will, assuming they don't have other jobs at the time, pick a job from that list as long as they're allowed to do so by their labor selections + workshop availability (if that is possible). Do note that this doesn't actually account for pathfinding or if the job is even possible. The game will gladly tell you over and over that a job is being cancelled if for whatever reason the items needed for it are inaccessible/don't exist. Just a small note. If the dwarf in question has no current jobs, the first priority will be for them to check their needs and try to fulfill them. Needs more or less are in two categories - "essential" and "non-essential". Non-essential needs used to be more obvious - it was the On Break part of a dwarfs schedule. Basically every once in a while, a dwarf goes "On Break", effectively making them unable to do anything except take care of their essential needs. Nowadays it's a set of activities derived from the unique identity of the dwarf (On Break doesn't exist anymore) - religious dwarves will want to play, while dwarves that seek musical entertainment will try to do so with a musical instrument. Essential needs on the other hand are things like drinking/eating and sleeping. These pretty much come in two degrees, "want" to do and "need" to do. Want to do means the dwarf will immediately get a job to fulfill the need once the criteria are hit - if a dwarf gets hungry while hauling a rock, they'll grab a bite to eat after. When a need progresses to "need to do", it just will straight up interrupt any non-need job they're currently doing[0] (the game even tells you this) and create a new job to do it. Its how a dwarf will fall asleep on the spot if they're extremely tired. Mental breakdown and tantrums are similarly "essential" needs, just with their own triggers that can't be interrupted by the player. [0]: With the notable exception of military duties, which is one of the reasons militias in Dwarf Fortress have to be on a rotating schedule - dwarves will not eat or drink if they're on active duty, no matter what. They will sleep in a barracks though.