Math and Space

Graph

Weighted graphs with pathfinding (A*, Dijkstra, BFS), flow fields, grids, spanning trees, cycles and components.

PackageShared

Getting it

local Graph = Engine:GetPackage("Graph")

A graph is a set of nodes connected by edges with a cost. Rooms connected by doors, waypoints connected by paths, quests that unlock other quests: all graphs. This package gives you the data structure plus the classic algorithms to search it.

Grid pathfinding with walls

local Graph = Engine:GetPackage("Graph")

local walls = { ["3,2"] = true, ["3,3"] = true, ["3,4"] = true }

local grid = Graph.GridGraph(10, 10, function(x, y)
	if walls[Graph.GridKey(x, y)] then
		return nil -- not walkable
	end
	return 1
end, true)

local path = Graph.AStar(grid, Graph.GridKey(1, 3), Graph.GridKey(8, 3), Graph.GridHeuristic)
for _, key in path or {} do
	print(Graph.GridCoords(key))
end

Building a graph

new

Graph.new(directed: boolean?): Graph

An empty graph. Undirected by default: an edge from A to B also goes from B to A.

Member	Description
`IsDirected`, `NodeCount`, `EdgeCount`, `IsEmpty`	Read-only.
`:AddNode(id, data?): id`	Adds a node. Any value can be an id. `data` is free to use.
`:GetNodeData(id)`	The node's data.
`:RemoveNode(id): boolean`	Removes a node and its edges.
`:HasNode(id): boolean`
`:AddEdge(a, b, cost)`	Connects two nodes.
`:RemoveEdge(a, b): boolean`, `:HasEdge(a, b): boolean`
`:GetEdgeCost(a, b): number?`
`:Neighbors(id): { id }`	Nodes reachable in one step.
`:OutEdges(id): { { To, Cost } }`	Outgoing edges.
`:Nodes()`, `:Edges()`	Every node id, every edge as `{ From, To, Cost }`.
`:Clear()`, `:Clone()`
`:Transpose(): Graph`	A copy with every edge reversed.

Shortest paths

Function	Description
`Graph.AStar(graph, start, goal, heuristic?)`	The cheapest path as a list of node ids, or `nil`. A heuristic that estimates the remaining cost (never overestimating) makes it much faster.
`Graph.Dijkstra(graph, start)`	Cheapest cost to every node, plus a `previous` map. Costs must not be negative.
`Graph.BellmanFord(graph, start)`	Like Dijkstra but allows negative costs. The third result is `false` when a negative cycle makes costs meaningless.
`Graph.BFS(graph, start)`	Fewest steps to every node, ignoring costs.
`Graph.FloydWarshall(graph)`	Cheapest cost between every pair of nodes. Fine for small graphs.
`Graph.ReconstructPath(previous, start, goal)`	Turns a `previous` map into a path list, or `nil`.
`Graph.DFS(graph, start)`	Nodes in depth-first visiting order.

Flow fields

Graph.FlowField(graph: Graph, goal: NodeId): { [NodeId]: NodeId }

For every node, the next node to step to on the cheapest way to goal. One flow field serves any number of units heading to the same goal, which is far cheaper than running A* for each of them.

local flow = Graph.FlowField(grid, Graph.GridKey(8, 3))
local nextStep = flow[currentKey]

Structure

Function	Description
`Graph.TopoSort(graph)`	Nodes ordered so every edge points forward (a directed graph without cycles), or `nil` if there is a cycle. Use it for unlock trees and build orders.
`Graph.HasCycle(graph)`	Whether the graph contains a cycle.
`Graph.ConnectedComponents(graph)`	Groups of nodes connected to each other.
`Graph.StronglyConnectedComponents(graph)`	For directed graphs: groups where every node can reach every other.
`Graph.Kruskal(graph)`, `Graph.Prim(graph, start?)`	Minimum spanning tree: the cheapest set of edges that connects everything. Return the edges and the total cost.

Grids

Function	Description
`Graph.GridGraph(w, h, costFn?, allowDiagonals?)`	A `w` by `h` grid graph. `costFn(x, y)` returns the cost of entering a cell, or `nil` for a wall. Diagonal moves cost more by `DiagonalCostMultiplier`. Node data is `{ X, Y }`.
`Graph.GridKey(x, y)`	The node id of a cell, `"x,y"`.
`Graph.GridCoords(key)`	Back to `x, y`.
`Graph.GridHeuristic(a, b)`	Manhattan distance between two grid keys, for A*.

Configuration

Defaults from DefaultConfiguration/Packages/Graph4 settings

Setting	Default	What it does
DefaultDirected	false	Whether Graph.new() builds a directed graph when not specified.
DefaultAllowDiagonals	false	Whether Graph.Grid() links diagonal neighbours when not specified.
DiagonalCostMultiplier	math.sqrt(2)	Edge cost multiplier for diagonal grid moves.
GridCellCost	1	Base edge cost between two adjacent grid cells.

Types

export type NodeId = any
export type EdgeInfo = { To: NodeId, Cost: number }
export type EdgeRecord = { From: NodeId, To: NodeId, Cost: number }
export type Distances = { [NodeId]: number }
export type Previous = { [NodeId]: NodeId }
export type Heuristic = (NodeId, NodeId) -> number
export type Graph