Pathfinding

Finds routes across weighted square grids or your own waypoint graphs, at once or a little each frame.

Commands

Import blitz.pathfinding As PF gives your program these, with PF. in front. Each name leads to its part of the reference.

Functions

• CreateGrid:Grid(width:Int, height:Int, diagonals:Int = False)
• GridNode:Int(grid:Grid, x:Int, y:Int)
• SetCell(grid:Grid, x:Int, y:Int, cost:Double = 1D)
• BeginSearch:Search(graph:Graph, startNode:Int, goal:Int)
• StepSearch:Int(search:Search, work:Int = 256)
• SearchState:Int(search:Search)
• TakeRoute:Route(search:Search)
• FindPath:Route(graph:Graph, startNode:Int, goal:Int)

Types

• Grid Implements Graph
  Methods ValidNode:Int(node:Int), NeighbourCount:Int(node:Int), Neighbour:Int(node:Int, index:Int), Cost:Double(fromNode:Int, toNode:Int), Estimate:Double(fromNode:Int, goal:Int), Revision:Long()
• Route
  Methods Count:Int(), Node:Int(index:Int), Status:Int(), TotalCost:Double()
• Search
  Methods WorkDone:Long(), EdgesExamined:Long(), NodesExpanded:Long(), PeakItems:Int()

Interfaces

• Graph
  Methods you write ValidNode:Int(node:Int), NeighbourCount:Int(node:Int), Neighbour:Int(node:Int, index:Int), Cost:Double(fromNode:Int, toNode:Int), Estimate:Double(fromNode:Int, goal:Int), Revision:Long()

Enums

• SearchStatus
  Values Pending, Found, NoRoute, Stale, LimitExceeded

Guide

Pathfinding finds the way from one place to another: round walls, through gaps, and the long way round a bog when that's quicker than wading through it. You describe your map as a grid of cells, each with a cost to walk into, and ask for a route. You get back the cells to visit, in order, and your game moves its characters along them.

Try it

Open route.bb and run it. Click anywhere to find a route from the top-left corner. Click a wall to see what happens when there's no way there.

; Click anywhere to find a route from the top-left corner, round the walls
; and the mud. Escape quits.
Dialect "modern"
Import blitz.pathfinding As PF

Const CELL:Int = 32 ; Each cell is 32 pixels square.
Graphics 640, 510, 0, 2
SetBuffer BackBuffer()
ClsColor 18, 52, 79

; A 20 by 15 grid where routes may also go diagonally. Every cell costs 1 to
; enter until we change it. We keep our own copy of the costs to draw them.
Local grid:PF.Grid = PF.CreateGrid(20, 15, True)
Dim cost:Double(19, 14)
Local x:Int
Local y:Int
For y = 0 To 14
    For x = 0 To 19
        cost(x, y) = 1D
        If x = 6 And y < 11 Then cost(x, y) = 0D  ; A cost of zero is a wall.
        If x = 13 And y > 3 Then cost(x, y) = 0D
        If x >= 8 And x <= 11 And y >= 5 And y <= 9 Then cost(x, y) = 5D ; Mud.
        PF.SetCell grid, x, y, cost(x, y)
    Next
Next

Local start:Int = PF.GridNode(grid, 1, 1)
Local route:PF.Route = PF.FindPath(grid, start, PF.GridNode(grid, 18, 13))

While Not KeyDown(1)
    ; GridNode needs a cell on the grid, so ignore clicks below it.
    If MouseHit(1) And MouseY() < 15 * CELL
        Delete route
        route = PF.FindPath(grid, start, PF.GridNode(grid, MouseX() / CELL, MouseY() / CELL))
    EndIf

    Cls
    For y = 0 To 14
        For x = 0 To 19
            If cost(x, y) = 0D
                Color 110, 120, 140
            ElseIf cost(x, y) > 1D
                Color 120, 80, 40
            Else
                Color 30, 70, 110
            EndIf
            Rect x * CELL + 1, y * CELL + 1, CELL - 2, CELL - 2, True
        Next
    Next
    ; A route is a list of nodes. On a grid, each node is y * width + x.
    Color 255, 220, 0
    Local index:Int
    For index = 0 To route.Count() - 1
        Local node:Int = route.Node(index)
        Oval (node Mod 20) * CELL + 10, (node / 20) * CELL + 10, 12, 12, True
    Next
    Color 255, 255, 255
    If route.Status() = PF.SearchStatus.Found
        Text 8, 488, "Route: " + route.Count() + " cells, cost " + Float(route.TotalCost())
    Else
        Text 8, 488, "No way through to there"
    EndIf
    Flip
Wend
Delete route
Delete grid
End

A cell's cost is how hard it is to walk into. A cost of 1 is ordinary ground, higher costs are harder going, and 0 makes a wall. The route above goes round the mud, which costs 5, because walking round is cheaper than wading through.

How do I...

Move a character along the route?

Visit the route's cells in order, starting from Node(0), which is where the character already is. On a grid, each node is the cell's y * width + x, so you can turn it back into a cell:

Local node:Int = route.Node(nextStep)
Local cellX:Int = node Mod 20 ; 20 is the grid's width.
Local cellY:Int = node / 20

Move a little towards that cell each frame. When you reach it, go on to nextStep + 1, until nextStep reaches route.Count().

Change the map while the game runs?

Call SetCell whenever you like. A route you already have doesn't change, so find a new one after the map does, such as when a door opens:

PF.SetCell grid, 6, 4, 1D ; A door in the wall opens.
Delete route
route = PF.FindPath(grid, start, goal)

Find long routes without the game stuttering?

Spread the search over several frames. Start it once, then do a little of it each frame until it's done.

Local search:PF.Search = PF.BeginSearch(grid, start, goal)
; Then, each frame:
If search <> Null
    PF.StepSearch search, 256 ; Do up to 256 units of work.
    If PF.SearchState(search) <> PF.SearchStatus.Pending
        Delete route
        route = PF.TakeRoute(search)
        Delete search ; The route is yours now, and outlives the search.
        search = Null
    EndIf
EndIf

If the map changes before a search finishes, its route's status is Stale: start a new search.

Let routes go diagonally?

Pass True as the third value when you make the grid, as the program above does. A diagonal step never cuts across the corner of a wall.

Use waypoints instead of a grid?

Write a Type that Implements PF.Graph, with six methods that tell the module which places there are, which ones lead to which, and what each step costs. The reference below explains them, and waypoints.bb has a complete one.

Blip's tip

To block a cell, give it a cost of 0, not just a big number. A big cost is only very deep mud: if there's no other way, the route will still go through it.

Good to know

• Check the route's status. Found means there's a route. NoRoute means there's no way there, or the start or the goal is a wall. Stale means the map changed during a search, and LimitExceeded that a search grew too big.
• A route includes both ends. Its first node is the start and its last the goal.
• The first cell is free. TotalCost counts what it costs to walk into each cell after the first.
• Delete what you're given. Delete each route when you've finished with it, and delete searches before their grid.

More examples

Three more complete programs come with the module:

• find_route.bb finds routes across a bigger map, with a gate that Space opens and closes, and a cell you can never reach.
• maze.bb sends a cube through a 3D maze along its route. Space sends it back again.
• waypoints.bb finds routes through waypoints of its own, two searches at a time, spread over several frames.

The reference below has every function and rule.

Reference

Needs

No other modules

Examples

find_route.bb, maze.bb, waypoints.bb

Find routes through weighted square grids or your own directed waypoint graph. The library owns no entities, clocks, windows or game loop. There are no module dependencies. Extended mode with object-lifecycle-v1 is required; Original is not supported. This is an unpublished preview, with no frozen 1.0 interface.

For characters finding their way through a 3D world, over terrain, up stairs and between the floors of a building, use the engine's Navigation commands (FindNavPath and the rest) instead: they work out where characters can walk from the world itself and keep it up to date. Grids and graphs remain the right tool for board games, tile maps, puzzles and abstract graphs.

Start here

Blitz3D+ comes with this module, so any Extended program can Import blitz.pathfinding.

Dialect "modern"
Import blitz.pathfinding As PF
Local grid:PF.Grid = PF.CreateGrid(30, 20)
PF.SetCell grid, 5, 4, 0D ; zero blocks; positive cost is paid on entry
PF.SetCell grid, 6, 4, 3D ; expensive ground
Local route:PF.Route = PF.FindPath(grid, PF.GridNode(grid, 1, 1), PF.GridNode(grid, 28, 18))
If route.Status() = PF.SearchStatus.Found
    Local index:Int
    For index = 0 To route.Count() - 1
        Print route.Node(index)
    Next
    Print route.TotalCost()
Else
    Print "No route on this map revision"
EndIf
Delete route
Delete grid
End

Open one of these complete programs and run it:

Run a built example with --verify for the finite check. All geometry and pixels are generated in source. Examples create no persistent files.

Grid and route API

SearchStatus.Pending=0, Found=1, NoRoute=2, Stale=3, LimitExceeded=4. The enum contains Int constants, not a checked runtime type. Invalid/blocked endpoints produce NoRoute; start=goal produces one node only when traversable. A completed result is an immutable snapshot: later graph edits do not alter it or its terminal status.

Diagonal steps cost sqrt(2) * destinationCost. Both orthogonally adjacent side cells must be traversable: diagonals never squeeze past even one blocked corner. Neighbours have stable N,E,S,W,NE,SE,SW,NW order. The grid's Manhattan/octile estimate uses a safe lower bound initially 1, reduced when a cheaper traversable cell appears. Increasing costs/blocking does not raise that bound, so edits stay O(1); an overly low bound may increase search work but preserves admissibility.

Incremental work

Local search:PF.Search = PF.BeginSearch(grid, 0, 599)
; In the game's update, after map changes and before drawing:
PF.StepSearch search, 256
If PF.SearchState(search) <> PF.SearchStatus.Pending
    Local completed:PF.Route = PF.TakeRoute(search)
    ; Use completed, then Delete completed when finished.
EndIf
; Keep grid alive until every borrowing search has been deleted.
Delete search

The example fragment shows one update, not a hidden loop. The waypoint example shows a complete application including transferred-result cleanup.

A unit is one state-machine transition, one heap sift level (at most two priority comparisons), one edge examination/relaxation, or one reconstructed route node. Push/pop setup, stale-entry inspection, endpoint initialisation and the end of an adjacency list are also charged. Work never includes a whole variable-length neighbour loop or path reversal. A reverse-owned node list gives O(1) forward queries without a final unbudgeted copy. FindPath uses this exact state machine.

Operation counts are not a time/frame guarantee. Graph callbacks must be bounded and nonblocking; List growth, Map rehashing and allocations can have variable latency. Grid creation is O(width×height). Explicit deletion is linear in retained scratch objects and lies outside the incremental budget. No hidden MilliSecs, sleep, input polling, rendering or random state appears in the module.

Per search, at most 2,097,152 logical records/heap entries/route nodes may be retained; additions check the cap before allocation. Reaching it finishes the search as SearchStatus.LimitExceeded (an empty route), distinct from NoRoute, so a game can fall back instead of ending. Collections may reserve spare capacity, and runtime object/Map overhead is platform-dependent. Independent searches have independent caps; the application still controls how many it creates.

Implement your own Graph

Grid Implements Graph. A custom Type must explicitly implement all six public methods, as examples/waypoints.bb demonstrates. No engine entities are exposed.

For one revision the graph must be finite and callbacks deterministic. A* orders by (estimated total cost, larger accumulated cost, insertion sequence), so on open uniform maps it expands about one route's worth of tied cells rather than all of them. Strict improvements reopen previously expanded nodes and obsolete entries are discarded when popped. This supports admissible but inconsistent heuristics. With nonnegative edges, admissibility and h(goal)=0, a popped goal has optimal cost because no frontier can lead to a cheaper remaining solution. Overestimating forfeits that guarantee. Do not use world-space distance unless its scale is a valid cost lower bound. With V discovered records, E examined edges, R successful relaxations, H maximum heap occupancy and L route length, expected work is O(E + R log H + L), plus popped/stale entry heap work, and storage is O(V + H + L). Admissible inconsistent heuristics can reopen records many times; no one-expansion-per-node bound is promised. Map lookup is expected constant time. Accumulated-cost/priority overflow, nonfinite values, bad neighbour IDs, negative counts and nonzero goal estimates fail clearly. Double arithmetic can round; compare independently computed noninteger totals using a documented tolerance.

Revision is checked before every charged unit and after each data callback. A change aborts as Stale immediately, including during reconstruction. No partial route can be transferred as Found. Revision() itself must faithfully report the current version; hidden edits or dishonest revisions cannot be detected.

Callbacks may observe SearchState and counters. They must not call BeginSearch, StepSearch or FindPath recursively, including through a different search. A module phase guard rejects this. They must not take an active search's result or delete the active Search/Graph. Active-search deletion and deleted borrowed graphs have diagnostics, but deletion is not a deferred-action facility. Set a game-owned request flag and delete/cancel after the outer call returns. Graph mutation is permitted if it updates revision; the current search becomes Stale.

Ownership and errors

Constructors and representation are private. Null/deleted resources passed to operations are programming errors. Null/already-deleted aliases remain safe to Delete. Leaving scope or assigning Null does not call destructors. Deleting a search has cancellation meaning only; no Stop, Save, Commit or implicit success operation is invented. Two searches can safely share a graph when driven in separate application calls. These are main-thread libraries, not Worker code.

Typical failures: PF.CreateGrid(0,20) rejects dimensions; PF.SetCell grid,0,0,-1D rejects a cost; PF.StepSearch search,-1 rejects work; route.Node(route.Count()) rejects an index. NoRoute, Stale and LimitExceeded are expected statuses, not LastError failures. There is no recoverable I/O/configuration operation, so no LastError API is needed.

Deferred: smoothing (clearance/terrain semantics need explicit opt-in), entity movement APIs, worker adapters and cross-module adapters. Navigation meshes and walkability worked out from geometry are the engine's Navigation commands. Movement in the maze is intentionally owned by the example.