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.

​​

​

​

​

​