Collaborative Diffusion Explanation
Traditionally
in a game each agent will have its own pathfinding routine that will be called
any time an agent needs to find a path to a specific goal state. Typically in
the majority of games this will call the A* algorithm, this works well in most
cases but as the number of agents increases the time spent pathfinding also
increases which can have a detrimental effect on the performance of the game.
To combat
this collaborative diffusions works on the idea of antiobjects, an antiobject
is a type of object that appears to do the opposite of what we would generally
think the object would be doing (Repenning, 2006) .
For example in the game Pac man (Pac-Man, 1980) the objective of each ghost is to find
Pac man. Using traditional pathfinding like A*, each ghost would run its own
pathfinding algorithm every time it needed a new path. From an object
orientation stand point this makes sense to many programmers that the
responsibility of finding a path would be down to each agent, however by
removing the computation from the objects that typically appear to do the
search, it allows the computation to be redistributed in a parallel fashion to
the objects that define the space to be searched instead.
Diffusion is a gradual
process in which physical and conceptual matter, such as molecules, heat,
light, gas, sound and ideas are spread over an N-dimensional physical or
conceptual space over time (Repenning, 2006) , within collaborative diffusion this
idea is used to transfer the scent of a goal state throughout the world in
which pathfinding will be taking place. This diffusion value is calculated
using the following equation.
Where:
D = diffusion value
n = number of neighbours
a = diffusion value of
neighbour.
Typically
the world is organised as a grid representing either a 2D or 3D environment and
each neighbour is defined according to the Moore neighbourhood (Moore Neighbourhood, 2013) which comprises of
the eight cells surrounding a central cell.
Each goal
state is given an initially high diffusion value which is used as the starting
state as shown by the green tile in Figure 2 below.
Figure 2 - starting state
During the
first iteration the diffusion value for all the tiles are calculated using the
diffusion equation. After this iteration the tiles surrounding the goal state
now have a larger diffusion value than they had initially and the ‘scent’ of
the goal state is beginning to move toward the agent as shown in Figure 3 below.
Figure 3 - Iteration one
This process
continues again for all of the tiles in the world during the next iteration, as
the diffusion value is calculated again for all the tiles it begins to spread
out further from the goal state expanding the ‘scent’ of the goal further
across the grid and towards the agent. During this iteration the diffusion
value of the tiles surrounding the goal state becomes larger making the goal
state appear more attractive to an agent. This second iteration is shown in Figure 4 below.
Figure 4 - Iteration two
At each
iteration the diffusion process repeats expanding further and further outwards
across the tiles. Eventually the ‘scent’ produced by the tiles will reach an
agent at which point a path can be found to the goal state.
Once the
‘scent’ has reached the agent, it is possible for a path to the goal state to
be found, unlike pathfinding algorithms like A* which use a back tracking
algorithm to find a path from the starting state to the goal state all the
agent simply has to do is look up the diffusion values of the tiles
neighbouring the tile it is currently on and move to whichever one has the
highest diffusion value.
As shown in Figure 5 during the third iteration our agent
is able to pick up the ‘scent’ of the goal state, by simply moving to the
neighbour with the highest diffusion value our agent is able to find the
quickest path to the goal as represented by the green tiles.
Collaborative
diffusion allows agents to collaborate together to complete objectives in a
very simple manner. In his paper collaborative diffusion: programming
antiobjects, Alexander Repenning states that there are four different types of
agents that allow collaboration to occur:
- 1 Goal Agents: Goal agents are pursued by other agents and can be either static or mobile.
- 2 Pursuer Agents: A pursuer agents is an agent that is interested in one or more of the goal agents. Multiple pursuer agents may be interested in the same goal and may collaborate or compete with one another.
- 3 Path Environment Agents: A path environment agent allows pursuer agents to move towards a goal agent and participates computationally in the diffusion process. In a simple arcade game this could be a floor tile in a maze.
- 4 Obstacle Environment Agents: Work in a similar manner to path environment agents but rather than helping an agent to reach the goal they interfere with the agents attempt to reach a goal. This could be represented by a wall or obstacle in a room.
Making use
of these different types of agents Repenning noticed that agents would appear
to collaborate with one another to reach a goal. He also states that the
collaboration between the agents is an emergent behaviour as no code is
explicitly responsible for orchestrating a group of agents but is instead a
result of the diffusion process and the way in which pursuer agents find a path
to goal agents through the path environment agents. Another interesting
observation by Repenning is that as the number of agents is increased the time
taken to perform the pathfinding remains constant (Repenning, 2006) .
Bibliography
Pac-Man.
(1980). Retrieved October 26, 2013, from Pac-Man:
http://pacman.com/en/pac-man-history/
Repenning, A. (2006). Collaborative Diffusion:
Programming Antiobjects. Boulder: University of Colorado.
No comments:
Post a Comment