Pathfinding Using Collaborative Diffusion

For my honours project this year at university i am aiming to compare pathfinding algorithms on the GPU, One of the algorithms i have chosen to compare is collaborative diffusion so i have implemented a simple application in which agents seek out food items within a maze using the collaborative diffusion algorithm to find the quickest path to the nearest item. The yellow cubes represent the agents, green spheres are food objects and orange cubes are walls which are impassable.

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.

Figure 5 - Iteration 3, path to goal is found

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).

By its very nature collaborative diffusion lends itself very well to a data parallel implementation on the GPU, as the GPU works by splitting the work across a number of threads and having each thread perform the same task it should be more than possible to split the work of the tiles across a number of threads as each tile performs the same diffusion calculation.

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.