THESIS: Path Finding with Influence Maps, Occupancy Maps and Potential Fields

Overview: 

Thesis is sub-divided to 3 major areas:

  • Pathfinding with Influence maps:

  • Use of Potential fields in games:

  • AI using Occupancy maps to find player:

Theory: 

Occupancy Maps:

Using occupancy maps is a probabilistic approach used by AI in games to find a player whenever the AI loses track of a player.​

Algorithm to create an influence map is similar to blurring process used by any photo editing software like gimp or adobe.

The AI can clear out all the nodes in the map it has vision of and move to the highest value in the map assuming to find the player.

The blurring process or updating the map occurs as fast as the player moves 

AI types using Occupancy Map:

Single AI using its own occupancy map: 

The AI behavior is as follows:

  • Idle: Initially the AI remains in idle state till it has sight of player

  • Chase Player: If the AI has sight of player the AI chases the player

  • Search using Occupancy Map: If the AI is searching the player and loses track of player the uses an Occupancy map to find the player 

Multiple AI sharing a common occupancy map:

The AI behavior is as follows:

  • Idle: Initially the AI remains in idle state till it has sight of player

  • Chase Player: If the AI has sight of player the AI chases the player

  • Search using Occupancy Map: If any of the AI that is searching the player loses track of the player the AI, all the AI uses a shared occupancy map to find the player.

  • This is a special case where AI uses Influence maps combined with Occupancy maps for better search results.

A short video of single AI using occupancy maps to search player:

A short video of multiple AI sharing occupancy map to search player:

Influence Maps and Pathfinding:

Influence Maps:

In artificial intelligence one of the biggest problems is how to convert a complex world into a set of data that the AI can actually understand and work on. The real world or even a game world is infinitely complex and different techniques to compress that infinite data set into a usable format is a classic problem in AI research. Thankfully for games we don't have the trouble of having to interpret the image from a camera to create a 3d world to move around in.

We have the advantage of having access to extremely detailed data of everything in the game. But the amount of data we have access to makes any sort of planning by the means of calculations impossible. The world is simply to complex, so in order to be able to work with it we have to employ a series of different algorithms the one we are going to look at today is called influence mapping and it's a way to resolve the actual strength relation ship on a map and helps to base tactical decisions on this. It has nothing to do with purchase planning or high level strategical decisions It's simply a analysis tool to create an accurate and usable view of the world.

Influence maps are based around the concept that objects in the game influences the strength relationships between the players and this influence spreads from their current position outwards throughout the map. If you add in all the influence of all the objects then you would get a view of the relative strength relationships for that part of the map. You should also be able to detect the actual front lines between the different sides with it too.

 

Influence maps are relatively easy to set up and are very flexible. There are parameters that can change the behavior of an influence map

  • Momentum : Linear interpolation is used to blend from the current influence value to the new value, and relies on the momentum parameter to control the result.

  • Decay: While the momentum features the strength of the scalar influence field, the decay represents how quickly the influence fades.

  • Update Frequency: Influence map update frequency depends on how many resources are to update in the game by the AI. Depending on the map, different update frequencies are used.

Algorithm:

The algorithm for influence mapping is similar to a blurring process that any photo editing software, such as, Adobe Photoshop or Gimp implements. Influence is set on the influence map and the algorithm repeatedly blurs the map to spread the influence from the source outward, to its neighboring nodes. The blurring process is a low-pass filter method as used in image processing to smooth images. In order to function, influence mapping needs to have propagators.

Influence mapping algorithm consists of two steps:

  • Step 1: While the propagator is active (i.e., enabled, alive), set influence field in the influence map.

  • Step 2: Loop through all the cells in the influence map grid and spread influence to neighboring cells. This is done using a simple blurring method which decays with distance using an exponential fall off.

Pathfinding

 

Pathfinding is defined as the search for the shortest path between two nodes in a graph. A path connects two nodes, A and B, through a set of arcs, and nodes. A node is a component that is used to represent a state and position and an arc (also known as edge) is a connection or reference from one node to another. The node that connects with an arc is a successor node.

Dijkstra's Algorithm:

In 1959,introduced a method to find the shortest path between two nodes of a weighted graph, where each edge would contain a positive traversal cost. Dijkstra's algorithm is both complete and optimal.

Dijkstra's algorithm explores the whole graph while keeping track of the cost so far (CFS) value C of each node from the starting node. C values allows to know how far is the currently explored node from the starting node. At each node, the cost to travel to a successor node is added to its C cost. Since multiple paths can exist to a single node, successor nodes may already have a G cost, meaning that there is an existing path to that node, at which point an evaluation of a better path needs to be done. A new C cost is calculated from the current node to the successor node, and in case it has a lower value, the path is updated. This guarantees that the returned path is the shortest path possible, the optimal path. During the search, Dijkstra's algorithm encounters nodes that fall into different states: unseen, unvisited and visited. When an unseen node is encountered, its C value is calculated. This unseen node now needs to be explored, so it is placed into a list, called the open list, which contains all nodes that need to be explored. A node is removed from the open list in order to be explored, and added to another list, called the closed list, which represents the nodes that have been visited, but visited once. The node popped from the open list to be explored is the node with the lowest C value. This means that it is the node that is closer to the starting node, that is, the shortest path so far. When there are no more nodes in the open list, the algorithm returns the shortest path from the starting node to the goal node.

A* Algorithm:

The A* algorithm was introduced in 1968 by Peter Hart, Nils Nilson and Bertram Raphael as a variant of Dijkstra's algorithm. However, unlike Dijkstra's algorithm, A* does not ensure that the shortest path is found.

A* algorithm explores a search graph in a best-first manner, growing an exploration area from the start node until the goal node is found, while remembering the visited nodes, to be able to avoid re-exploration of nodes and to reconstruct a solution path to the goal. The A* algorithm works by combining the C value used in Dijkstra's algorithm and the heuristic estimate, H, to the goal, into a total estimated cost, referred as F(n) = C(n) + H(n). A* differs from Dijkstra's algorithm on its selection of the node from the open list. Dijkstra's algorithm selects the node that has a lower C value, i.e., the node that is closer to the starting node, while A* selects the node that as a lower F value, which represents the node that has a shorter path so far and that is estimated to be closer to the goal.

Combining A* algorithm with influence Maps: 

The A* algorithm works by combining the C value used in Dijkstra's algorithm and the heuristic estimate, H, to the goal, into a total estimated cost, referred as F(n) = C(n) + H(n).

Combining Influence maps the new F(n) = C(n) + H(n) + I(n) where I(n) is the influence value of the nodes. This does not ensure a shortest path but the path given is better for the AI as it tends to move towards positive influences and away from negative influences.

Some images of A* path using influence maps and without influence maps : 

Astar4way.PNG

A* path - 4 way movement without influence map

Astar8Way.PNG

A* path - 8 way movement without influence map

4waywithInf.PNG

A* path - 4 way movement with Influence map

8WaywithInf.PNG

A* path - 8 way movement with Influence map