How to Build a Heatmap for Tactic AI : Attempt 1

I’ve been doing experiments on game AI, tactic team AI to be specific. And currently I’m looking forward to make use of a heatmap.

My idea is to make a grid map and assign heat value (or temperature) on grids so that it represents value of some property that can be reasoned about by an agent. An example would be to represent the potential danger. Think of a group of defenders who wants to defend a room with two entrance from waves of zombies. The area close to the two entrances are most dangerous, therefore have highest temperature in the heatmap. In addition to those two points, places nearby should also be ranked more dangerous than any other places. And a corner of the room could be a safer place to hold (although it’s not always true).

However I’d like the heatmap to have some extra characteristics. Namely, I want the emission of the heat satisfy this constraint:

The narrower the space is, the harder for the heat to go away.

It makes sense because it’s most dangerous if you are trapped in a small cage or a narrow corridor with a ruthless zombie than in a open space, where you can run and turn freely.

My first implementation attempt is to use Breadth-First Search to spread the heat and decrease the energy as it goes farther and farther. And to satisfy the requirement above, I made the decrease factor negatively related to the number of open spaces (neighbor grid without obstacles) next to a grid. For instance, let’s say first there’s a heat source somewhere in the grid field, and 5 out of it’s 8 neighbors are obstacles. And those 3 open neighbors will share all the energy the heat source emits. On the other hand, if all 8 neighbors of some heat source are open, the heat emit will be evenly distributed among them, therefore each neighbor receives less energy.

Intuitively this method tends to keep energy in small room and makes heat in narrow hallways to travel further before the energy becomes insignificant, than in a wide open space. However, the experiment didn’t work out well.

In the experiment I use the number of grids a heat source can influence to indicate whether this model makes sense. In common sense, a heat source with the same initial energy should influence same number of grids regardless of geometry, assuming the obstacles are made of insulation materials. But this naive model cannot guarantee it. Also, exponentially decreasing energy feels wrong. You can see the results from the image below. (Depth of green-ish color indicates the energy. Two heat sources are on the same row, different columns of the field)

exponential_decreasing_by_open_neighbors
Heat in narrow spaces does influence further, but the area of influence is unproportional.

Next step I’ll figure out how to preserve the area of influence on any geometry, and try to invite some 1/distance^2 like factor into the function because it feels more natural.

One thought on “How to Build a Heatmap for Tactic AI : Attempt 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s