top of page

Heatmap System

After alot of work within the AI area I wanted my AI characters to be less predictable and take more advanced decisions. After seeing a GDC talk from Dave Mark I got inspired to try my own take on modular Heatmaps

Github repo

Showcase scene

Kitty Engine (own)

  • Green unit will flee whenever it detects high enough threat from red units at it's own location.

  • Red units are coded to move towards the green unit and will reset if under high enough threat from blue units.

  • Blue units will defend the green unit if it's under threat.

Blue units constantly check the threat at the location of it's defend point (the green unit). If threat value over X is detected, the blue units scans a bigger area around the green unit.

​

In this scan the blue units first add friendly location influence with a interest value of 1 and exclude their own location influence.

We then invert the values, treating them as negative and add enemy threat influence with a interest value of 0.5 (positive), meaning we care more about the location influence over the enemy threat influence.

 

By blending these two heatmaps together within our scan area, we retrieve a position spread away from friendly units but with high enemy threat. Simply a better suited location to defend the green unit!

The modular layout of the workmap allows for a wide variety of operations and is also data driven, allowing designers to set interests values, the size of the area and define which maps to blend together. We can scan specific areas, point of interests or even unit locations, letting us to do behaviours and perform actions based on the data around us.

Workmap operations of the blue units

Example usages:

- Is there threat at my location higher than X? Retrieve a safe position, I want to flee!
- is there threat at my allied healer location? Defend my healer!
- Do the area around me have a total value higher than X? Perform a Area of effect spell!
- Where is the frontline located? Combine my team and enemy team threat maps and retrieve a position!
- Where do I throw my grenade? Retrieve the location with highest enemy influence (center of mass)!
- Where are my allies located? Retrieve a position with low location value, I want to spread from my allies!

More in depth

The Manager

Users & adaptation to level Geometry

  • Units register themselves to the Manager with specifications of Heat type, radius, highest value, falloff curve. The manager then allocates the Heatmaps requested by the users.
     

  • During runtime, the manager then repaints the influence (based on a update frequency).
    A optimization I did for this was to only repaint a units influence if they have moved. To allow for this we need to keep track of their previous and current location within the Grid and then simply remove influence from their last known location and applying it on their new location.
     

  • As we repaint the influence on the Heatmaps we want the values high close to the unit and lower the further away they are. To define the fallof ratio, we can use different types of falloff curves.

Applying Influence

Painting Influence

The Manager's runtime work

  • In order to adapt the Heatmaps to the geometry of the level, the Manager calculates which cells to discard based on Navmesh information. We only want to apply influence on locations where units can be at.​ This information is then used for a breadth-first search (BFS) algorithm that only applies influence to cells that are valid. Increasing the cost of the re-paint process but enabling more complex geometry.
     

  • Though, it is quite expensive to do these falloff calculations during runtime. To solve this I created a "Heat Template" which is basically a small grid with values based on the distance from center to each cell (together with a falloff curve) calculated at the initialization stage. This eliminates the distance and falloff curve calculations, but we are limited to certain sizes of templates.
     

  • To optimize this even further, I knew that the only place where we change the data in the Heatmaps are within the Manager. Users only read this data but they never change it. This allowed me to put the re-paint process on a separate thread. Though I had to mutex lock the map we are changing, preventing users from reading it until the re-paint is done.

Heat Template

Collecting information

User side of the system

  • To keep this modular and user friendly, I created a adaptor to the Manager called "Workmap" that users can retrieve from the Manager. This is where all the processing of user requested data happens.
     

  • A user requests a workmap by defining the position and area where we want to collect data from in the world. The workmap interface then has operations like "Add, Subtract, Normalize, Invert", allowing the user to collect information and modify it. 
     

  • When adding different types of values to the workmap, we can specify at what interest we have in those values. This allows us to blend different type of heatmaps together, and here is where the magic happens. By having multiple maps blended together, we can receive a cell of interest based on multiple inputs, for example: "a cell with low threat and low friendly location" influence, this position would be kind of hard to retrieve without heatmaps.

Step by step

Further improvements

Optimization: A threaded worker system would heavily increase performance. Letting users request collections of data and retrieve them when the working thread is done. 

More techniques:

  • Bread crumbing: A special type of heatmap where influence decay over time, leaving a trail after the unit.

  • Static influence: Where have units died during the course of the game? Those locations might be considered more dangerous, would be nice for AI's to learn from past mistakes!

bottom of page