pathfinding

SIL - Exploring Mazes and Pathfinding - Graph Theory and Shortest Path Algorithms

(hi teachers this is my SIL, I did this so that the tooltips and whatnot could be customised to my liking and so that the demo could embed directly into the main page, if any issues please let me know)

I chose to explore maze generation and pathfinding because the subject combines rigorous mathematics, algorithmic logic, and a surprising amount of creativity. A maze looks deliberately complex, yet many maze algorithms rely only on simple graph concepts and a bit of randomness. Likewise, pathfinding algorithms such as A* and Dijkstra’s find optimal routes even though their decisions are made one step at a time. Programming these algorithms and watching them run side-by-side turned abstract definitions into living processes for me — the math began to feel tangible. I was also drawn by the clear real-world links: GPS route planning, robotic navigation and procedurally generated game levels all use the same core ideas.

As with last year’s SIL, I vibe coded a demo. If godot didnt mess up, it should be rendered below.

While researching on this topic, I found this interesting youtube short, which was a direct reference for the demo.

Graph theory

In graph theory, we study objects called graphs, which consist of vertices (or nodes) connected by edges . A maze can be modelled with graphs. Every cell becomes a vertex, and every removed wall creates an edge between two vertices. For example:

A path is simply a sequence of adjacent vertices.

A cycle is a closed path where you can return to the start without repeating edges.

A graph is connected if there is a path between any two vertices.

A tree is a connected graph with no cycles.

The grid itself, before walls are carved, is a special type of graph called a lattice graph — specifically a 2D rectangular lattice where each node has up to 4 neighbours. This graph is regular and predictable, but once walls are removed using an algorithm, the structure becomes far more interesting.

Representing a maze as a graph matters because the algorithms I used, A* and Dijkstra, all operate on graphs. They don’t care whether the graph came from a maze, a road network, or a social network. This abstraction is what allows these ideas to apply to everything from Google Maps to neural network architectures.

Graph theory provides useful tools for analysing the behaviour of the maze:

The maze generated by DFS Backtracking is guaranteed to be a spanning tree: a subgraph that connects all vertices with no cycles. This property mathematically ensures a unique solution path between any two points.

The absence of cycles makes the complexity of pathfinding easier to analyse, because algorithms like A* operate more predictably on trees.

The structure of the graph affects the search space: long corridors reduce branching factor, while dense branching increases it. Branching factor directly affects the time complexity of pathfinding algorithms.

Understanding these properties helped me see why different algorithms behave differently even on the same maze: the mathematics of the graph strongly influences the mathematics of the search.

Maze Generation

The DFS Backtracking algorithm is a direct application of depth-first traversal in graph theory. Traversal means systematically visiting all nodes of a graph, and DFS proceeds by always moving as far as possible along one branch before backtracking.

In mathematical terms, DFS explores the graph in a manner equivalent to a preorder tree traversal. When applied to maze generation, we treat each cell as a node and each potential passage as an edge. The algorithm builds the maze by gradually constructing a spanning tree of the grid graph.

DFS can be expressed recursively, but internally it always relies on a stack which is a last-in–first-out data structure, where both inputs and outputs are from the same end of the structure. This structure is essential because it ensures that backtracking happens in the reverse order of exploration.

At each step, the algorithm chooses a random unvisited neighbour. Random choice introduces non-determinism, which means that the algorithm can generate exponentially many possible spanning trees. This relates to a known concept in combinatorics: the number of spanning trees of a graph grows rapidly with graph size. On an n×n grid, the number is enormous — far too large to compute manually — which explains why each maze looks unique.

Because DFS never creates cycles, the final structure is always a tree. Trees have useful mathematical characteristics: Exactly V−1 edges for V vertices.

A unique simple path between any two vertices.

Average path length (tree height) depends on randomness and traversal behaviour.

This explains why DFS mazes tend to have long, winding corridors. The DFS procedure tends to create long branches before backtracking, meaning the resulting spanning tree is fairly “deep.” This property can even be analysed statistically: DFS mazes have a characteristic path-length distribution that differs from Prim’s or Kruskal’s mazes. Understanding the maze as a spanning tree gave me a clear mathematical reason for the maze’s visual and navigational behaviour.

This was done in my simulation through the below approach.

A maze of size ( w \times h ) is represented as a graph:

  • Each cell is a vertex.
  • Between any two adjacent cells, there is a possible edge.
  • Initially, all edges are “blocked” by walls.

Formally:

[ G = (V, E) ]

where

  • ( V = w \cdot h )
  • Each vertex has up to 4 neighbors: [ \text{deg}(v) \le 4 ]

The list:

const DIRS := [
    Vector2i(0, -1),  # up
    Vector2i(1, 0),   # right
    Vector2i(0, 1),   # down
    Vector2i(-1, 0)   # left
]

encodes the adjacency relation between vertices. This is equivalent to defining the edge set mathematically as:

[ E = {(v, v + d) \mid d \in \text{DIRS and within grid}} ]

Maze Representation

Each cell stores:

[up, right, down, left]

with:

  • true → wall exists (edge is blocked)
  • false → passage (edge is open)

This is equivalent to storing the adjacency matrix of a planar grid graph but compressed per vertex.

The algorithm used is DFS Backtracking, which mathematically produces a random spanning treeof the grid graph.

A perfect maze must have:

  • exactly one unique path between any two cells → meaning no cycles
  • all cells reachable → meaning connected

A structure that is connected and cycle-free is, by definition, a tree.

Thus the algorithm constructs a spanning tree.

Algorithm Description (Mathematical Form)

The algorithm:

  1. Choose a start vertex ( v_0 ).

  2. Repeatedly:

    • Look for an unvisited neighbor ( u in N(v) ).
    • Choose one randomly.
    • Add edge ( (v, u) ) to the spanning tree.
    • Move to ( u ).
  3. If a vertex has no unvisited neighbors, backtrack.

This is equivalent to performing DFS on an undirected graph, but with randomized choices.

More formally:

[ T = { (v, Next(v)) during DFS traversal } ]

Because DFS never revisits a cell and never adds an edge to an already-visited vertex, cycles cannot form.

This code:

var unvisited_neighbors := []
for i in range(DIRS.size()):
    var nx = current.x + DIRS[i].x
    var ny = current.y + DIRS[i].y
    if nx >= 0 and nx < width and ny >= 0 and ny < height:
        if not visited[ny][nx]:
            unvisited_neighbors.append(i)

mathematically checks:

This is a classical neighbor set:

[ N(v) = { v + d in DIRS } ]

restricted by grid boundaries.

The “grid boundary” condition defines the domain of the graph.

This line:

var dir_index = unvisited_neighbors[rng.randi_range(0, unvisited_neighbors.size() - 1)]

implements a uniform random selection from a discrete set.

This randomness ensures the spanning tree produced is not deterministic unless seeded.

When the algorithm chooses a neighbor and moves there, it “knocks down” walls:

grid[current.y][current.x][dir_index] = false
grid[next.y][next.x][opposite] = false

The opposite direction uses modular arithmetic:

[ opposite = (i + 2) \mod 4 ]

This matches the fact that grid directions are symmetric:

  • up ↔ down
  • right ↔ left
var stack: Array = []
stack.append(start)

The DFS stack represents the recursion structure of DFS.

Whenever the algorithm backtracks:

stack.pop_back()

this is equivalent to returning from a recursive DFS call.

When the algorithm terminates:

  • The visited set contains all vertices → connected
  • No cell was visited twice → acyclic
  • There are exactly ( w \cdot h - 1 ) passages (edges in a spanning tree)

Thus the maze is guaranteed to be a perfect maze— one path between any two points.

A* Pathfinding

A* is essentially an optimisation algorithm that solves the shortest-path problem using both real and estimated information. It is built on the idea of best-first search, but mathematically enhanced by evaluating each node using the formula: f(n)=g(n)+h(n) where g(n) is the known cost so far, h(n) is the heuristic, a mathematical estimate of future cost and f(n) is the total estimated cost of the best path passing through n.

The mathematical strength of A* comes from its use of heuristics.

  1. Admissibility
    • A heuristic h(n) is admissible if it never overestimates the true cost to reach the goal. For Manhattan distance on a grid, this is true because each move reduces the Manhattan distance by at most 1. By guaranteeing h(n)≤h*(n) (where h*(n)h^*(n)h*(n) is the true optimal cost), A* is mathematically guaranteed to find an optimal path.
  2. Consistency (Monotonicity)
    • A heuristic is consistent if:
    • h(n)≤cost(n,n′)+h(n′)h(n) - This ensures the estimated total cost f(n) never decreases along a path. Consistency means A* never needs to revisit a node once it has found the best path to it. This reduces time complexity significantly.
  3. Search-space reduction
    • One of the most mathematically powerful aspects of A* is the reduction in explored nodes. Without a heuristic, Dijkstra explores in all directions equally. A* explores a cone of directions that point roughly toward the goal. The branching factor and depth determine the theoretical complexity: Dijkstra: O(bd) in the worst case. A*: O(bd−k), where k depends on heuristic strength.

Thus, even a simple heuristic dramatically improves efficiency.

  1. Relationship to optimisation
    • A* can be viewed as minimising a cost function. In optimisation terms, it finds the path that minimises the energy f(n). This parallels gradient descent and other optimisation algorithms, showing how deep the mathematical connections run.

This was done with the below code.

extends Node
class_name Solver

signal path_updated(path: Array)
signal open_closed_updated(open_set: Array, closed_set: Array)

What this does

  • Declares a base Solver node you can reuse/extend.

  • Defines two signals:

    • path_updated(path) — emitted when a full path is reconstructed (used by UI to draw the path).
    • open_closed_updated(open_set, closed_set) — emitted each step so UI can display the current open/closed sets.
var astar: AStar2D
var width: int
var height: int

var start_id: int
var goal_id: int

var open_set: Array = []
var closed_set: Array = []
var came_from: Dictionary = {}
var g_score: Dictionary = {}
var f_score: Dictionary = {}
var path_computed: bool = false
var current_path: Array = []

State / data structures

  • astar: reference to an AStar2D graph helper (provides neighbor lists and position lookup).
  • width, height: grid dimensions — used to convert between (x,y) and linear node IDs.
  • start_id, goal_id: integer IDs for start/goal nodes (IDs are computed as y * width + x).
  • open_set: nodes to be considered (frontier). For A*, this is usually a priority queue, but here it’s a plain Array.
  • closed_set: nodes already processed.
  • came_from: Dictionary mapping node -> predecessor for path reconstruction.
  • g_score: Dictionary mapping node -> cost from start.
  • f_score: Dictionary mapping node -> g + heuristic.
  • path_computed: flag indicating algorithm finished (found path or exhausted).
  • current_path: final path as an array of Vector2i positions.
func setup(astar_ref: AStar2D, w: int, h: int) -> void:
	astar = astar_ref
	width = w
	height = h

setup

  • Stores references to the AStar2D helper and grid dimensions.
  • Call this once before solving.
func start_solver(start: Vector2i, goal: Vector2i) -> void:
	start_id = start.y * width + start.x
	goal_id = goal.y * width + goal.x

	open_set.clear()
	closed_set.clear()
	came_from.clear()
	g_score.clear()
	f_score.clear()
	current_path.clear()
	path_computed = false

	initialize_open_set()
	emit_signal("open_closed_updated", open_set, closed_set)

start_solver

  • Converts Vector2i positions to linear node IDs using id = y * width + x.
  • Clears all previous state so the solver starts fresh.
  • Calls initialize_open_set() — an overridable method where different algorithms put the initial node(s) into open_set and set initial scores.
  • Emits open_closed_updated so a UI or visualizer can immediately show the starting frontier.
# Override this in child classes
func initialize_open_set() -> void:
	pass

initialize_open_set

  • Meant to be implemented by subclasses (e.g., A* puts the start in open_set and sets g_score/f_score).
func step_solver() -> bool:
	if path_computed or open_set.is_empty():
		path_computed = true
		return true

	var current := pick_next_node()
	if current == goal_id:
		reconstruct_path(current)
		path_computed = true
		return true

	move_current_to_closed(current)

	process_neighbors(current)

	emit_signal("open_closed_updated", open_set, closed_set)
	return false

step_solver — single-step driver

  • This is the main per-frame / per-tick method. Returns true if the algorithm is finished.

  • Behavior:

    1. If path_computed is already true or open_set is empty (no path), mark done and return true.
    2. Choose the next node to process by calling pick_next_node() (overridable).
    3. If current is the goal_id, reconstruct the path and finish.
    4. Move the current node from open_set to closed_set.
    5. process_neighbors(current) — relax neighbor edges and update scores.
    6. Emit open_closed_updated so the UI sees the latest open/closed sets.
    7. Return false (not done) so caller can continue stepping.

This design makes it easy to run one solver step per frame to visualize progress.

func pick_next_node() -> int:
	return open_set[0]

pick_next_node (base)

  • Default chooses the first element of open_set.
  • Subclasses (like A*) override this to pick the node with smallest f_score.
func move_current_to_closed(current: int) -> void:
	open_set.erase(current)
	closed_set.append(current)

move_current_to_closed

  • Removes current from open_set and appends it to closed_set.
  • open_set.erase(current) removes only the first occurrence — fine if each node appears once.
func process_neighbors(current: int) -> void:
	for neighbor in astar.get_point_connections(current):
		if neighbor in closed_set:
			continue
		var tentative_g = g_score.get(current, 999999) + 1
		if neighbor not in open_set:
			open_set.append(neighbor)
		elif tentative_g >= g_score.get(neighbor, 999999):
			continue
		came_from[neighbor] = current
		g_score[neighbor] = tentative_g
		f_score[neighbor] = tentative_g + get_heuristic(neighbor)

process_neighbors — relaxing edges

  • For each neighbor of current (via astar.get_point_connections(current)):

    • Skip if neighbor is in closed_set.
    • tentative_g = g_score[current] + 1. The +1 assumes uniform cost between adjacent cells.
    • If neighbor not in open_set, add it (discover the node).
    • If the new tentative_g is not better than the neighbor’s current g_score, skip.

    • Otherwise:

      • Set came_from[neighbor] = current to record path.
      • Update g_score[neighbor].
      • Update f_score[neighbor] = g + heuristic(neighbor).

  • Notes:

    • g_score.get(..., 999999) uses 999999 as a stand-in for infinity.
    • This is standard A*/Dijkstra relaxation logic. If get_heuristic returns 0, algorithm behaves like Dijkstra.
func get_heuristic(id: int) -> int:
	return 0  # default Dijkstra/BFS has no heuristic

get_heuristic

  • Base implementation returns 0 so base Solver is effectively Dijkstra (no heuristic).
  • Subclasses override to provide heuristic estimates (e.g., Manhattan distance).
func reconstruct_path(current: int) -> void:
	var temp := current
	var id_path: Array = [temp]
	while came_from.has(temp):
		temp = came_from[temp]
		id_path.insert(0, temp)

	var path_vec: Array = []
	for id in id_path:
		var v := astar.get_point_position(id)
		path_vec.append(Vector2i(int(v.x), int(v.y)))
	current_path = path_vec
	emit_signal("path_updated", current_path)

reconstruct_path

  • Walks backward from current (goal) to start using came_from.
  • Builds id_path in reverse then converts each node ID back to Vector2i using astar.get_point_position(id).
  • Stores the resulting current_path and emits path_updated so visuals can render the full route.
func get_current_path() -> Array:
	return current_path

getter

  • Returns the computed path (array of Vector2i) for external code to read.

AStar subclass 


extends Solver
class_name AStarSolver

func get_heuristic(id: int) -> int:
	var pos := astar.get_point_position(id)
	var goal_pos := astar.get_point_position(goal_id)
	return int(abs(pos.x - goal_pos.x) + abs(pos.y - goal_pos.y))  # Manhattan

func pick_next_node() -> int:
	var best = open_set[0]
	for id in open_set:
		if f_score.get(id, 999999) < f_score.get(best, 999999):
			best = id
	return best

func initialize_open_set() -> void:
	open_set.append(start_id)
	g_score[start_id] = 0
	f_score[start_id] = get_heuristic(start_id)

What AStarSolver changes

  • get_heuristic: returns Manhattan distance between node and goal (|dx| + |dy|). Good for 4-way grid movement.
  • pick_next_node: scans open_set and returns the node with smallest f_score. (Because open_set is a plain array, this is O(n) per pick. Performance can be improved with a binary heap.)
  • initialize_open_set: seeds the algorithm by adding start_id to open_set, setting g_score[start] = 0, and f_score[start] = heuristic(start).

Dijkstra’s

Dijkstra’s Algorithm solves the single-source shortest path problem on graphs with non-negative edge weights . It does so by repeatedly selecting the node with the smallest tentative distance and “relaxing” its neighbours.

  1. Distance relaxation updates the estimated distance to a node. This iterative refinement is essentially dynamic programming: each update narrows the gap between the tentative and true shortest path values.

  2. The algorithm is correct because once a node is extracted from the priority queue, its tentative distance is guaranteed to be the true shortest distance. That happens because all edge weights are non-negative, so no later path can “shortcut” back to this node. This property fails if negative edges exist, which explains why Dijkstra cannot handle them.

  3. Special case: unweighted grids In an unweighted maze, every edge has weight of 1, which simplifies Dijkstra to:

    • Equivalent to BFS

    • Expands nodes in concentric layers

    • Uses a queue instead of a priority queue

Thus, Dijkstra’s behaviour becomes mathematically predictable and symmetric. This is because A* reduces to Dijkstra when h(n)=0. In other words, Dijkstra = A with no heuristic. This mathematical relationship shows how closely the two algorithms are connected.

Reflections

This project deepened my appreciation for how relatively simple mathematical ideas can power complex systems like traffic routing, public transport scheduling, and even evacuation planning, which use the same principles of graph modelling and shortest-path optimisation. In robotics, pathfinding must be combined with obstacle avoidance and sensor uncertainty; the algorithms I studied are the foundation for those higher-level systems.