NAIL122 AI for Games�Game AI Design Crash Course 2��Peter Guba

Faculty of Mathematics and Physics

Charles University

​

Source: http://www.gameaipro.com/GameAIProOnlineEdition2021/GameAIProOnlineEdition2021_Chapter12_Squad_Coordination_in_Days_Gone.pdf

​

Problem

• Open-world RPG

​

• Enemies grouped into squads

​

• Different enemy groups can fight one another

​

• The player can also join in

​

• What should NPC squad behaviour look like? How should it be implemented?

Original solution

• A confidence value is computed for every member

​

​

​

​

​

• x=unit to compute for, s=strength, c=confidence, F=friend, E=enemy, K=kills, L=losses

​

• A squad’s confidence is the average of its members’

​

• This determines behaviour (push on, hold ground, retreat, etc.)

“(The formula) has a self-reinforcing effect allowing a few confident characters to rally their Squad, while a few characters losing Confidence has the opposite effect, causing their allies to lose Confidence as well. Conversely, seeing your enemy falter will boost your own Confidence, while enemies that are confident in their imminent victory will make you think twice.”

Original solution

• NPC positions and movements are guided using a Frontline object

​

• This describes the spatial relationships between squads engaged in combat

​

Original solution

• The space is partitioned into three areas using the “centres of gravity” (average positions) of the two teams

​

• The neutral area extends a fixed length from the closest enemy

Original solution

• The space is further divided into equally wide lanes, one for each squad member

​

Original solution

• All of this is used to properly position and move the NPCs

​

• They can be in one of 4 states:
• Forming up
• Holding ground
• Pressing charge
• Retreating

​

​

​

Original solution

• The player affects the frontline as well

​

• If the AI’s only enemy is the player, his position is considered the “centre of gravity”

​

• To mitigate rapid changes to the frontline when the player charges, it only changes while they stop moving

​

​

​

​

​

Source: https://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter24_Being_Where_It_Counts_Telling_Paragon_Bots_Where_to_Go.pdf

Problem

• Third-person MOBA

​

• Standard map layout – 3 lanes, towers, minions, bases

​

• Special structures/regions – XP wells, jungle with NPCs, etc.

​

• Each hero has unique abilities

​

• How should the AI bots strategize in a team consisting only of AIs? And how when some teammates are players?

Original solution

• Create a graph where nodes are strategically important places (bases, towers, XP wells, vantage points, good places for an ambush, etc.)

​

• Edges represent paths between places

​

• These can be generated automatically with some fine tuning done by hand

​

Original solution

• At runtime, the graph is updated with data about the “influence” of enemy heroes and minions (their influence is only confined to their lane)

​

• Using this information, one can find paths that satisfy different objectives (avoid enemy, seek out enemy, stick to one lane, etc.)

​

• Pathfinding can be done hierarchically (find high-level graph path, then refine every segment)

​

​

Original solution

• Key idea – adding objectives to nodes (hence the name Objective graph)

​

• Objectives tell agents where to go and what to do once they get there

​

• Examples: attack, defend, get XP

​

• All information about which agents can satisfy an objective, how many are necessary and how they do it is contained within the objective

​

​

Original solution

• Objectives are generated at the start of a match, but may be dormant (for example there is no need to defend a structure that has full health and isn’t being attacked)

​

• They get assigned priorities at runtime

​

• This takes into account things like objective type, location, enemy influence in the area, etc.

​

​

Original solution

• An AI Commander assigns objectives to agents
• Each objective picks its state (Dormant or Active)
• Priorities for the objectives are calculated
• Each objective goes through all members of the team, filters them and scores them
• Objectives are assigned
• Find the highest priority objective
• The objective gets to pick a minimum set of agents of given types it needs
• Its priority gets decreased

​

• When navigating the world, an agent can also query all graph nodes it passes through for objectives that it could fulfil

​

• Objectives internally decide whether they want to be assigned then

Original solution

• When a team is partially comprised of humans, these are treated the same way as AI agents (i.e. they also get assigned objectives)

​

• The assumption is that players will behave reasonably and that the AI Commander can pick reasonable goals for all team members – therefore players should fulfil its goals without being explicitly made to do so

​

• There is also an on-screen textual communication system which can be used to request that the player do something, like defend a certain structure

​

​

“As proven by our internal user experience tests, the introduction of a strategy layer to the Paragon bot AI greatly improved players’ experiences. The game did not instantly become harder, because no behavioral changes have been made to the bots’ individual behaviors, but users did notice the game being more interesting.”

“Bots started showing signs of a deeper strategic understanding of the game: filling in for fallen comrades, switching lanes, attacking enemy harvesters, and even [ambushing], although the latter behavior was entirely emergent. Players will generate their own explanations for what is going on in the game as long as the AI is doing its job well enough!”

Sources: https://www.youtube.com/watch?v=9RRjM1yNvy4

https://www.guerrilla-games.com/media/News/Files/Putting%20the%20AI%20back%20into%20Air.pptx

Problem

• Open-world RPG

​

• Enemies are machines inspired by various animals

​

• Some (Glinthawk and Stormbird) can fly

​

• How to handle their navigation through air and make them seem natural? How to handle landing or crashing down after being killed?

Original solution

• Full 3D navigation can be quite expensive, unless your representation of space if very sparse

​

• Instead, height maps can be easily utilized to handle collision queries

​

• One height per map cell => no flying under arches, rock outcrops, etc. – in the world of Horizon: Zero Dawn, that isn’t too much of an issue

​

• Height maps are generated at runtime

​

• Agents have a sphere around them within which the height maps are generated

Original solution

• Pathfinding done using 2D A*

​

• Height is changed is necessary, but flying up is penalized (if an agent needs to fly higher to reach a certain cell, the cost is Euclidian XYZ distance, for others it’s just Euclidian XY), while flying down isn’t

​

• Just using A* led to performance issues, as, with few obstacles, there were lots of equally good paths

Original solution

• Solution: hierarchical path planning over mipmaps

​

• Heightmaps are generated at multiple levels of detail (this necessitated ~33% more memory, which was acceptable)

​

• Pathfinding is first performed at the highest level, then the path is progressively refined

​

• Raycasts are used to find straight paths between points (if there’s no hit, the creature can fly straight, if there is, split the path in the middle and repeat for both segments)

​

• A limited number of A* iterations is allowed per query (path is refined until these are used up)

​

Original solution

• Path following implemented using simple physics

​

• Each creature has a velocity, angular velocity, acceleration and angular acceleration

​

• The acceleration vector is dynamically changed in such a way as to follow the path as closely as possible

​

​

​

​

​

Original solution

• Collision avoidance between creatures while in the air is ignored – the player doesn’t really notice two creatures flying through one another

​

• When landing, candidate positions on the navmesh are generated (these can be anywhere in principle)

​

• When crashing, the same process is applied, except the generated positions have to be in the direction of the creature’s velocity

​

​

Sources: https://youtu.be/km_DYozYh54

https://ubm-twvideo01.s3.amazonaws.com/o1/vault/gdc2012/slides/Programming%20Track/Fauerby_Kasper_CrowdsInHitman.pdf

Problem

• Open-world RPG

​

• Large crowds (>1000 characters)

​

• NPCs have to walk around and react to some of the player’s actions

​

• Individual NPCs are capable of more complex behaviours

​

• How to efficiently simulate crowd behaviour and also allow each NPC to exhibit more complex behaviour when needed?

Original solution

• A reasoning grid is overlayed on the navmesh to help with navigation

​

• Each cell has a walkable/unwalkable flag, various annotations (exclusion zones, ambient flow vectors, etc.) and keeps track of the agents currently within its borders

​

Original solution

• The navigation process involves lots of neighbourhood searches and comparisons of NPC attributes

​

• Memory trick – divide NPC attributes to core and others, store all cores in a single chunk of memory (this results in less cache misses)

​

• Cell attributes are stored in arrays (1 per attribute) – this is again more memory efficient

​

​

Original solution

• The AI of crowd NPCs a basically an FSM

​

• 3 navigation states – Idle, Pending walk, Walk

​

• Other gameplay states – Alert, Dead, Prone, etc.

​

• Every game frame, every agent determines whether it should change its state

​

• When panicked, the agents try to follow panic flows, which are computed when the grid is generated – these contain the direction to the nearest exit and the cost to reach it

​

Original solution

• When the player does something that should affect the behaviours of agents around them, behaviour zones are created to communicate this

​

​

Original solution

• NPCs can be “possessed” by behaviour trees when the player tries to interact with them specifically, which makes their behaviour more complex

​

​

Sources: https://www.youtube.com/watch?v=9gf2MT-IOsg

https://www.youtube.com/watch?v=YjuOSgPdtS0

https://www.youtube.com/watch?v=DVMs5_B611E

http://robert.zubek.net/publications/Needs-based-AI-draft.pdf

Problem

• Social simulation game

​

• The player can control various characters

​

• The NPCs have to act autonomously when the player isn’t controlling them

​

• They have to have a wide range of possible behaviours and personalities

​

• How to ensure variability and also that the characters can behave autonomously in a way that makes sense and is in line with the player’s previous actions?

Original solution

• Sims have needs/motives (hunger, social, bladder, etc.)

​

• These have metres associated with them which decay over time

​

• Objects (including the Sims themselves) advertise what needs they can satisfy

​

• When deciding what to do, an NPC probes its surroundings for available actions, then scores them based on its needs and picks one

​

• They won’t necessarily pick the best one (which makes them less predictable and means they can’t satisfy their needs perfectly, giving the player something to do)

Original solution

• Different weights can be used for different needs to achieve more realistic behaviour

​

​

​

​

​

​

​

​

​

​

• Weights based on other things can also be applied (distance, character traits, etc.)

Original solution

• Different weights can be used for different needs to achieve more realistic behaviour

​

​

​

​

​

​

​

​

​

​

• Weights based on other things can also be applied (distance, character traits, etc.)

Original solution

• The town also has needs (such as employment rate and gender balance)

​

• It can satisfy these needs by generating life events for Sims

​

• Some specific places (e.g. restaurants) also have needs (number of people inside) which they can fulfil by giving new motives (eat outside) to nearby Sims

​

​

Original solution

• Sims’ personalities are defined using traits

​

• These can unlock specific actions and give additional needs as well as adding flourishes to the way they walk, idle, look, etc.

​

• Adding and removing needs can also be used to adjust behaviour in various situations (e.g. when visiting someone, the Sim can be incentivised to behave more properly)

​

Original solution

• Social situations still need a more fine-tuning by hand to seem believable

​

• The Sims uses production rules for this

​

• These are ranked by specificity and the most specific one is applied

​

• There are 1000s of these in Sims 3

​

​

Original solution

• The lives of Sims that aren’t visible have very simplified simulations

​

• Predefined curves are used to compute the values of their needs when the player next sees them

​

• Important life events (e.g. getting a job, getting married) are generated for them once in a while

Original solution

• The Sims shouldn’t break the story that the player is trying to tell

​

• To achieve this, there are many so-called ‘autonomous feedback loops’

​

• Player commands a Sim to do something -> this modifies their internal preferences -> they are more likely to behave the same way in the future

​

​

That’s it for today!