21
\$\begingroup\$

What is the most elegant way to implement a command ordering system for AI? for example in dwarf fortress when you mark a forested area for wood cutting, the dwarfs then would do the following sequence:

  1. Go to the tree
  2. Chop the tree
  3. Deliver wood to the stockpile
  4. Go to another tree
  5. and so on..

I already have a stack command working no. 1 which goes from idle state to reaching the destination tile of the tree.

What I'm afraid of is how this would get messy when I create more orders like this:

Build a house

  1. Go to stockpile
  2. bring wood to construction area
  3. go back to stockpile
  4. Bring stone to construction area
  5. animate building sprite

Planting

  1. Go to stockpile
  2. bring seed to farm plot

Brewing

  1. Go to stockpile
  2. Bring plant to still
  3. animate brewing sprite

So my question is, how do I implement a command ordering system like dwarf fortress and avoiding spaghetti code at the same time? are there any data structures that I need to study? Do I need to put the command sequence on a separate xml file?

\$\endgroup\$
  • 1
    \$\begingroup\$ Dwarf Fortress actually doesn't have such a system. Dwarves are assigned one task at a time, and idle dwarves will look for something to do. ("Hey, there's a tree marked for chopping - I should chop it!" / "Hey, there's some wood not in a stockpile - I should take it to one!") \$\endgroup\$ – user253751 Jan 30 '15 at 6:37
  • 1
    \$\begingroup\$ Dwarves are not assigned anything by the player, but are "assigned" tasks by the system, which is exactly the architecture Jed T. describes above. Create order, and the system assigns individual component tasks in order to fulfill that order. \$\endgroup\$ – Attackfarm Jan 30 '15 at 7:32
  • 2
    \$\begingroup\$ Note that this is called Task Allocation and Scheduling, and is extensively studied in several engineering fields. You will find a lot of papers discussing this problem, which could be of interest. \$\endgroup\$ – TonioElGringo Jan 30 '15 at 9:24
  • \$\begingroup\$ @Attackfarm The system doesn't decide all the tasks in advance; nor does it assign multiple tasks to the same dwarf. One task is initially assigned, and when it completes, it has the consequence of making another task available. \$\endgroup\$ – user253751 Jan 31 '15 at 10:26
  • 2
    \$\begingroup\$ This sounds like an excellent use case for Goal-Oriented Action Planning \$\endgroup\$ – Problematic Feb 1 '15 at 2:20
27
\$\begingroup\$

At first you see that your commands are in the form of a list, so your first instinct might be to recreate that structure, and each dwarf will run through that list in sequence. What I suggest though is to break the list into steps, with each step having prerequisite(s), and then you run the entire command in reverse. Let me demonstrate with an example:

Wood cutting

  • Am I carrying wood, and at a stockpile? Yes: drop it off
  • Am I carrying wood? Yes: go to a stockpile
  • Am I at a tree? Yes: chop it
  • No to all above: go to a tree

The advantages of this is:

  • Very simple to implement
  • Flexible - you can freely decompose this list, add items, remove items, combine items
  • No state - you can run this list from the top for any dwarf in any state, and the dwarf will just Do the Right ThingTM

Disadvantages:

  • It's easy to get stuck in loops, since there is no state and no awareness of being stuck

Logically, you can represent these commands as a flow chart, that is run from the top each time, and what you do depends on whether you answer yes/no at each step. Whether you implement this in code or in an external file like XML is up to you.

\$\endgroup\$
  • 2
    \$\begingroup\$ This also has the advantage of letting status override commands, Am I hungry? if yes drop everything and set task to "eat" with eat being similar to the wood hauling job. \$\endgroup\$ – ratchet freak Jan 30 '15 at 11:05
  • 7
    \$\begingroup\$ @ratchetfreak "I know my fortress's safety relies on me fighting this monster so that it doesn't attack the civilians, but gosh, my stomach just growled!" Try not to make it too much like DF in that regard :P \$\endgroup\$ – Colonel Thirty Two Jan 30 '15 at 15:05
  • \$\begingroup\$ I think this resembles what uses (or at least used) which allowed the bugged artifact of planepacked (this was due to a forbidden item, which caused said looping) \$\endgroup\$ – Destrictor Jan 30 '15 at 15:08
  • 3
    \$\begingroup\$ @ColonelThirtyTwo Wheres the fun in that? ;) \$\endgroup\$ – Lasse Jan 30 '15 at 16:29
  • \$\begingroup\$ I strongly recommend not using declarative symbolic action planning for this. It's basically impossible to debug, and undesirable behavior can easily arise. Much easier to hardcode the action sequences for each task in a procedural way. \$\endgroup\$ – mklingen Jan 30 '15 at 18:01
10
\$\begingroup\$

If you can make sequences pretty general, there's not much of a spaghetti code.

In case of deliveries e.g.: WorkTask operates with a WorkPlan. Workplan says what kind of resource unit must pick, from what kind of house, using which walk animation, using which work animation, time to work and all such details. So in the end WorkTask might look like:

  1. Find %resource1% on map
  2. Go to that location using %animation_1%
  3. Work on place using %animation_2% for %time%
  4. Take %req_resource1% in %req_count1% count
  5. Go to %home% using %animation%
  6. Start %animation_6% inside for %time_2%
  7. etc..

We successfully use described approach. We have ~15 tasks in our game. Some highlights:

  • Tasks give unit actions (go there, enter, exit, go here, stay, work, go)
  • Action ends with either Done or Aborted state and passes it to the Task
  • Everything is hardcoded (no need to write parser, interface methods, backwards compability)
  • Each task implements abstract Task class with just a few common methods (create, execute, save, load)
  • Generally one task per module, but similar tasks are in one module
  • Very similar tasks are within one class and ruled by few IFs (deliver to house or deliver to unit)
  • Each task needs a proper locking and unlocking of resources (f.e. if unit dies at ANY step, the resource he locked must be released)
\$\endgroup\$
  • 2
    \$\begingroup\$ This is the system we use in our dwarf fortress-like game. Tasks are accomplished by behavior trees. Resources get locked by behaviors, and unlocked by failure. It's much more robust and easy to debug than the action planning approach described by the top answer \$\endgroup\$ – mklingen Jan 30 '15 at 18:00
5
\$\begingroup\$

So this is basicaly topographical sorting problem.

You have a graph, each node is a task that needs to be done, and some nodes depend on some other nodes (this is represented by an edge in the graph from depending node to the node it depends on). You want to do all the tasks, so you need to produce SOME ordering of the nodes that is topographicaly OK (the depending nodes are after the nodes they depend on).

Now, there are many such orderings usually (because some nodes have no dependences and can be put anywhere, and some nodes have the same dependences and aren't dependent on each other so they can be in any order between themselves, and any node can be put in any place after it's dependencies are done, and before nodes depending on it are done ).

It's also possible that there are no way to sort a graph topographicaly - this happens when there are cycles in the graph (you have no wood, to get wood you need to chop a tree, to chop tree you need axe, to make axe you need wood). In such case the algorithm should probably indicate to the player that these tasks can't be done.

You can also add priorities to nodes, and the task may be to find such ordering, among all orderings that fullfil the dependencies, that has the bigger priority nodes performed first.

You can also add recuring tasks - the easiest way will probably be to just add the task with timeout again to the graph each time it is done.

Now how to solve it - http://en.wikipedia.org/wiki/Topological_sorting

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.