TERRAIN ANALYSIS

The goal here is to create a simple Hide & Seek game mechanic as shown above. Before we can implement this, let me cover some useful terrain analysis techniques that make this possible.

OPENNESS

This is one of the simplest terrain analysis techniques. Evaluating a given cell and its distance to the closest wall. Here I am using the value of `1 / (d * d)` where `d` is the distance to the wall or edge which is used to visualize the results by coloring the cells according to the value produced.

This analysis can have multiple use cases such as proximity to static objects, good cover points (shielding or darkness), good cover along path (wall hugging), wall building sites and more.

VISIBILITY

Visibility can be a good tactile indicator. Two cells are visible to one another if a line between their center points doesn't intersect the four boundary lines of every wall cell.

While performing this check a simple optimization can be performed by computing the line between the two cell centers, then checking it against the 4 boundary lines of each wall that falls inside the bounding box of the two end points. However, since I was working with a grid, another optimization can be performed by using fast voxel traversal. This has the benefit of limiting the visibility search to only the cells the line between the two cell centers crosses, with a single special case when the line crosses the corner of a cell.

To visualize the visibility the cells are colored using the number of cells that are visible to it.

This information can be used to determine how safe or dangerous a position is, how much cover it provides, is it a good position to attack from, determine pinch points, create ambush points, and more.

VISIBILITY TO AGENT

Expanding on visibility, you can compute it in relation to an agent. The same calculation as before is performed with different resulting values all in relation to the cell the agent is occupying. All cells that are visible to the agent in blue are colored with a value of 1. All cells that are not visible but are next to a visible cell have a value of 0.5 with all other non-visible cells having a value of 0.

This can be useful to determine line of sight, peek points, areas of interest, determining a search area, and more.

SEARCH

Once you have visibility working you can then apply it to create a search. For every cell in the given layer that is visible to the given agent it is marked with a value of 1. As visible cells leave the agent's search the value is decayed over time to represent most recently searched cells.

It is important to consider the direction the agent is facing as this is what influences the agent's field of view.

This is the beginning of the hide and seek mechanic allowing an agent to check cells within view for a target.

PROPAGATION

Propagation will determine the likelihood of a given cell. In our case the propagation refers to the likelihood the blue agent is in this cell. This will be performed on an Occupancy layer which simply contains agent locations. 

This is the key factor in determining how an AI agent will seek the player.

PROPAGATION SUDO CODE

For each tile on the map
  • Get the influence value of each neighbor after decay Keep the maximum decayed influence value of all neighbors
  • Apply linear interpolation to the influence value of the tile, and the maximum decayed influence value from all neighbors, with growth factor as coefficient
  • Store the result in the temp layer
Store influence value from the temp layer

PROPAGATION EXAMPLE

BRINGING IT ALL TOGETHER

Making propagation a viable value for seeking:
  1. Run the propagation algorithm on the occupancy layer
  2. Normalize the occupancy value after each propagation
    • The highest occupancy value is always 1.0
  3. The tile with the highest occupancy value is the most likely location for the player
    • Need to find the closest tile to AI with 1.0 influence value, to make sure AI searches the closer area first 
  4. If no tile has occupancy value >= 1.0 after normalizing, means there is no propagation
    • AI “loses” the player
    • AI should go back to its old behavior
Finally, making a minor change to how visibility is calculated, we will now use negative values instead of positive values. This simplifies checking if the player is visible.

AI LOGIC

Compute FOV layer
If AI sees the player (player’s cell has negative occupancy value), behavior: RUN TO PLAYER
  • Pick the player’s position as goal
If the AI can’t see the player, behavior: SEEK PLAYER
  • If the player moves out of sight, use its last known position to start propagation 
  • Update occupancy map 
  • Pick the closest cell with 1.0 occupancy value as goal 
  • If no cell has 1.0 occupancy value, AI loses the player
If AI loses player, behavior: PATROL AI
  • Picks a random position within certain distance as goal, and walk to it
And this is how we can use some terrain analysis to create fun and engaging game mechanics.

ADDITIONAL INFO

Layers can be used for just about anything, Some might represent utility, while others could represent influence.
Influence maps can provide an abstract distribution of power.
Line of fire layers can inform you which direction weapons are facing.
Light levels can provide brightness or darkness on any spot.
Cover layers can provide information about where AI can take cover from gunfire.
Generally, when working with layers, you are combining multiple layer values together into a single layer used to make a decision. There are a few options to do so such as multiplying them all together, taking the mean, or taking the geometric mean, with geometric mean being the optimal solution.