Tribes

Current Issues

Today we have fixed spawn points for NPCs and some simple paths used to move the NPCs around. Let’s analyze the issues of this approach:
  • It’s very time-consuming to place npcs in world nicely.
  • World is not responsive to player actions or lack thereof, static npc grounds lead to player camping and general apathy, loss of immersion and suspension of disbelief.
  • No element of surprise or discovery when logging in again after significant time away.
  • NPCs act individually with no ability to communicate information or orders in an effective way.
  • Perceptions are permanently tied to adjust the same behaviour, e.g. when a NPC is attacked it will always respond by either attacking back or continuing its current behaviour rather than varying the response based on the health of the attacker. This leads to robotic like and reflexive behaviour.
  • Script parameters are also only adjustable by hand so although there is a number of NPCTypes that are defined, every NPC with that type will act in exactly the same manner.
  • No sense of evolution or progress for the creatures found.

Goals of the Tribes system

The main goal of the new system is to solve the above issues and in particular:
  1. The world should run more as a 'simulation' so that things are happening/changing whether players are around or not. If areas are ignored by players, npc population grows and npc's even compete with each other for good spots. Obviously if the players are not there, the server can use shortcuts and calculate progression only when a player visits the location, or regularly, example every hour.
  2. NPCs should have a concept of a “tribe” they should know they belong to a group of people and contribute to the growth of this group.
  3. NPCs should be able to find resources, build huts, houses and then villages if intelligent, mate, have children, build defenses, grow in wealth and number, attack other tribes, etc.
  4. Players need to team up to keep certain areas cleared of bad guys, so teamwork and organization are required to keep the game somewhat orderly.

The goal of this system is to provide a basis of realistic behaviour for NPCs based on daily tasks assigned to it by the tribal object yet still retain the individuality of its race or type. The communication must be two-way, members can send requests or information to the tribal object for help or if they suspect an invasion for example. So for example, a tribe could consist of both humans and krans, the tribal object assigning the krans the task of patrolling and defence while the humans act as resource gatherers and explorers. The tribal object has a set of needs similar to every normal NPC but acts on them in a more dynamic manner and NPCs should be able to alter their own behaviours and adapt them to the situation.

Building blocks

To have our goals achieved we need a number of building blocks, listed below.

A) NPC movement

To bring the NPCs to life they should have a basic set of actions available at their disposal. Actions will be managed by AI objects or simple triggers depending on occasions.

NPCs should be able to:
  1. Move “Home”. A recognized place that’s the current home village or nest where they bring resources.
  2. Move along predefined paths.
  3. Wander with region radius around “Home” while waiting for more important orders.
  4. Execute some random actions like sitting down for resting, looking around, waiting few seconds.
  5. React to other NPCs nearby and stop walking to look at the nearby creature (just for few seconds, then restart walking).

B) Natural Resources

Natural resources are a critical part of the evolution of a tribe. This is the list of what must be available to dig, harvest, search :

  1. Food, like mushrooms, apples, fishes, crops, etc… – required by the tribe for growth, not needed for maintenance of tribe (like it’s for players).
  2. Building materials – required by the tribe to support expansion, a small population can survive without the need for a distinguishable home but a large one cannot.
  3. Raw materials – used by the tribe to craft and trade allowing it to actively participate in the economy, increase wealth, tools quality, weapons. These are the actions needed for NPC to use natural resources:
  4. Dig or search for resources along the movement paths
  5. Know which tool is needed for digging/harvesting
  6. Remember a location when they find a resource
  7. See objects that lie on the ground, so can be picked up

C) The Tribe and the individual Objects

All individuals belonging to a tribe will be managed by an instance of an object called the “Tribal Object”. The tribal object evaluates the circumstances and conditions of the tribe and thus identifies a goal to realise its need. It then sends suggestions to every member it is aware of to update their actions. In this way, the tribal object reflects the long-term needs and goals of the tribe in each of the members goals and objects. The matching of goals to members controlled by the tribal object enables each member to be assigned a different overarching task while still retaining its individuality through its own scripts. Our tribal behaviour aims to follow these rules:
  1. Unity: Members should act towards a common goal, no one member may act against it.
  2. Predictability: It must be possible to explain any tribal action in the overall scheme of things, ie. a tribe won’t attack another one because it felt like doing so while it has a major crisis going on
  3. Goals :The goals of the tribe should reflect the majority view of its members.

To achieve the above the tribal objects needs:
  1. Be seeded by a table storing all the tribes (for now managed by setting team, in the future it will auto-seed itself)
  2. Keep a list of its members – minimum 1 member or the tribe has to restart from the seed. Members can be categorized based on their skills:
    • Fighters – equipped with a variety of weapons to suit their tasks be it patrolling or raiding
    • Support – primarily spellcasters, which aid the fighters and provide assistance to non-combat minions
    • Explorers – discover new resources
    • Gatherers – pickup resources once discovered
  3. Keep a list of goals with priorities. The goal with the highest priority will be executed. After successful completion of a goal this priority will be lowered, so other goals will be executed. Possible goals for now are:
    • Grow in number (mate)
    • Build/enhance village size or quality
    • Gain wealth
    • Expand non aggressively (if other tribes are found, they stop) e. Expand aggressively (if other tribes are found, attack)
  4. Be able to evaluate what’s needed to accomplish a goal, splitting it into subtasks.
  5. Be able to give the subtasks to members to achieve the goal. For example if goal is grow in number, it should send input to members to seek food, then to build houses, then to mate.
  6. Be able to spawn a new member based on a sample formula triggered by “grow in number” goal.
  7. Keep a list of houses/buildings owned by the tribe
  8. Keep a list of resources owned by the tribe. Those are the ones that are “dropped” at “Home” by the members of the tribe. For now it’s not very important that we have a real building at “Home”, can be just a spot in the map. We will place a building there as soon as we can spawn buildings.
  9. Keep track of passing of time since tribe inception, so it can spawn special events, like ritual dance once a year, or great sleep every winter.
Based on the current 'score' of resources available, their max population can be determined, and we can spawn gradually to that number, which would affect their wander radius and thus affect their resource availability more. For intelligent races, things like 'huts' can be spawned as standard game objects as a function of # of people in the tribe.

Implementation detail

Tribe Types


The PALSAO should be aware of the type of tribe he is managing, because not all tribes will have the same goals, and the same possibilities. For example a tribe of “hydlaa city guards” will have no plans of expansion, no need for new resources, and they will reproduce just by having a new rookie guard sent by the central command. A gobble tribe will have need to consider food resources, to reproduce, explore and expand creating new villages.

The Evolution of the tribe

Apart from the events that will change the course of actions of the tribe (e.g.: players attacking or a plague spreading), the tribal object should have a predefined evolution path, that will guide actions if nothing special happens. Based on the tribe intelligence, it may seek only food and peace, or also expansion and money, it can seek other villages to attack, and decide to build and research better buildings. The standard path should take into account the “Tribe Type” described above and usually go toward expansion of territory, wealth and members number.

Paths

We already have a number of predefined paths used to move NPCs around our world. It’s important that the EDLO identifies those paths and use them to seek places where the NPC can fulfill its objectives. For example we have a path to go to work, another to go to rest, we will have some to go outside the city where the NPC can start seeking new resources to dig. We have to define which attributes each path has, so that all EDLOs in game can use the paths present. There will be some paths specific of an NPC, like the road that goes from blacksmith shop to the house of Harnquist (used only by harnquist), and paths that can be commonly used by all NPCs, like the path that brings from hydlaa plaza to the Kada-El tavern.

Adaptive Tribal Behaviour

The tribal object holds an incomplete view of the world in terms of its resources but knows the precise location of all its members to allow planning to be significantly simplified. It will hold a set of needs and perceptions, perceptions are triggered by communication from its members or from the environment. During everyday operation, the object distributes tasks in proportion to the status of its needs during that day. During an exceptional operation, such as an enemy stealing all of its food stocks, the need the exception corresponds to is raised to a critical level.

At this stage the object utilises a partial order planner not only to fulfil its objective but to allow behaviour to vary in an unpredictable fashion. The planner is passed the initial state of the tribe and aims to get to a goal state where all of its needs are satisfactorily fulfilled. It has access to a tribal rulebase, tailored to each tribe that contains a set of rules. Each rule has a precondition that must exist for the rule to be run and an effect which is what the effect of running that rule will be.

For example, a tribe of humans have experienced a heavy attack by an enemy where most of its members have been wiped out their states are both:

Food = 1.0 Population = 0.1 Security = 0.01 Money = 0.1

The following set of actions is planned from the human rulebase:

Time 0: Precondition: None Action: Order members to chop wood Effect: Wood +0.2

Time 1: Precondition: Wood > 1.0 Action: Order members to sell wood Effect: Money +0.1

Time 1: Precondition: Food < 2.0 Action: Buy food Effect: Food +1.0 Money -1.0

Time 2: Precondition: Food > 2.5 Action: Reproduce Effect: Population +1.0 Food -1.0

So by 3 days after the attack the humans will be back to their full population. This can be viewed as a series of actions and their associated transformations but is structured in a way that behaviour can be significantly altered through altering or adding a few rules. So for the Ynnwn the action to obtain wood might be to raid and plunder a neighbouring village. As we gradually add more capabilities to tribes it would be very easy to add further rules to the rulebase and the tribe’s behaviour able to adapt quickly as a result. If at any stage things don’t go according to plan, the tribal object would also be able to easily create a new plan that suits new circumstances but will still have a solid idea of what it wants to achieve. Rules can also be shrunk down to menial tasks for precise control for example getting three members together to build a bridge across a river to reach a new area.

Individual members will contribute to the needs of a group and can communicate basic information to it such as sightings of enemies or resources.

Dynamic Scripting

Another element of tribal behaviour is adaptability to tactics and strategies enforced by players. For now, only short-term combat is considered in which a tribal member skilled in a variety of melee techniques and spells comes up against an aggressor. Dynamic scripting, in essence creates a combat script from rules in the rulebase each of which has a weight assigned and a set of conditions to execute.

Each set of weights is unique to each type of aggressor, so there would be one set that a npc uses against a Ynnwn fighter and one against a Enki spellcaster. After each encounter the weights of the rules can then be adjusted according to the effectiveness it had in combat. In this way, the NPC would gradually adapt its tactics against the player’s, which is absolutely required for a challenging NPC in a spell-casting environment. These are just my initial thoughts on this…

Conclusion

Through the main technologies of partial order planning and dynamic scripting I believe NPCs will be able to behave significantly more realistic than before with a minimum amount of new code and scripts. The whole system will be tailored exactly to the rules that are set up which will govern the rate of change of needs as well. From my research, these techniques have never been used in a massively-multiplayer game before and it will definitely be interesting seeing them work on such a scale.

References Artificial Intelligence in Games (2002):
http://www.cs.rochester.edu/u/brown/242/assts/termprojs/games.pdf

Adaptive Game AI (2005) http://www.cs.unimaas.nl/p.spronck/Pubs/ThesisSpronck.pdf

Machine Learning in Computer Games (2004) http://www.cse.lehigh.edu/~munoz/CSE497/classes/LearningMarc.ppt