AI Stuff
This is going to be a technical post. Today I’ve been working on fixing bugs in the AI code for the kickstarter demo. The AI in Dwarfcorp uses my own hand-rolled version of GOAP (Goal Oriented Aciton Planning) from Jeff Orkin at MIT. GOAP is based on STRIPS (Stanford Research Institute Problem Solver), which is an extremely old symbolic planning algorithm. The idea behind these symbolic action planners is to have agents (which, in my case, are Dwarves) plan in the dual space of “actions” and “states”. I discovered it while doing research for my PhD work in Robotics. Remember that AI from F.E.A.R that was touted as the greatest AI ever? That was GOAP. There are whole academic conferences on this stuff.
If you boil down all the things an agent can do (like in my case, chopping down trees, mining, moving things to and from stockpiles) to a set of discrete actions and states, you can plan using A* a series of actions which takes you to the goal. This can lead to some awesome behaviors from the agents, but it can be unpredictable. For instance, Dwarves in Dwarfcorp may decide that the best way to build a wooden wall is to chop down some trees, bring them to a stockpile, and then build the wall — or they could just as easily chop up their coworker’s bed and use it for the wall instead! Or, in my case, I’ve been debugging the AI planner deciding that it’s a great idea to have Dwarves steal dirt piles from each other over and over again as they try to build something.
To some programmers, symbolic planning can sound like the holy grail of AI, as it can allow your agents to figure out what to do on their own without programmer intervention. The sad part is, GOAP and STRIPS-like planners require a lot of boilerplate code to actually get them to work. You also sometimes have to pre-cache plans as action sequences if they are too complex for the planner. Even with these limitations, I’ve chosen to keep GOAP around as a design decision.
Interesting. Sometimes you want awesome weird unpredictable behaviors from the agents; sometimes you want them to be completely predictable. I only found this site today and don’t yet know what style of game it’ll be.
If you’re going to have lots of agents you might want them to coordinate in some way. Goblin Camp (inspired by Dwarf Fortress but much much simpler) uses the Munkres-Kuhn algorithm to assign jobs to agents in a coordinated way. This moves the AI work from the individual agents to the management of a job queue. The job queue is centralized so it’s the town collectively making plans and deciding what work needs to be done first, instead of each agent deciding that.
What I’m missing is an algorithm to assign goals to Dwarves. Right now the AI is assigned goals with a heuristic saying which goal is closer to which Dwarf. An approach like the Munkres-Kuhn algorithm would be way more principled. Thanks for the advice!
Also, I just realized you are Amit Patel!! I occasionally read your blog. I directly used your post on terrain generation to make the terrain generation in Dwarfcorp! Thanks for the great content you put out.
Glad my terrain generation pages helped! I’m looking forward to this game. 🙂