Hello!
Today, we'd like to introduce our game's pathfinding system.
Our first system was a simple tile‑grid approach.
With the A* algorithm, it explores the terrain in eight directions: north, south, east, west, and the four diagonals.
In the early game the terrain was simple, but in the new levels ropes and humans appear.
So we thought AI should also be able to make use of ropes.
To make pathfinding efficient, we needed to incorporate these features into the system.
We decided to build a navigation mesh to store such points.
Navigation Mesh
Here is the navigation mesh we completed after lots of coding.
For debugging, additional detailed information is shown in the editor.
Ropes are mapped as shown above.
We calculate positions where you can jump onto a rope to connect the terrain.
Based on this, we run pathfinding.
Each path contains information about different movement modes such as walking, jumping, and riding a rope, depending on the node type.
The navigator, described below, makes use of this information.
Navigator
If the navigation mesh is the terrain data, the navigator is the module that follows the path based on that information.
We implemented various sub‑modules to ensure correct path following.
Path Simplification Module
A path that simply connects nodes can be inefficient or look awkward.
To address this, we keep the movement within node bounds while straightening the path as much as possible.
This runs in real time.
Wall Collision Avoidance Module
If the AI unexpectedly touches a wall, simply moving along the planned path causes it to rub against the wall, which looks unnatural.
To prevent this, when the AI touches a wall we slightly turn its movement direction to keep motion natural.
Fall Prevention Module
Because our game uses a physics‑based movement system, the AI might accidentally run off a cliff.
To prevent this, the AI computes dangerous movement angle ranges within its current node that could lead to a fall.
Obstacle Handling Module
This module detects and gets past dynamic obstacles that block the path.
For these local searches we reuse the grid‑based pathfinding we previously built.
If it’s a small obstacle, we pick it up and move it aside.
Wrapping Up
Finally, here’s the AI chasing while using a rope.
Thanks for reading!
