Hi community, I'm working on a small game in Java and I've reached the point where I have to think about AI. The game consists of a grid based map, for instance 100x100 tiles, and there are soldiers on them. They have a current facing, a limited arc of view, a certain action speed and they already know how to find a path to a destination. Also, there will be zones, i.e. an overlay to the map that can tell the AI whether there is a building, who controls it etc. I was contemplating to equip each soldier with an AI object that will control it. This AI class handles tasks, for instance "patrol on entire map", "guard building at x, x", "collect mineral x", "reequip armanents", "build sand bags at zone x". Since these tasks require different kinds of parameters, I'm asking myself on how to do this elegantly? The container for these tasks would be a Vector<Task> probably, but how on Earth can class Task be designed in order to be able to contain all the info for all possible tasks? I thought maybe one of you guys has a bright idea.

Why don't you make class Task an abstract one and use subclasses of it to define each specific task. You can still store this in a Vector<Task> then.

The abstract class could contain stuff as the expected duration of the job, whether the soldier can leave it temporarily, etc.

I would have thought there would be subclasses of Task, eg one for Patrol, one for Guard, one for Collect Minerals, etc. Each one has whichever parameters are relevant to that type of task. But how you make use of this, and indeed whether this entire Task system is of any use, depends on what you hope the Tasks are going to do. And why do you need a container of such Tasks? Why don't soldiers own their current Task rather than the other way around?

The problem I see with having subclasses of Task is that I would need a method for each one to be processed. I.e. PatrolTask needs a processPatrolTask() in order to read and change the right parameters. It would definitely work, but I have a strange feeling whether this really is an elegant solution.

@Kylotan: The container is contained within the AI object of the unit, thus the soldier actually does own his tasks. That's what I was trying to say.

I'm not sure what exactly you mean by "depends on what you hope the Tasks are going to do", but I'll try to explain away:

I was hoping to be able to create a unit with a base task that always remains, i.e. patrolling. It then starts wandering about, looking for enemies. If it encounters any enemies, it'll add a "Attack enemies" task on top, processing it until there are either no enemies left in sight (-> delete attack task and thus returning to patrol), out of ammo (-> run for replenishment) or badly hurt (-> flee home).

Quote: Original post by hypno_
I was hoping to be able to create a unit with a base task that always remains, i.e. patrolling. It then starts wandering about, looking for enemies. If it encounters any enemies, it'll add a "Attack enemies" task on top, processing it until there are either no enemies left in sight (-> delete attack task and thus returning to patrol), out of ammo (-> run for replenishment) or badly hurt (-> flee home).

Then give every soldier a stack on which you push the base task to begin with. When he sees an enemy, push an attack action on it and, once he decides to not follow it any longer, pop it off the stack and call the resume function of the base task.

As to the methods, give it a blank methods "process()" and "resume()" in the abstract class and overload it in every subclass. So you can call it by the same name when handling the stack.

I'd approach this using a finite state machine, since each task can be associated with a behavioural state of a soldier.

Quote: Original post by Timkin
I'd approach this using a finite state machine, since each task can be associated with a behavioural state of a soldier.

Good idea, however judging from the way I see it, that would render the soldiers unable to "remember" what they were doing before they were interrupted. I would very much like to give the player the ability to issue orders to allied soldiers, for instance to "build sand bags at location x, x". The soldier will do as told until he encounters a threat. He then fights it and returns to his original task. I guess it has to be a combination between a stack and a FSM.

Well, then give each task class a finite state machine and have it remember the state it was in the moment you pushed a new task on top of it. So when you pop it off again, your resume-function of the task sets the soldier into the state he was in when he left the task.

The solution is exactly as Sleep describes. By storing information in the state machine class owned by each soldier as to its current state and previous state, you can easily handle reverting behaviour when a task is complete.

I would take it a step further though by including a test before reverting state to determine whether it is appropriate to do so.

My preference for an OO state machine is based around a class heirarchy for states, each implementing a simple derived interface: OnEnter, OnEvent, OnExit. The logic for state transitions is encoded in the OnEvent function of each state (so this is where you would test for which state to switch to, which might include reverting to the previous state). The OnEnter and OnExit functions activate and deactivate (respectively) the various behaviours that are relevant to that state.

There are, of course, many other ways to implement a state machine and I make no claims that my way is the best (but I could probably safely say it's not the worst)! ;)

Cheers,

Timkin

Quote: Original post by hypno_
I was hoping to be able to create a unit with a base task that always remains, i.e. patrolling. It then starts wandering about, looking for enemies. If it encounters any enemies, it'll add a "Attack enemies" task on top, processing it until there are either no enemies left in sight (-> delete attack task and thus returning to patrol), out of ammo (-> run for replenishment) or badly hurt (-> flee home).

This could be done with a prioritized to-do list, also known as a priority queue.

Assign Task<Patrol> a low priority, and throw it in the to-do list for every new soldier. Then if something more important comes along, for instance a captain unit orders sandbags at zone x, add Task<Sandbag(x)> to the soldier's queue with a higher priority. Maybe Captain's Orders has a priority of 2. And if an immediate threat is discovered, add a task AnalyzeThreat with a high priority.

Analyze threat would decide whether to attack, call for re-inforcements, or retreat. Once it picks one, it adds Task<Attack(target)> or Task<CallReinforceZone(x)> or Task<Retreat> to that soldier's to-do list.

The task CallReinforceZone(x) requires an additional design pattern, a method for communicating between troops. A good one for this is Contract/Bid design, where the soldier posts a contract (kill 3 tanks -- 30hp, zone x, within 15 seconds, priority 4). Other soldiers can examine the contract board, and bid their firepower and time to target (if not currently engaged in a higher priority task). Then when the contracter's turn comes around again, he can determine if it's possible, and accept all the bids necessary to make it happen.

[Edited by - AngleWyrm on February 19, 2008 12:24:42 AM]