Tracking Furthest Enemy in a Tower Defence Game using Max Heap
We have multiple enemies on the map, but which enemy should a tower focus on?
Looking at a map as a player, it's an easy question to answer — the furthest enemy within tower range. But it’s not a simple thing to code!
In this article, I will explain how to use the max heap to track the furthest enemy on the map. The answer to this question is the building block towards enabling towers to track enemies more effectively.
This article is part of a larger series of articles where I explore the development of a tower defence game.
Current Implementation
In the existing implementation, whenever an enemy moves on the map, I trigger an event called EnemyMoved. This event then triggers an update of the enemy's position on the map. The code below is for the update function:
function updateAvailableEnemyStore(enemy: Enemy): void {
if (enemy.getPrevPosition()) {
const prev_position_key = `${enemy.getPrevPosition().row}${enemy.getPrevPosition().col}`
enemySpatialGrid[prev_position_key][enemy.id] = false
delete enemySpatialGrid[prev_position_key][enemy.id]
}
if (enemy.getPosition()) {
const current_position_key = `${enemy.getPosition().row}${enemy.getPosition().col}`
enemySpatialGrid[current_position_key][enemy.id] = enemy
}
}I used an array enemySpatialGrid that tracks enemies in each cell on the map. This way, I can see what enemies are present within any cell.
Towers also use this array to locate enemies to attack within their range.
This implementation does the job, but there is a key issue: we don’t know if an enemy we pick from a cell is the furthest and within the tower’s range. This is because enemies within cells are in no particular order.
Why Max Heap?
Max Heap can enable us to do the following:
- Return the furthest enemy with a time complexity of O(1).
- Computing the furthest enemy when a new enemy is added or distance updated with a complexity O(logN).
- Removing enemies from the heap at O(logN) time complexity.
Alternatives
A simple alternative is to sort enemies within a cell by distance. Afterwards, a tower can loop through enemies in a cell and get the first enemy within its range.
There are issues with this approach:
- Sorting items generally takes O(N logN), this is slower than max heap.
- Enemies that we loop through might not be within the tower’s range. It’s quicker to grab the first element from the max heap.
There are other approaches. One example is a balanced binary search tree. However, I will not be covering those.
Intuition
We can tell which enemy is the furthest by looking at the map. But, how can we achieve the same using code?
One way is to measure the distance the enemy travelled. Then we can compare distances between enemies. The enemy with the longest distance is the furthest.
Implementing Heap
To implement a heap we need an array (the heap) and a dictionary (the positions). The heap will be used to store enemy distances [4,3,2,1]. The positions mapper will map enemies to the indexes in the heap { 1:0, 2:1, 3:2, 4:3 }. This will help us keep distances for each enemy up to date. When the enemy moves, we will update both the heap and positions.
This is how both heap and positions can be demonstrated using a tree and a table:
This is our base class for max heap, with the methods that we will implement:
class MaxHeap {
heap: [number, number][] = [];
positions: { [key: number]: number } = {};
constructor() {
this.heap = [];
this.positions = {};
}
public insertOrUpdate(enemy_id: number, distanceTravelled: number): void;
public deleteEnemy(enemy_id: number): void;
public peek(): number;
}
export default MaxHeap;1. Implementing “adding an enemy”
To add an enemy, we need to do three things:
- Add the enemy’s distance to the heap.
- Map the enemy to the index in the heap.
- Bubble the enemy’s position in the heap by comparing the enemy’s distance to its parent.
When adding an enemy to the heap, we will insert both distance and enemy ID. (This way we will know what enemy distance belongs to.)
The code below shows how an insert can be implemented:
public insertOrUpdate(enemy_id: number, distanceTravelled: number): void {
const id = enemy_id;
if (id in this.positions) {
// TODO: enemy needs to be updated
} else {
// add distance to the heap
const array_length = this.heap.push([enemy_id, distanceTravelled]);
// map enemy to the index
const index = array_length - 1;
this.positions[id] = index;
}
// bubble enemy up
this.bubbleUp(index);
}Bubbling up distance is a little bit harder. We need to compare the added distance to its parent. If a parent is of lower value, we need to swap a parent with a child.
Below is a visual example of going through the process, building from Figure 2. In the example below we will add a new enemy with id 5 that travelled a distance of 3.5.
- Add a new enemy to the back and map the enemy position to index in the heap.
2. Check if bubble-up is possible against its parent. A parent needs to be smaller than a child.
3. Yes, bubble-up is possible, do the swap!
4. Now, we must go back to step 2 until the parent is greater than the child.
This is the code for the bubble-up:
protected bubbleUp(index: number): void {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex][1] < this.heap[index][1]) {
this.swap(parentIndex, index);
index = parentIndex;
} else{
break
}
}
}A parent is stored at the position floor((index — 1)/2). In array [1,2,3], 1 is a parent of both 2 and 3.
We then compare the parent value to the value at the index. If a parent is less than a child, do the swap.
The code for the swap is below:
protected swap(index1: number, index2: number): void {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
this.positions[this.heap[index2][0]] = index2
this.positions[this.heap[index1][0]] = index1
}2. Implementing “update enemy position”
An update is done similarly to adding a new enemy. Except we need to know the enemy’s position in the heap. After that, we need to update the distance travelled in the heap and bubble up.
public insertOrUpdate(enemy_id: number, distanceTravelled: number): void {
const id = enemy_id;
if (id in this.positions) {
const index = this.positions[id];
this.heap[index] = [enemy_id, distanceTravelled];
} else {
// previous code for adding enemy here...
}
// bubble enemy up
this.bubbleUp(index);
}3. Implementing “deleting an enemy”
Generally, items are popped from the heap, but in the game, enemies might be killed before reaching the top.
To achieve deletion, we need to take three steps:
- Swap element to be deleted with the last element in the heap.
- Pop the last element from the end of the heap.
- Bubble down swapped element.
The code for the delete functionality:
protected deleteEnemy(enemy_id: number): void {
const index = this.positions[enemy_id];
// swap enemies
this.swap(index, this.length() - 1);
// delete enemy
this.heap.pop();
delete this.positions[result[0]];
// bubble down swapped element
this.bubbleDown(index);
}In the example below I will take you through visuals of deleting the furthest item in the heap, as shown in the Figure 7.
- We swap the first element with the last element.
2. Delete the last element
3. Bubble the enemy down if necessary by comparing the parent to its children. If any of the children are smaller than the parent, bubble down the parent, by swapping the parent with the largest child.
4. Keep repeating step 3 until bubble down is not possible.
This is the code for the bubble down:
protected bubbleDown(index: number): void {
while (index < this.length() ) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
const leftVal = this.heap[leftChildIndex] ? this.heap[leftChildIndex][1] : -Infinity;
const rightVal = this.heap[rightChildIndex] ? this.heap[rightChildIndex][1] : -Infinity;
const targetIndex = leftVal > rightVal ? leftChildIndex : rightChildIndex;
const target = this.heap[targetIndex]
if (target && target[1] > this.heap[index][1]) {
this.swap(targetIndex, index);
index = targetIndex;
} else{
break
}
}
}We get indexes for the left and right child. Afterwards, we grab the largest child of the two and compare it to the parent. If the child is greater than the parent, swap values.
4. Implementing “peek”
This is the simplest thing to implement. Since the heap is already sorted, we just need to grab the first element in the heap:
public peek(): [number, number] {
return this.heap[0];
}Start using Heap!
Now that we have implemented the heap, we can integrate it into the code!
The original code, within updateAvailableEnemyStore, can now be swapped for a one-liner:
const furthest_enemies = new MaxHeap()
function updateAvailableEnemyStore(enemy: Enemy): void {
furthest_enemies.insertOrUpdate(enemy.id, enemy.distanceTravelled)
}There is also an event responsible for the removal of enemies from the maps. This is where heap delete will go.
window.addEventListener("enemyRemoved", event => {
const enemy: Enemy = event.detail.enemy
furthest_enemies.deleteEnemy(enemy.id)
});You can see the outcome of this in the video below:
Conclusion
There it is. We implemented a max heap and then applied it to the game.
Max heap successfully solved the problem. Now we know the furthest enemy on the map. Additionally, the max heap is more performant than the existing implementation.
Lastly, its implementation paves the way to integrating it with towers. This will make it easier for towers to know what enemy to attack next.
