Programming Game AI by Example seems to be a popular book on this board, and I have used it myself as the basis for the AI in my game. Specifically, I have implemented the goal-oriented AI in C#. And now I have a question: Why does the list of subgoals need to work like a stack (last-in, first out). This is giving me big problems. If I add two subgoals that I want executed sequentially, I need to add them reversely, like so: AddSubGoal(new PickUpItem()); AddSubGoal(new GoToItemPosition()); instead of, more logically: AddSubGoal(new GoToItemPosition()); AddSubGoal(new PickUpItem()); That was tolerable in the beginning. Now that my project has grown I am adding 10 subgoals nested inside conditionals. The code has gotten very complicated. Does anyone have similar experiences? Shouldn't the list be a queue instead?

You can re-implement your task stack with any sort of data structure you like, so long as you use it appropriately. You could easily change it to a list, so long as you make sure that either the insertions or the removals are ordered according to the required execution order.

Cheers,

Timkin

Quote: AddSubGoal(new PickUpItem());
AddSubGoal(new GoToItemPosition());

instead of, more logically:

AddSubGoal(new GoToItemPosition());
AddSubGoal(new PickUpItem());

Well, I think that, conceptually, GoToItemPosition is a subtask of PickUpItem.

I'll say that I have the same book, but I skipped that chapter, so I can't tell you for sure, but for what I understood, you have to implement diferent levels as a stack, but subgoals as a list.

1. TakeItem
1.1. GoToItemPosition
1.2. PickUpItem

you have to do first "1.1.", then "1.2.", finaly "1.".

[Edited by - Atridas on July 14, 2008 5:19:57 AM]

I can probably get it to work again after I change the data structure to something other than a stack. I'm just anxious because at this point it will be a major change to a lot of classes.

This is an example from the book of one of the goal classes in the Raven program (Goal_NegotiateDoor.cpp) that illustrates the issue, with the author's own comments:

//because goals are *pushed* onto the front of the subgoal list they must
//be added in reverse order.

//first the goal to traverse the edge that passes through the door
AddSubgoal(new Goal_TraverseEdge(m_pOwner, m_PathEdge, m_bLastEdgeInPath));

//next, the goal that will move the bot to the beginning of the edge that
//passes through the door
AddSubgoal(new Goal_MoveToPosition(m_pOwner, m_PathEdge.Source()));

//finally, the Goal that will direct the bot to the location of the switch
AddSubgoal(new Goal_MoveToPosition(m_pOwner, posSw));

Again, I have goals that are much more complicated (and getting more so) with subgoals added depending on this or that condition. Doing everything in reverse doesn't exactly make it less complicated.
Anyways, I would like to hear if someone else has done this change or thought about it.

I went ahead and changed the Subgoals stack to a queue. Other than reversing all my previous AddSubGoal calls, which was the point, it required very few changes - Pop becomes Dequeue and Push becomes Enqueue in the .NET implementation.

If someone is following the book, I recommend making this change as soon as possible in the process - the design improves a lot.

Quote: Original post by captain_crunch
I went ahead and changed the Subgoals stack to a queue. Other than reversing all my previous AddSubGoal calls, which was the point, it required very few changes - Pop becomes Dequeue and Push becomes Enqueue in the .NET implementation.

If someone is following the book, I recommend making this change as soon as possible in the process - the design improves a lot.

And it sounds like it would be MUCH more intuitive to program/design.

Quote: Original post by ID Merlin
And it sounds like it would be MUCH more intuitive to program/design.

This does depend on what the book is trying to teach. If a 'command queue' works for you, then go with it by all means. By using a stack however, the AI can typically be considered to be an automaton/state machine (more), with each subgoal/task being a state. This may be useful for writing rules for transitions (ie adding new subgoals) depending on visited/stacked states and giving the AI a crude state of mind. For example, if the stack is (Pickup, GoToItem) and Pickup is popped but fails because the item moved away, the AI will automatically return to the state of GoToItem.

Yeah, and I'm still curious as to whether it's a recursive or a sequential system. If it really is just a case of doing one task after another, then you can do it as a queue, but if it's about tasks having subtasks, then a queue is not really the right structure. A stack, although more awkward, more closely represents the tree structure, much like a function call stack.

There may be cases that benefit from using the stack, I cannot think of any myself, but for what I am concerned with, which is coding behaviour by an AI agent, I think the design work becomes much more intuitive.
I can give you an example on designing a specific behaviour that I just finished.

An agent must must move a pile of items from one location to another. Let's say there are 4 items and the agent can only carry 3 at a time.

The intuitive way of coding this behaviour (in my view) is creating a loop where items are picked up one at a time until capacity is filled or exceeded (AddSubGoal(PickUpItem)), then exit the loop, move to the destination and drop them all before returning to the pile if there are any more.

Coding this using the queue meant that that the agent first moved 3 items, leaving 1 in the pile, then returned and moved the remaining 1 item. This is the desired behaviour that I would think corresponds with how people think and act.

Using the stack however, gave the unexpected result of the agent picking up just 1 item, leaving 3 in the pile, moving it, then returning and picking up the remaining 3...

I think the normal work process of imperative programming conflicts with the way of thinking that is required to code with the stack, creating unnecessary headaches.

First of all, you can obviously just stick with whatever works for you. I'm not advocating the stack as the perfect solution, but here are a few things to consider.

Quote: Original post by captain_crunch
Coding this using the queue meant that that the agent first moved 3 items, leaving 1 in the pile, then returned and moved the remaining 1 item. This is the desired behaviour that I would think corresponds with how people think and act.

...

Using the stack however, gave the unexpected result of the agent picking up just 1 item, leaving 3 in the pile, moving it, then returning and picking up the remaining 3

This behavior could just as well be implemented with a stack. It doesn't follow from some defect in the stack approach that it doesn't exhibit the behavior you'd like to see. A stack based approach could play out like this:

(GoToItem)               // push Pickup when the item is reached(Pickup, GoToItem)       // pop Pickup, meaning perform the action(GoToItem)               // push Pickup when the item is reached(Pickup, GoToItem)       // pop Pickup, meaning perform the action(GoToItem)               // push ReturnCargo when the cargo hold is full(ReturnCargo, GoToItem)  // pop ReturnCargo, meaning perform the action(GoToItem)               // continue item hunting

Quote: I think the normal work process of imperative programming conflicts with the way of thinking that is required to code with the stack, creating unnecessary headaches.

It may look more complicated at first, but there is no inherent conflict IMO and it does have the advantages I listed above. In addition Kylotan also pointed out recursive systems, which can prove especially useful. With recursive systems, the current state could push a new state onto the stack, making for a logical flow of actions.