Pathfinding

Pathfinding

Void's pathfinding system helps characters navigate through your game world. It supports multiple algorithms with configurable heuristics, diagonal movement modes, and custom cost functions.

Overview

The pathfinding system is built around a graph of points connected by edges. Each edge has a cost, and the system finds the lowest-cost path between two points.

Supported Algorithms

• A*: Heuristic-guided search. The default and most commonly used algorithm. Uses a heuristic to guide the search toward the goal, making it fast and efficient.
• Dijkstra: No heuristic. Finds the shortest path to all nodes. Slower than A* but guarantees the optimal path without needing a heuristic. Useful for flow fields and weighted graphs.
• BFS: Unweighted breadth-first search. Fastest when all moves cost the same. Good for simple grids and unweighted pathfinding.
• Greedy Best-First: Heuristic only. Fastest but may not find the optimal path. Good when speed is more important than accuracy.

Creating a Pathfinder

var pathfinder = new AStar2D(initialCapacity: 1000);

Adding Nodes

Add points to the graph:

pathfinder.AddPoint(0, new Vect2(0, 0));
pathfinder.AddPoint(1, new Vect2(10, 0));
pathfinder.AddPoint(2, new Vect2(10, 10));
pathfinder.AddPoint(3, new Vect2(0, 10));

Each node has an ID and a position in world space.

Node IDs from Map Positions

When building a pathfinding graph for a tile-based map, you need to convert tile positions to node IDs. Use MapHelper.To1D to convert a Vect2 position to a 1D index:

int nodeId = MapHelper.To1D(location, mapWidth);

Add nodes in a loop:

for (int y = 0; y < mapHeight; y++)
{
    for (int x = 0; x < mapWidth; x++)
    {
        var location = new Vect2(x, y);
        int nodeId = MapHelper.To1D(location, mapWidth);
        pathfinder.AddPoint(nodeId, MapHelper.MapToWorld(location, tileSize));
    }
}

Connect adjacent tiles:

for (int y = 0; y < mapHeight; y++)
{
    for (int x = 0; x < mapWidth; x++)
    {
        var current = new Vect2(x, y);
        int currentId = MapHelper.To1D(current, mapWidth);

        // Check neighbors (right, down)
        if (x + 1 < mapWidth)
        {
            var right = new Vect2(x + 1, y);
            int rightId = MapHelper.To1D(right, mapWidth);
            pathfinder.ConnectPoints(currentId, rightId);
        }

        if (y + 1 < mapHeight)
        {
            var down = new Vect2(x, y + 1);
            int downId = MapHelper.To1D(down, mapWidth);
            pathfinder.ConnectPoints(currentId, downId);
        }
    }
}

This approach keeps your pathfinding graph aligned with your tile map without manual ID management.

Connecting Nodes

Connect points to form paths:

pathfinder.ConnectPoints(0, 1);
pathfinder.ConnectPoints(1, 2);
pathfinder.ConnectPoints(2, 3);
pathfinder.ConnectPoints(3, 0);

Connections are bidirectional by default. The cost of a connection is the distance between points.

Finding a Path

Get the shortest path between two nodes:

var path = pathfinder.GetPath(0, 2);
// path contains node IDs: [0, 1, 2]

The returned path is a list of node IDs from start to end.

Heuristics

The algorithm uses a heuristic to guide the search. Different heuristics work better for different movement types: Manhattan: |dx| + |dy|. Best for 4-directional movement where diagonal movement is not allowed. Euclidean: sqrt(dx² + dy²). Best for free movement in any direction. Octile: max(dx,dy) + (sqrt(2)-1) × min(dx,dy). Best for 8-directional movement with diagonal costs. Chebyshev: max(dx,dy). Best for 8-directional movement where diagonal costs are equal to straight costs.

Set the heuristic:

pathfinder.SetHeuristic(HeuristicFormula.Octile);

Diagonal Movement

Control how diagonal movement works:

• Always: Characters can walk diagonally anywhere.
• Never: Characters can only walk up, down, left, and right.
• AtLeastOneWalkable: Diagonal allowed if at least one adjacent tile is walkable. Useful for preventing corner-cutting.
• OnlyIfNoObstacles: Diagonal allowed only if both adjacent tiles are free. Prevents characters from clipping through corners.

pathfinder.DiagonalMode = DiagonalMode.AtLeastOneWalkable;

Flow Fields

Flow fields are optimized for crowd movement. They calculate the direction to move at every node, allowing thousands of units to follow the same path with a single calculation.

Compute a flow field to a target:

var flowField = pathfinder.ComputeFlowField(targetId);

Get the direction for a specific node:

var direction = flowField.GetDirection(0);

Use it for each unit:

foreach (var unit in units)
{
    var direction = flowField.GetDirection(unit.CurrentNode);
    unit.MoveInDirection(direction);
}

Flow fields are much faster than calculating separate paths for each unit when you have many units going to the same target.

Custom Costs

Override the cost of moving between nodes:

pathfinder.ComputeCostOverride = (nodeA, nodeB) =>
{
    float baseCost = Vect2.Distance(nodeA, nodeB);
    float terrainCost = GetTerrainCost(nodeB);
    return baseCost * terrainCost;
};

Override the heuristic estimate:

pathfinder.EstimateCostOverride = (nodeA, nodeB) =>
{
    return Vect2.Distance(nodeA, nodeB);
};

Filter which neighbors are considered:

pathfinder.FilterNeighborOverride = (neighbor) =>
{
    return !IsBlocked(neighbor);
};

Node Capacity

Set the initial capacity to avoid reallocations:

var pathfinder = new AStar2D(initialCapacity: 1000);

The capacity grows automatically if needed, but pre-allocating improves performance.

Performance

Pathfinding performance depends on several factors:

• Node count: More nodes means slower searches.
• Heuristic accuracy: Better heuristics guide the search faster.
• Cost function complexity: Expensive cost functions slow down searches.

For real-time pathfinding, keep node counts reasonable and use efficient heuristics.

---

Back to Home