Harbor Havoc

Contributions
- Throwing ball physics
- Player
- Portals
- Audio System

Harbor Havoc

Contributions
- AI Enemies
- AI Manager
- Behavior Tree

Stellas Quest

Contributions
- Astar pathfinding
- Grid Manager
- Frustrum Culling
- Collision System

Spite Hymn of Hate

Contributions
- Navmesh import
- Navmesh Pathfinding
- AI Enemies

Dissonance

Contributions
- Scene Manager
- Level json parsing
- Checkpoint System
- Boss Abilities
- UI

3D Navigation Grid

The navigation grid is a system designed to enable pathfinding and navigation within three-dimensional spaces, allowing agents (such as flying units) to traverse complex environments.By using a grid structure, the system efficiently breaks down the 3D space, evaluating terrain and static obstacles to define which volyms are accessible. This process ensures precise pathfinding, even in environments with intricate geometry.For pathfinding, the system employs a unique Grid Trace technique that straightens paths between cells, optimizing movement to be both efficient and smooth.

• Read more

Influence Maps

The system provides units with real-time information about their surroundings, such as threat levels and proximity.Multiple influence maps can be dynamically combined during runtime, generating valuable data that units can use to make informed decisions.Learn more to see how units operate solely based on influence data, enabling autonomous and intelligent behavior.

• Read more

Navmesh Pathfinding

The system provides units with waypoints along the navigation mesh, allowing them to move efficiently through complex environments.While the final algorithm may seem simple, getting there was a complex challenge. Debugging pathfinding logic required overcoming countless obstacles, uncovering tricky edge cases, and gaining deep insights into the field.Learn more to see how I developed my own version through trial and error.

• Read more

Flocking Boids

A side project to deepen my understanding of kinematic movement and how to combine velocity-based movement with pathfinding.Learn more to see how this small side project evolved into a versatile Steering Controller, which I later applied across multiple game projects to handle AI movement more efficiently.

• Read more

Influence Maps

Green unit (Fleeing) constantly tries to move to a position under least amount of enemy influence (Red units).
Red Units (Enemies) are coded simply to move towards the green unit but will reset upon detecting high enough influence from the blue units.
Blue units (Defenders) constantly tries to position them self on a high threat position around the green. They also take their own team's proximity into account to keep spread out and avoid clumping up at the same position

How does it work?

An Influence Map in its simplest form, is a grid where each cell holds a value representing some influence in the world.
It works by spreading values from the units center and outwards using a BFS algorithm, creating spatial data describing the units surroundings.The system I’m presenting here takes this concept a bit further by allowing multiple influence maps to be combined during runtime, essentially creating a "texture" that AI's can make strategic decisions based on.

Spreading Influence

On a set timer, the system looks to re-paint influence of all registered units that have moved to a new cell since last update-tick. We spread half the influence on our current position and our future position (position + velocity) to better represent the units influence.

The need to adapt to level geometry is important also, as it would not make sense to retrieve or apply values on the other side of a wall or outside the map, we want to mark up which cells are valid.
To do so we compare each cell's center position against the Navmesh and mark cells outside of it as invalid. Also when both retrieving and applying influence we use a flood fill algorithm (BFS) to adapt it to the level geometry.

void InfluenceMap::FloodFillInfluence(const Vector2i& aOriginCoord, const InfluenceData& aInfluenceData, float aAmount)
{
    InterestTemplate& interestTemplate = myManager->GetInterestTemplate(aInfluenceData);
    FalloffFunction curve = GetFalloffFunction(aInfluenceData.type);

    int radius = interestTemplate.dimensions / 2;
    int maxIterations = radius + 1;
    int distance = 1;

    std::set<int> visited;
    std::queue<std::tuple<Vector2i, Vector2i, int>> bfsQueue;

    Vector2i boundsMin = { std::max(myBoundsMin.x, aOriginCoord.x - radius), std::max(myBoundsMin.y, aOriginCoord.y - radius) };
    Vector2i boundsMax = { std::min(myBoundsMax.x, aOriginCoord.x + radius), std::min(myBoundsMax.y, aOriginCoord.y + radius) };

    bfsQueue.push({ aOriginCoord, interestTemplate.centerCell, distance });

    int worldStartIndex = aOriginCoord.y * myGridSize.x + aOriginCoord.x;
    int localStartIndex = interestTemplate.centerCell.y * interestTemplate.dimensions + interestTemplate.centerCell.x;

    if (worldStartIndex >= 0 && worldStartIndex < myValues.size()) {
        myValues[worldStartIndex] += interestTemplate.values[localStartIndex] * aAmount;
        visited.insert(worldStartIndex);
    }

    float bfsFallof = 1.0f;

    while (!bfsQueue.empty()) {
        Vector2i nextLocalCoord, nextTemplateCoord;
        Vector2i localCoord, templateCoord;

        std::tie(localCoord, templateCoord, distance) = bfsQueue.front();
        bfsQueue.pop();

        float fallof = curve(static_cast<float>(distance), static_cast<float>(maxIterations));

        for (const auto& direction : directions) {
            nextLocalCoord = localCoord + direction;
            nextTemplateCoord = templateCoord + direction;

            if (nextLocalCoord.x < boundsMin.x || nextLocalCoord.x > boundsMax.x ||
                nextLocalCoord.y < boundsMin.y || nextLocalCoord.y > boundsMax.y) {
                continue;
            }

            int heatmapIndex = nextLocalCoord.y * myGridSize.x + nextLocalCoord.x;
            int templateIndex = nextTemplateCoord.y * interestTemplate.dimensions + nextTemplateCoord.x;

            if (!myValidCells->at(heatmapIndex)) continue;

            if (visited.find(heatmapIndex) == visited.end()) {
                myValues[heatmapIndex] += (interestTemplate.values[templateIndex] * fallof) * aAmount;
                bfsQueue.push({ nextLocalCoord, nextTemplateCoord, distance + 1 });
                visited.insert(heatmapIndex);
            }
        }
    }
}
                      

Retrieving information

When retrieving information units request a "Working Map" of a certain size and place (position) in the world.
The modular way of the workmap then allows us to fill it with data from the influence maps by specifying Influence type, from which Team and of what Magnitude.This way we can collect different types of influences and combine them using various math operations.

Workmap* workmap = influenceManager->GetWorkmap(scanOrigin, scanRadius);
workmap->Add(Team::Player, InfluenceType::Proximity, 1.0);
workmap->ExcludeUserInfluence(user, InfluenceType::Proximity);
workmap->Invert();
workmap->Add(Team::Enemy, InfluenceType::Proximity, 2.0);

Vector3f result;
if (workmap->GetPositionByHighestValue(result)) {
    highestThreatPosition = result;
}
                        

---

Initialization process

Units register them self into the system, specifying influence type, spread radius, influence strength and falloff curve.
The system creates the desired influence maps and stores the information for each user on how their influence should be applied.The falloff curve tells the system how the values should be applied based on the distance to the units position. Having the ability to set a certain curve is useful as some units might not be threatening at close range and want higher values to be applied as the distance increases.To increase performance we can skip running the distance based curve calculations during runtime as the spread radius and falloff curve gives us all information we need to pre-calculate this.
The system therefor creates "InterestTemplates" during setup which basically are smaller grids holding the magnitude of the influence value for each cell of the specified radius and type. A small cost of memory but quite a big gain to runtime performance.

void InfluenceManager::RepaintUserfluence(InfluenceComponent &user)
{
  Vector2i previousCoordinate = user.location;
  Vector2i currentCoordinate = GetCoordinate(user.myPosition);
  if (currentCoordinate == previousCoordinate) return;

  std::unordered_map<InfluenceType, InfluenceMap*> &container = myInfluenceMaps[user.myTeam];

  for (InfluenceData &imprint : user.myImprints)
  {
    // Get the template (brush) for how we spread values.
    InterestTemplate &interestTemplate = GetInterestTemplate(imprint);
    InfluenceMap &targetPaintMap = *container[imprint.type];
    
    // Remove from the previous and paint on new location
    targetPaintMap.SpreadInfluence(previousCoordinate, interestTemplate, -imprint.maxValue);
    targetPaintMap.SpreadInfluence(currentCoordinate, interestTemplate, imprint.maxValue);
  }

  user.location = currentCoordinate;
}
                  

---

Examples of usage

The dynamic setup of the system allows both dumb and smart AI's to accomplish their goals by assigning weighted values when retrieving influence data through the Workmap.A dumb AI might just care about destroying nearby opponents no mater what, only taking the opponents proximity influence into account when choosing a location to throw a bomb at.A more strategic and smart AI might want to take allied units proximity into account to avoid hurting them.Example scenarios:
- 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? Retrieve position around it with highest amount of threat, I will defend you!
- Do the area around me have a total influence value higher than X? Time to use my Area of effect spell!
- Where do my grenade do most damage? 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!

Further improvements

- Having a Octree as main grid that can hold influence maps within it to avoid unnecessary cells outside the map.
- Add a scheduler to spread out repainting of influence over multiple frames.
- Bread-crumbing influence that stays in cells and decay over time.

Defining flight volumes

The setup process is a crucial step in determining which volumes within the 3D navigation grid are traversable. It involves performing various collision checks against the terrain, static objects, and predefined blocked areas. Cells that intersect with any of these obstacles are marked as invalid.After marking intersected cells, a breadth-first search (BFS) is initiated from a cell known to be connected to the main grid. This allows us to identify and validate all connected, traversable cells. Any remaining cells that are not reachable through this search are considered disconnected from the main grid and are also marked as invalid.

Grid Tracing

A common optimization technique for grid-based navigation is Bresenham's line algorithm. Given a line segment, it efficiently determines which grid cells the line intersects, one step at a time.By leveraging this, we can perform a grid trace from each apex point in the path, effectively “string-pulling” the A* result. This process simplifies the route, reducing the number of waypoints and producing a more optimized, direct path through the grid.

bool grid_trace(NavigationGrid &navgrid, const V3 &from_world_pos, const V3 &to_world_pos, const int max_steps) {
    v3i from_grid, to_grid;
    world_pos_to_grid_array_idx(navgrid, from_world_pos, from_grid);
    world_pos_to_grid_array_idx(navgrid, to_world_pos, to_grid);

    int target_index = CELL_INDEX2(to_grid.x, to_grid.y, to_grid.z);

    // Step direction: +1 or -1 depending on the direction of movement in each axis
    int stepX = (to_grid.x > from_grid.x) ? 1 : -1;
    int stepY = (to_grid.y > from_grid.y) ? 1 : -1;
    int stepZ = (to_grid.z > from_grid.z) ? 1 : -1;

    // How far we need to travel along the ray to cross a voxel boundary on each axis
    float deltaX = std::fabs(1.0f / (to_world_pos.x - from_world_pos.x));
    float deltaY = std::fabs(1.0f / (to_world_pos.y - from_world_pos.y));
    float deltaZ = std::fabs(1.0f / (to_world_pos.z - from_world_pos.z));

    // Position within the current voxel (range: 0.0 to 1.0)
    float startX = (from_world_pos.x / navgrid.cell_size.x) - std::floor(from_world_pos.x / navgrid.cell_size.x);
    float startY = (from_world_pos.y / navgrid.cell_size.y) - std::floor(from_world_pos.y / navgrid.cell_size.y);
    float startZ = (from_world_pos.z / navgrid.cell_size.z) - std::floor(from_world_pos.z / navgrid.cell_size.z);

    // Distance to the first voxel boundary on each axis
    // After this, we’ll increment by deltaX/Y/Z per step
    float tMaxX = (stepX > 0) ? (1.0f - startX) * deltaX : startX * deltaX;
    float tMaxY = (stepY > 0) ? (1.0f - startY) * deltaY : startY * deltaY;
    float tMaxZ = (stepZ > 0) ? (1.0f - startZ) * deltaZ : startZ * deltaZ;

    v3i current_coord = from_grid;

    int steps = 0;
    while (steps < max_steps) {
        int current_index = CELL_INDEX2(current_coord.x, current_coord.y, current_coord.z);

        if (is_out_of_bounds(navgrid, current_coord)) return false;
        if (navgrid.nodes[current_index].is_obstructed) return false;
        if (current_index == target_index) return true;

        // Move to the next voxel along the axis with the smallest tMax
        if (tMaxX < tMaxY) {
            if (tMaxX < tMaxZ) {
                current_coord.x += stepX;
                tMaxX += deltaX;
            } else {
                current_coord.z += stepZ;
                tMaxZ += deltaZ;
            }
        } else {
            if (tMaxY < tMaxZ) {
                current_coord.y += stepY;
                tMaxY += deltaY;
            } else {
                current_coord.z += stepZ;
                tMaxZ += deltaZ;
            }
        }

        steps++;
    }

    // If we reach here, we exceeded the max steps before reaching our target
    return false;
}
                        

Navigating

Pathfinding is handled using a basic A* algorithm, which calculates the sequence of volumes (or cells) that need to be traversed from point A to point B. However, since the grid is cell-based, the resulting path tends to be jagged and overly detailed, following a direct cell-to-cell transition that lacks smoothness.To both smooth the path and reduce the number of navigation points, we apply the Grid Trace algorithm. This technique effectively "string-pulls" the path, simplifying it into a more direct and optimized route. It's conceptually similar to the funneling algorithm commonly used in navmesh-based pathfinding.

bool string_pull_path(NavigationGrid &navgrid, const V3 &start, Path &astar_path, OUT Path &out_smooth_path) {

    if (astar_path.size() < 2) { return false; }

    out_smooth_path.clear();
    out_smooth_path.emplace_back(astar_path.front());

    V3 apex = astar_path.front();
    int path_index = 1;
    int last_valid_index = 0; 

    while (path_index < astar_path.size()) {

        V3 to = astar_path[path_index];

        if (grid_trace(navgrid, apex, to)) {
            last_valid_index = path_index;
            path_index++;
        } else {
            apex = astar_path[last_valid_index]; 
            out_smooth_path.emplace_back(apex);
        }

        if (path_index >= astar_path.size()) {

            if (!grid_trace(navgrid, start, astar_path.front())) {
                out_smooth_path.emplace_back(astar_path[last_valid_index]);
            }
        }
    }
    return true;
}
                        

Further improvements

Octree-Based Spatial Partitioning
Replacing the uniform grid with an Octree structure allows for adaptive subdivision of space. This enables finer resolution in complex or narrow areas while keeping broader spaces lightweight, leading to more precise path generation and better handling of obstacles in 3D environments.Bezier Curve Smoothing
After generating the simplified path, applying Bezier curves (or other spline-based interpolation methods like Catmull-Rom or B-splines) can produce smooth, natural-looking flight paths. This is especially useful for aerial navigation, where abrupt turns are unrealistic.

Navmesh Pathfinding

Video showing the algorithm handing out a path to the player in a top down point and click game.
I used my implementation as part of a group project at TGA, see trailer on youtube to see the final results of the project.

Funnel algorithm

The Funnel algorithm solves the most efficient way to move through a series of triangles.It treats the sequence of triangles as a series of portals (shared edges) and forms a "funnel" shape using two vectors from the current position (the apex) to the left and right sides of each portal.As long as the funnel narrows without the sides crossing, we keep extending it. When the sides cross (i.e., the funnel collapses), we set the apex to the last valid side and restart the funnel from that new position.Once all edges have been processed, we perform a final check by extending both sides to the end position one at a time.
If one side cross the other, we add the last valid side before adding the end position and returning the shortest path.

A star

The A* algorithm determines the most efficient sequence of nodes to traverse in a graph — in the case of a NavMesh, these nodes are triangles.It works by evaluating which node has the lowest total estimated cost to the goal, using a heuristic estimate function. At each step, it expands the node with the lowest cost, gradually building an optimal path from start to end.However, A* relies heavily on the accuracy of the heuristic function to find the most efficient sequence of nodes. A poor estimate can lead to longer paths or unnecessary node expansions.Another thing I did was to create a grid where each cell contained triangles overlapping the cell.
By doing this I could retrieve the start and end triangle in a efficient way.

Hueristics

A heuristic is a function used in A* to estimate the cost of traveling from a node to the goal, helping prioritize which nodes to explore.When estimating distances on a NavMesh, using the center of a triangle for the heuristic can be problematic due to the variety in triangle shapes. Triangles with irregular proportions (e.g., long, narrow ones) can cause misleading estimates and result in inefficient paths.A better approach is to base the heuristic on the nearest position along the shared edge between adjacent triangles. This method provides a more accurate distance estimate and helps ensure the pathfinding algorithm works more efficiently and reliably.

Challanges & learnings

Debugging pathfinding algorithms can be particularly challenging. When a bug appears, the issue is often not so easy to locate. Identifying the cause requires stepping through the algorithm step by step, which can be time-consuming. The varied shapes of triangles in a NavMesh add further complexity, and after resolving issues for a path from A to B, new problems may arise when testing from C to D.The code base for the pathfinding project works as intended, but could definitely need a cleanup and some more structure, which is something I would like to do in the future.

Flocking Boids

Steering behaviors

Work in progress