Dijkstra's Algorithm – Unity Step Simulator

Interactive DAA prototype (CIA): a step-by-step visualiser of Dijkstra's single-source shortest path algorithm (Greedy paradigm), built in Unity 2D with C#. Companion to the blog post "Dijkstra's Algorithm: Finding Shortest Paths with a Greedy Strategy".

System Overview

The simulator runs Dijkstra once, records the full algorithm state after every step as a Snapshot, and then plays those snapshots back. Because the whole run is precomputed, you can play, pause, step forward, step backward and jump to the start or end at any time.

What the screen shows at every step:

Panel	Purpose
Graph view	Node colour = state (grey unvisited, blue in queue, yellow picked, green final). Edge colour = examined (yellow), just relaxed (orange), shortest-path-tree (green)
Pseudocode	The line being executed is highlighted
"What just happened"	Plain-English explanation with the actual arithmetic, e.g. 2 + 1 = 3 < 4 → YES
Vertex table	dist, parent, and status of every vertex
Priority queue	Contents of Q sorted by distance (front = next EXTRACT-MIN)
Counters	Relaxation attempts and successful updates (ties to the complexity analysis)

Stages demonstrated: initialisation → EXTRACT-MIN of the closest unvisited vertex → relaxation of each incident edge (compare, update or reject) → repeat until Q is empty → final dist[]/parent[] and shortest-path reconstruction.

Controls (original keyboard and mouse; the handheld shell below maps them onto its buttons)

Input	Action
Play / Pause, Space	Auto-play at the chosen speed
> / <, → / ←	Step forward / back
`	</>
Left-click a vertex	Make it the new source and rerun
Right-click a vertex (after the last step)	Highlight its shortest path in pink and show the cost
Randomize weights / Default weights	New random edge weights (1–12) or the blog's example graph

The default graph is the same one used in the blog (A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2). From A the final distances are B = 3, C = 2, D = 8, E = 10 and the path to E is A → C → B → D → E (cost 10).

Setup Instructions

1. Install Unity 2021.3 LTS or newer (Unity 6 works). Create a new 2D (Built-in) or 2D URP project.
2. Copy the three scripts into Assets/Scripts/:
   • DijkstraEngine.cs
   • GraphView.cs
   • SimulatorController.cs
   • ChalkSkin.cs
   SimulatorController retargets Camera.main to a RenderTexture at runtime, so leave your scene's Main Camera in place (or none, one is created).
   Copy the Resources/Shaders/ folder (4 files: ChalkCommon.cginc, ChalkNode.shader, ChalkLine.shader, Chalkboard.shader) to Assets/Resources/Shaders/. It must sit under a Resources folder so the shaders are included in builds. If they are missing, the sim logs a warning and falls back to the plain flat look.
   Font: put the handwriting TTF at Assets/Resources/Fonts/PatrickHand-Regular.ttf (Patrick Hand, Google Fonts). The loader also accepts Resources/ChalkFont. Shaders are found whether they sit in Resources/ or Resources/Shaders/.
   Script file names should match the class names exactly (GraphView.cs, SimulatorController.cs, ChalkSkin.cs). Unity requires this for MonoBehaviours.
3. Open any scene (the default SampleScene is fine). No GameObjects to add. The controller spawns itself on Play via [RuntimeInitializeOnLoadMethod] and creates the camera settings, graph and UI in code.
4. Press Play. Set the Game view to Full HD (1920x1080) or Free Aspect.

Notes:

• The UI uses IMGUI (OnGUI) with Event.current, so it works whether the project uses the old Input Manager or the new Input System package.
• The auto-boot hook runs in every scene of the project. For a dedicated CIA project that is what you want. To opt out, delete the Boot() method and add SimulatorController to an empty GameObject manually.
• For submission, build WebGL (File → Build Profiles) and host it on itch.io or GitHub Pages so the evaluator can run it in a browser without installing Unity.

Key Components

File	Role
DijkstraEngine.cs	Pure C# with no UnityEngine dependency. Contains GraphModel, Edge, Snapshot and DijkstraEngine.Run(), which returns one Snapshot per step. Unit-testable outside Unity
GraphView.cs	Presentation only. Builds chalk nodes, jittering edge LineRenderers and the chalkboard quad, and recolours them from a Snapshot. Knows nothing about the algorithm
ChalkSkin.cs	The flat cartoon UI skin: procedurally generated rounded-rect textures (flat fill, ink outline, hard shadow) in 3 wobbly versions that are cycled ~8x/second
Resources/Shaders/*	The chalk toon look (see below)
SimulatorController.cs	Playback state (index, speed, play/pause), input handling, camera fitting, and the IMGUI panel and labels

Data flow: GraphModel → DijkstraEngine.Run() → List<Snapshot> → SimulatorController picks the current snapshot → GraphView.Apply() recolours the graph and DrawPanel() renders the text panels.

Algorithm mapping (for the viva):

Pseudocode line	Code
Initialise dist, parent, Q	Setup at the top of Run()
u ← EXTRACT-MIN(Q)	Linear scan for the smallest dist in q
for each neighbour v of u	foreach (int id in g.Incident(u))
Relaxation dist[u] + w < dist[v]	long cand = dist[u] + e.W; bool better = cand < dist[v];
Update dist, parent	Inside if (better)

Handheld Shell (PSP-style)

The whole simulator lives on the screen of a cartoon handheld. No logos, just a generic handheld drawn procedurally in the same flat style.

How it is built

• The graph camera renders into a RenderTexture (1440x1040) shown on the handheld's screen with GUI.DrawTexture.
• The entire device (body, bezel, screen, buttons) is drawn with IMGUI under one GUI.matrix. Shaking that matrix shakes everything together, and IMGUI hit-testing follows the matrix, so the buttons stay clickable while the device vibrates.
• A second empty camera (ScreenCamera) keeps the Game view from reporting "no cameras rendering", because the graph camera targets a texture.

Buttons (mouse or keyboard)

Handheld	Key	Action
D-pad left / right	← / →	Step back / forward
D-pad up / down	↑ / ↓	Speed up / down
Cross	Space	Play / pause
Circle	R or Home	Reset to the start
Triangle	End	Jump to the last step
Square	W	Random edge weights
Start	Enter	Default weights
Select	Tab	Next source vertex
L / R shoulder	Q / E	Switch panel page (Run / State)
Analog nub	click	Cap leans toward the mouse; click it to shake the device
Anywhere on the body	click	Poke (shake)
Vertex on the screen	left-click / right-click	New source / trace shortest path (after the last step)

Two feedback layers, both driven by simulation events

Layer	Trigger	What you see
Screen jitter	Every move of the simulation (any step, forwards or back, reset, new source)	The graph image tears into horizontal slices shifted sideways, with pink and cyan colour-split ghosts, and the panel and labels shudder. It settles in about 0.3 s
Device shake (trauma)	Button presses, extract-min, successful relaxation, finishing the run	Whole device jumps and tilts up to about 2.4 degrees. Strength is trauma squared, decaying at 1.7 per second, so small events are small and the finish is big
Rumble	Successful relaxation, finishing, nub click	Frame-by-frame buzz while the power LED turns orange

Shake noise is quantised to 30 fps (24 fps for the screen) so it reads as hand-animated jitter rather than smooth camera shake.

Tuning

• Shake strength: the 30f (pixels) and 2.4f (degrees) in DeviceMatrix().
• Shake decay: 1.7f in Update().
• Screen tear: 32f (slice offset), 14f (ghost offset), 3.2f (jitter decay) in DrawGraphImage() / Update().
• Kick sizes per event: React() and Do().
• Graph image upside-down on your platform: set FlipRt = true.

Performance: the graph is rendered once per frame into the texture (4x MSAA, about 6 MB). The jitter draws the same texture about 12 times in 2D for roughly 0.3 s after a move, which is trivial. Everything else is IMGUI and a few GUI.DrawTexture calls.

Cartoon UI (ChalkSkin)

No gradients: Unity's default IMGUI skin is replaced entirely. Every box is a flat rounded rect with a thick ink outline and a hard offset shadow. Colour is applied through GUI.backgroundColor, so one white texture set serves every colour.

• Boil: each shape exists in 3 slightly different wobbly versions. The UI picks (tick + id) % 3, so neighbouring elements are out of phase.
• Meaning, not decoration: the "What just happened" card changes colour per step type (yellow = extract-min, orange = relaxation succeeded, blue = no change, grey = skipped, green = done). Vertex-table chips use the same colours as the nodes on the board.
• Jitter extras: outlined title, wavy underline, striped panel background and scalloped left edge all re-roll every tick.
• Fonts: hand fonts lack maths glyphs, so with a custom font the UI swaps ∞ → ← ≥ for ASCII (inf, ->, <-, >=) in SimulatorController.T().
• Tweak: BoilFps in SimulatorController, palette constants at the top of ChalkSkin, texture parameters (radius, outline, shadow, wobble) in the ChalkSkin constructor.

Chalk Look (shaders)

Shader	Used by	What it does
DAA/ChalkNode	Node sprites	Draws the whole disc procedurally: wobbling circle outline, 3-band cel shading, diagonal chalk hatching in the shadow band, highlight dab, grainy fill, broken double outline and dust specks
DAA/ChalkLine	Edge LineRenderers	Two overlapping hand-drawn strokes per edge with wandering centres and thickness, grain dropout and dust
DAA/Chalkboard	Background quad	Completely flat board: two greens in diagonal bands whose edges boil each tick, plus flat chalk dots

Where the jitter comes from: time is quantised (floor(_Time.y * _JitterFps)), so shapes re-roll about 8 times a second like a hand-redrawn animation. The grain is world-space and static, so it stays put like the board texture. Edge geometry is also re-wobbled on the CPU in GraphView.RebuildLine() at the same rate.

Tuning cheat sheet

Want	Change
Calmer / jumpier jitter	GraphView.JitterFps (edges) and _JitterFps in the node, line materials
Edges wander more	GraphView.EdgeJitter (default 0.045)
Wobblier circles	_WobbleAmp on ChalkNode
Chunkier chalk	Lower _GrainScale (bigger grain), raise _GrainStrength
Less hatching	Lower _HatchScale, or set the shadow hatch factor 0.22 in ChalkNode.shader to 0
Thicker edges	wk and the width values in GraphView.Apply()

Colour and a per-node noise seed reach the node shader through SpriteRenderer.color (rgb = fill, alpha = seed), which is why Apply() overwrites the alpha channel.

Optimization Notes

• Complexity in this simulator: EXTRACT-MIN is a linear scan, so total time is O(V²) and space is O(V + E) for the graph plus O(V) per snapshot. That is deliberate: it keeps the queue easy to read. The blog's binary-heap version is O((V + E) log V). The snapshot list costs O(V) memory per step, roughly O(V + E) steps, which is trivial for a teaching graph.
• Draw calls: about 13 for the graph (5 nodes, 7 edges, 1 background) plus IMGUI. Nodes and edges each share one material but do not batch, which is irrelevant at this size and far below any concern on an RTX 2050 baseline.
• Shader cost: the fragment shaders use a few 3-octave noise calls per pixel. Node quads are about 1.8 world units wide (bigger than the disc, to leave room for wobble and dust), so overdraw is a few hundred thousand transparent pixels in total. Trivial here. If you scale to hundreds of nodes, render them in one instanced mesh instead of one SpriteRenderer each.
• GC: IMGUI allocates every event (string concatenation, GUILayout params). Fine for a 5-node teaching tool. If this becomes a real game UI, move the panel to UI Toolkit or uGUI and cache strings.
• Layout stability: the panel always draws the same controls between Layout and Repaint events (only text and colours change). Adding conditional controls to DrawPanel will trigger IMGUI "control count" errors.
• Scope-creep flags: node dragging, a graph editor, a heap visualisation and directed or negative-weight modes are all out of scope for this CIA. Negative weights in particular would need a Bellman-Ford mode to be meaningful.
• Extension path: because the engine is decoupled and emits snapshots, Bellman-Ford or Prim's can be added by writing another Run() that produces the same Snapshot shape. GraphView and the panel would not change.