4
\$\begingroup\$

I am currently developing a nations / factions simulator on a map with in-depth resource system, population system, important characters system.. and this is where I finally met a real obstacle.

You see, I wish to give important characters a set of actions which their AI will use to achieve goals, goals that will depend on their character type. For example, an important character who spawns because he leads a migration wave will have two goals : to keep himself and his party alive and to reach his destination and start a new "population node" there. Another example : warlords could seek to increase their "power" variable by making plans to get ahead of other warlords through simple actions like giving money to a local lord to help develop his land, etc.. this would take very long to describe in great detail.

As you can see, or at least as I see it, the best AI architecture for this kind of behavior would be a Goal Oriented AI : it would allow me to keep expanding the set of actions characters have to advance their interest and at the same time allow me to easily create new types of important characters.

I have done quite a lot of research, and most of the sources I found explain the same thing clearly, which I understood : GOAP is about having a starting "world state" and through a "path" of actions, get to a desired world state called a "goal".

The thing I couldn't understand is how exactly you can achieve this with actions other than actions which do not require any parameters. I could implement a basic system right now, I think, provided actions can fully run by themself with no external information, and more importantly no knowledge of eachother, because that would break the point of the whole system I believe.

The articles talk about that very vaguely. I've read about a "blackboard" system where information like what is the current target, where to move.. can be stored. But while planning how do you use this ? Where does that information come from ? How do you associate it with "world state" key-value pairs ?

Finally, I found that some people solve this problem, or at least solve it for the movement, by making a FSM over the GOAP, where one of the state is "moving" and the other one is, basically "GOAP". But I do not think this is the best approach and more importantly I'd like not to go with a hybrid if I can.

So if someone would be kind enough to explain the basic concepts of implementing a Goal oriented AI, or at least help me deal with actions that require a parameter, I'd be extremely grateful. If you want me to expand this wall of text I can provide more detail, simply ask.

PS : I use Unity, coding in C# exclusively.

\$\endgroup\$
6
\$\begingroup\$

Planning

You have a world that has some state, and the agents can do actions that affect that state. Now, you can think of the world state as a node, and the actions are the links.

You would not have a graph with all the possible game states. Instead you should express your actions as pre-conditions (needed to be able to do the action) effects (that you should be able to apply to the world state to be able to compute the new state) and some cost (in time or resources).

Then the goals are predicates you should be able to check about the world state (for a given world state, the goal has been met or not). As you can see, the actions have pre-conditions that are basically the same thing. This means that you can model the goal as an action (having the effect of "the AI wins").

What follows is planning. There are two approaches:

Forward Searching

The idea is that you need to find a path (a series of actions) that will take the current world state to a world state that satisfies the goals. You do this by pathfinding.

As you know, when pathfinding you can have a heuristic to provide priorities over the different branches you search... that heuristic could be a measurement of the progress towards a goal (you may expand this idea to include the risk of moving away from the goal, perhaps as an estimate of enemy treats).

Now, you can search the action space for a path that will lead you to the goal state. Or, perhaps you could just plan a few steps by finding the path that would take you closer to the goals in those steps, this way keeping the time dedicated to AI short.

Note: As I said above, you don't have a graph will all the possible states of the game. Instead you would generate the game states that the AI explores as it does it. If you give a look to the pseudo code for A* Search Algorithm or for Dijkstra's algorithm you'll see that you only need to persist the actions, not the states. This also allows you to search an infinite state machine.

Backtracking

Here you start with the goal, you attempt to do it as an action and you find you need to meet some condition first. Then you look at the other actions and see what actions may lead to that, etc... until you reach an action that can be performed right away (that is an action to which the current world state satisfies its pre-condition).

As you can see, this is also searching, except you start by the end. Backtracking works better with simple abstract scenarios, but it may not work for open ended games because reaching the goals may be too far away that it takes too long for the AI to start doing any actions.


Abstractions

The world representation that the AI sees doesn't need details. The idea is to move code away from the predicates. For example one possible action is to shoot an enemy; its pre-conditions would be to have a ranged weapon, with enough ammo, and for there to be a nearby visible enemy. You don't want to have to write in the predicate the logic to find nearby objects, line of sight checks, etc... This would be abstracted by the code that creates the world representation with which the AI works. A subsystem will then deal with the details of changing weapon, aiming and shooting.

Another thing you can do is to find interchangeable objects. If something can be done with object A or with object B to similar results, the AI doesn't need to be concerned with it. Instead a subsystem can deal with the details. For example in some combat video games the AI doesn't have the responsibility of choosing kick vs punch. Instead another subsystem can check the collision boxes, the damage of each option, and whatever or not they can be chained in a combo to decide what attack to do. The AI will then worry about being offensive or defensive, going for ranged attacks or close combat and predicting player moves to dodge, block or counter.

Another technique you can apply is to bookmark zones and choke points that are important to control. This will allow you to provide the AI with a discrete list of locations instead of having to deal with coordinates. Then a subsystem dealing with formation and pathfinding will decide exactly where to go.

Note on large maps

You will want to keep a structure that allows you to query nearby objects (this is useful for other things), using that structure you will be able to limit the representation of the world state used by the AI to the immediate surroundings of the objects it controls. This will keep the AI performance regardless of the size of the map.


Predicting other agents

Of course there are multiple agents in the game, and there is no way an agent will know what another agent will do (unless they share information). You can approach this by implementing game theory: the agent considers the possible moves the other agents may do and picks what’s best across all the possibilities.

In order to keep things simple you may consider making each agent predict what is best for each other agent according to your AI (similar to MinMax) but with only the information available to the agent doing the prediction.

To predict players, you can represent them as probabilities. To give value to those probabilities you can use the frequency with which the user does an action, is seen in a given location, or uses some item. For the locations you may want to annotate the frequency in the map. Since you are keeping your AI isolated, you would make a separate representation of each player for each AI agent.


Randomness

So far the AI is deterministic, therefore predictable…

A simple way to do is, is having using random to have the AI pick unnecessary actions or actions that nonetheless have some reward for the AI agents, or by taking a suboptimal approach to reach the goal. This may provide a more interesting gameplay, more replay value, and the benefits of the unnecessary action may help the AI to find alternative solutions when their plans fail.

\$\endgroup\$
  • \$\begingroup\$ Dang ! Thanks a bunch mate. I'll get to reading this wall of text you took the time to write for me. \$\endgroup\$ – Marc Jacob Feb 5 '17 at 9:00
  • 1
    \$\begingroup\$ Read it, very interesting and helpful. The "Abstractions" part interested me the most, but not sure I understand it fully. So basically, for example, instead of trying to go for a plan like "MoveToCoordinates(whatever) -> DoActionOn(TargetObject) -> MoveToCoordinates(whatever) .." I should go for "MoveToTarget -> DoActionOnObject -> MoveToTarget" and let a subsystem deal with what is the target location every time and what is the target object ? \$\endgroup\$ – Marc Jacob Feb 5 '17 at 9:09
  • \$\begingroup\$ @MarcJacob That's the idea. To expand on that: Consider the set of action not fixed, since your pathfiding will have to see what actions can be done you may have a routine to discover the actions. Following the example of the Sims (look for articles about The Sims AI): your code may look to nearby objects, bookmark those that are relevant. Then query the bookmarket objects for actions, that give you your set of actions. About bookmarking locations, I'd suggest to play Globulation 2 (its free) it will make the idea clearer. \$\endgroup\$ – Theraot Feb 5 '17 at 20:53
  • \$\begingroup\$ I see, thank you for your help, it is invaluable. For now I think I understand everything, I'll ask more questions here whenever it's not the case anymore. \$\endgroup\$ – Marc Jacob Feb 5 '17 at 22:15

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.