Skip to content

Algorithms

Jump to bottom
Alexandre Mondaini Calvão edited this page Dec 3, 2025 · 1 revision

Algorithms

While PathfindingEngine is recommended for most use cases, you can also use the underlying algorithms directly.

Floyd-Warshall

Best for:

  • Dense graphs (many connections)
  • Static graphs that don't change often
  • Queries between many different node pairs
  • Games where you need all shortest paths precomputed

Overview

Floyd-Warshall computes shortest paths between all pairs of nodes in O(n³) time. After generation, any path query is O(1).

Usage

const pathfinding = @import("pathfinding");

var fw = pathfinding.FloydWarshall.init(allocator);
defer fw.deinit();

// Set size and initialize
fw.resize(100);  // Up to 100 nodes
try fw.clean();

// Add edges (node IDs are mapped internally)
fw.addEdgeWithMapping(100, 200, 10);  // entity 100 -> 200, weight 10
fw.addEdgeWithMapping(200, 300, 5);
fw.addEdgeWithMapping(100, 300, 20);  // Direct but longer

// Compute all shortest paths
fw.generate();

// Query
const dist = fw.valueWithMapping(100, 300);  // Returns 15 (100->200->300)
const next = fw.nextWithMapping(100, 300);   // Returns 200 (next hop)
const exists = fw.hasPathWithMapping(100, 300);  // Returns true

Path Reconstruction

var path = std.ArrayList(u32).init(allocator);
defer path.deinit();

try fw.setPathWithMapping(&path, 100, 300);
// path.items = [100, 200, 300]

API Reference

Method Description
init(allocator) Create instance
deinit() Free resources
resize(n) Set max node count
clean() Reset graph
addEdge(u, v, weight) Add edge (direct indices)
addEdgeWithMapping(u, v, weight) Add edge (entity IDs)
generate() Compute all paths
value(u, v) Get distance (indices)
valueWithMapping(u, v) Get distance (IDs)
next(u, v) Get next hop (indices)
nextWithMapping(u, v) Get next hop (IDs)
hasPath(u, v) Check path exists
hasPathWithMapping(u, v) Check path exists (IDs)
setPathWithMapping(list, u, v) Reconstruct full path

A* (A-Star)

Best for:

  • Large sparse graphs
  • Single source-destination queries
  • Dynamic graphs that change frequently
  • Real-time pathfinding

Overview

A* finds the shortest path from a start to a goal using a heuristic. It's computed on-demand, not precomputed.

Usage

const pathfinding = @import("pathfinding");

var astar = pathfinding.AStar.init(allocator);
defer astar.deinit();

astar.resize(100);
try astar.clean();

// Set heuristic
astar.setHeuristic(.manhattan);

// Set node positions (required for heuristic)
try astar.setNodePositionWithMapping(100, .{ .x = 0, .y = 0 });
try astar.setNodePositionWithMapping(200, .{ .x = 10, .y = 0 });
try astar.setNodePositionWithMapping(300, .{ .x = 10, .y = 10 });

// Add edges
astar.addEdgeWithMapping(100, 200, 10);
astar.addEdgeWithMapping(200, 300, 10);

// Find path
var path = std.ArrayList(u32).init(allocator);
defer path.deinit();

if (try astar.findPathWithMapping(100, 300, &path)) |cost| {
    // cost = total path cost
    // path.items = [100, 200, 300]
}

Heuristics

Heuristic Formula Best For
euclidean √((x₂-x₁)² + (y₂-y₁)²) Any-angle movement
manhattan |x₂-x₁| + |y₂-y₁| 4-directional grids
chebyshev max(|x₂-x₁|, |y₂-y₁|) 8-dir, equal diagonal cost
octile max(dx,dy) + (√2-1)·min(dx,dy) 8-dir, diagonal costs √2
zero 0 Dijkstra's algorithm 
astar.setHeuristic(.euclidean);   // Default
astar.setHeuristic(.manhattan);   // Grid games
astar.setHeuristic(.zero);        // Guaranteed optimal (Dijkstra)

API Reference

Method Description
init(allocator) Create instance
deinit() Free resources
resize(n) Set max node count
clean() Reset graph
setHeuristic(h) Set heuristic function
setNodePosition(idx, pos) Set position (index)
setNodePositionWithMapping(id, pos) Set position (ID)
addEdge(u, v, weight) Add edge (indices)
addEdgeWithMapping(u, v, weight) Add edge (IDs)
findPath(start, goal, path) Find path (indices)
findPathWithMapping(start, goal, path) Find path (IDs)

Comparison

Feature Floyd-Warshall A*
Precomputation O(n³) once None
Query time O(1) O(n log n) per query
Memory O(n²) O(n)
Graph changes Requires regenerate Immediate
Best for Static, dense, many queries Dynamic, sparse, few queries

When to Use Each

Use Floyd-Warshall when:

  • Your graph doesn't change during gameplay
  • You query paths between many different pairs
  • Graph is relatively small (< 1000 nodes)
  • You need instant path queries

Use A when:*

  • Graph changes frequently
  • You only need paths from one or few sources
  • Graph is large and sparse
  • Memory is constrained

Use PathfindingEngine when:

  • You want everything handled for you
  • You need spatial queries
  • You need entity position management
  • You're building a typical game

Clone this wiki locally