Skip to content
FutureBlitz

    Install

    Import std.algo.search

    std.algo.search

    std.algo's searches of graphs: breadth-first and depth-first search, Dijkstra, and A*. A graph is any values a successors Function steps between, so a grid's cells, a level's rooms, and a game's states are graphs alike, and a node is Hashable, so a search knows where it's been. A search takes its start, its successors, and a Function that says which nodes are the goal, and goes over a node's successors in the order successors gives them, so a run finds what the last did. A weighted step's cost is of any Numeric and Comparable type, Ints for exact sums, and isn't negative or NaN.

    std/algo/search.fb

    Types

    Path struct 

    Public Struct Path<N, C>

    A path a search found: its nodes from the start to the goal, both of them included, and its cost, the sum of its steps' weights.

    std/algo/search.fb, line 14

    • Public Field Nodes: N[] field #

      Its nodes, from the start to the goal, both of them included.

    • Public Field Cost: C field #

      The sum of its steps' weights.

    ShortestPaths class 

    Public Class ShortestPaths<N, C>

    The cheapest paths from a start to every node it reaches, as DijkstraAll finds them.

    std/algo/search.fb, line 22

    • Public Property Nodes: N[] property #

      The nodes reached, the cheapest first, the start among them.

    • Public Method Contains(node: N): Bool method #

      Whether the search reached the node.

    • Public Method CostTo(node: N): C? method #

      The cost of the cheapest path from the start to the node, or Null for one it didn't reach.

    • Public Method Parent(node: N): N? method #

      The node before this one on its cheapest path from the start, or Null for the start or one the search didn't reach.

    • Public Method PathTo(node: N): N[]? method #

      The cheapest path from the start to the node, both included, or Null for one it didn't reach.

    Functions

    Bfs function 

    Public Function Bfs<N: Hashable>(start: N, successors: Func(N): N[], goal: Func(N): Bool): N[]?

    The path with the fewest steps from start to the first node that goal says is one, by breadth-first search, or Null when none it reaches is.

    std/algo/search.fb, line 88

    BfsOrder function 

    Public Function BfsOrder<N: Hashable>(start: N, successors: Func(N): N[]): N[]

    The nodes start reaches, itself first, in the order breadth-first search meets them: those fewer steps away first.

    std/algo/search.fb, line 110

    Dfs function 

    Public Function Dfs<N: Hashable>(start: N, successors: Func(N): N[], goal: Func(N): Bool): N[]?

    A path from start to the first node that goal says is one, by depth-first search, which follows each successor as far as it goes before the next: not the shortest path, but found with only the path in hand. Null when none it reaches is the goal.

    std/algo/search.fb, line 134

    DfsOrder function 

    Public Function DfsOrder<N: Hashable>(start: N, successors: Func(N): N[]): N[]

    The nodes start reaches, itself first, in the order depth-first search meets them: a successor, and all it reaches, before the next successor.

    std/algo/search.fb, line 163

    Dijkstra function 

    @PanicsAtCaller Public Function Dijkstra<N, C>(start: N, successors: Func(N): (N, C)[], goal: Func(N): Bool): Path<N, C>?

    The cheapest path from start to the first node that goal says is one, by Dijkstra's algorithm, with each step's weight from successors, or Null when none it reaches is. A negative or NaN weight panics.

    std/algo/search.fb, line 295

    DijkstraAll function 

    @PanicsAtCaller Public Function DijkstraAll<N, C>(start: N, successors: Func(N): (N, C)[]): ShortestPaths<N, C>

    The cheapest paths from start to every node it reaches, by Dijkstra's algorithm, with each step's weight from successors. A negative or NaN weight panics.

    std/algo/search.fb, line 305

    AStar function 

    @PanicsAtCaller Public Function AStar<N, C>(start: N, successors: Func(N): (N, C)[], heuristic: Func(N): C, goal: Func(N): Bool): Path<N, C>?

    The cheapest path from start to the first node that goal says is one, by A*, which goes on first from where the cost so far, plus heuristic's guess of what's left to the goal, is least. For the path to be the cheapest, the guess can't be more than what's left, as a straight line's length isn't. Null when no node it reaches is the goal. A negative or NaN weight, or a NaN guess, panics.

    std/algo/search.fb, line 333

    Report an issue with this page or with FutureBlitz on GitHub.