Making enemies come to life

Using A* and ORCA algorithms to help enemies navigate through the map 

Do you ever wonder how enemies are able to chase down players through tight spaces and never get stuck? It might look like magic but behind the scenes it's all about the complex algorithms used. In this blog post, I will be breaking down two algorithms that were used to help move the enemy, A* and ORCA, and how they work together to make the enemy come to life. 

In Mega Dimension Ripper 9000, enemies are a core element of the main game-play loop. To bring them to life, we first must introduce the A* algorithm. So, what is the A* algorithm? In short, the A* algorithm traverses through the map and finds the fastest route towards a target. To find the closest path, this algorithm will need a reference to the map; in our case, we made our map into a 19x32 grid. Each grid consists of nodes which we determine to be walkable or not. Then our A* algorithm will be able to tell which nodes can be traversed.  

Starting at the node where our enemy is located, the algorithm will traverse through each node until it reaches the player. It does this by calculating a cost for each possible path: the actual cost from the start node to the current node (called g) and an estimated cost from the current node to the goal (called h). These values are combined to form f = g + h, and the algorithm always chooses the node with the lowest f value to explore next. This allows the enemy to efficiently find the shortest path to the player while avoiding obstacles. Once the path is found, the enemy follows it step-by-step, updating as needed if the player moves or the environment changes. However, A* alone isn't enough when multiple enemies are navigating the same space — that’s where ORCA comes in.

Along with the A* algorithm, we also used the ORCA algorithm. ORCA, otherwise known as Optimal Reciprocal Collision Avoidance, will make sure our enemies are able to navigate through the map without colliding with one another. This is an added layer to make our enemies feel life-like. Like the A* algorithm, ORCA needs a target to go towards. ORCA then calculates time to collision with another enemy. If the time to collision is within a certain time horizon, ORCA will then take the velocity of an enemy and add a force that either slows down or speeds up the enemy to avoid collision.  

-Chong Vang