Almost all games at least use a form of path finding which uses either a navmesh or a grid or some sort of graph to find where an agent can/cannot go. Other than that, different games and engines have different mechanisms to answer spatial questions like where should I take cover? where the traffic path is and what is the direction and speed of the current traffic and …
In this post we’ll take a look at the different mechanisms and their usefulness in different situations

Influence Maps

We are biased toward influence maps since we heavily use them and sell libraries for it for both Unity and Unreal Engine but this aside, these are advantages and disadvantages of them.

An influence map is a 2d grid which each of its cells stores a value which indicates existence of something. A threat map stores existence of enemies in each sell and a food map’s value in each cell indicates how much food is in that cell.
Influence maps always store the data no matter if you need it or not. Whenever something you want a map for, like agent positions and their threats or important events like kills or travels, the map records the info.

This means you always know what is going on in the world but also means influence maps take some CPU and memory. They use a grid like structure in most implementations and take a good amount of space compared to a sparse Navigation Mesh but they store the info on all parts of the map which are good for dynamic, systemic games which pre-defined structures cannot define where is important too much.
You don’t have to have maps for every part of your world, if it does not make sense to have a map for some part of the world though. Influence maps cache the data of events or object positions so agents don’t need to recalculate that to be able to ask questions. They still need to pay the price of the search for their questions but not more.

Since influence maps do lots of similar calculations on very cache friendly data-structures (arrays) they can use the cache and SIMD instructions to their advantage to become a lot faster. Also you can have maps in different resolutions and update frequencies for different things which help a lot.

The ability to store data in multiple resolutions is very useful because you might need a map with 1 meter accuracy around the player for combat but the map of food in the world can have cells of 100 meters and still be very useful.
Also, the enemies map needs to update 2-3 times a second, but the foods map can update whenever a food object is added/removed from the world.
The influence of an enemy or a food or anything else like an event is usually a stamp of multiple cells in form of a square. so a ranged unit can say I’m here, not only where he stands but also in 10 meters. The influence usually decreases with distance or increases in cases like a tank which can shoot further away better than close by.

Other than multiple resolutions, another very useful property of influence maps is the fact that you can combine multiple maps to answer complex questions. As an example, you can add the map of wolfs and rabbits to each other and multiply the map of where rabbit kills has happened by 2 and add to them to know where the potential is to see more hunts and chases. something like

rabbits + wolfs + (hunts * 2) = where photos should be taken.

Did anybody make such a photography game. or maybe you go there to save rabbits or whatever, put some glue on the ground so both rabbits and wolfs are trapped and you can bring them to your zoo or anything else.

If your game needs to or can benefit from answering these sorts of complex questions for decision making, influence maps can really shine.

Graphs

A graph structure can be used to mark movement of objects and properties of a point because a graph node can hold any arbitrary data and it has relations with the nodes it is connected to. We can even add data to edges. This data can be anything. Strength and direction are two common examples. Actually influence maps can be thought of as graphs because implicitly a grid is a graph which each node is connected to its Neighbours.

Usually, graphs are used to show the direction of movement or the strength of events in different places with some directionality. They are good for things which a grid is a waste and need to know more about the edges like what direction the movements are or from which node to which other kills are happening.

Where to put nodes can be a challenging task for designers and situations might happen at runtime which might need adding/removing nodes which you might not have anticipated. This is specially true for multiplayer or sandbox games where lots of unexpected things happen. Imagine you wanted nodes to show you where cars usually go in your game and in which direction so the police can go where the most traffic is, if in your game only roads can have cars then that is fine but if your game is sandbox/systemic and players can go off-road then you need to add graph nodes where actually cars are. so graphs are less good for games which the structure of the level and where gameplay happens changes. However if you have mostly static levels and known places which gameplay happens in them then they can save your lots of processing and give you lots of information.

Runtime graph creation can be done and can help with this but only to a certain extent like when you create roads in a city building game but if you want to add graph nodes based on what happens at runtime all the time, then first of all when you realize that gameplay is happening off-road and add nodes to gather and cache info, it might be too late and the agents might show incorrect/weird behavior for the lack of information and secondly, it is hard to know when is a good time to add/remove nodes in a way so behavior of the agents look both correct and consistent. Imagine a road has been empty and you remove its nodes but then one car goes throw it and because it is just one, you don’t add nodes and police doesn’t chase the car despite the fact that it is going where it should not go. Having a grid or influence map which always calculates the info for all the points or a dense grid which does the same solves these issues.

Unreal Engine’s EQS like systems

Unreels EQS allows your agents to do a set of ray traces/sphere traces to find out what exists in different positions in the world and then using some criteria, choose good candidates for your query as the response. This approach is very CPU heavy andcan only answer questions which can be answered based on the current position of the colliders in the world. It cannot tell you anything about events which happend over time in different places or where the entities have been. It also can potentially mean many entities recalculating nodes and conditions but it can be mitigated and by writing a good system on top and re-using query results as much as possible, you can reduce the number of queries you execute.

The advantage is that the queries are very intuitive to form for designers and they have the highest resolution possible and work with the most accurate representation of the environment. The traces work with the actual colliders and not any form of approximation of their shape and size which is an advantage for queries you need to know in very high resolution where exactly is the right position. But for the same reason EQS naturally is not the best choice if you need to answerhigher level questions like: roughly speaking where some resource is more abundant? In which 50 meter radius area, most enemies are located to throw a bomb? Where rabbits have been eaten by wolfs so they should avoid that place because they are scared of the place.
Sometimes EQS like systems and Influence Maps/graphs don’t replace each other and serve different purposes. Your influence map can tell you which part of the world go to but then the EQS can tell you exactly where in that part of the world you should stand. High resolution influence maps can answer that question as well and even can help you find a place with good distance from the other units as well but the distance calculations can be done using obstacle avoidance to some degree and query parameters can help with that to some extent as well. In EQS like systems, you might need to run multiple queries if the ideal place cannot be find and you have to relax the conditions a bit to find a somewhat good position, but it is doable.