Theseus and the Minotaur | Exploring State Space

A visual introduction to algorithms that explore the state space (BFS, Dijkstra, A*).

@polylog7346's A* video:    • The hidden beauty of the A* algorithm  
Advent of Code: https://adventofcode.com/2022/

------------------

Timetable:
0:00 - Introduction (BFS)
1:18 - Implementation
4:52 - Adding the Minotaur
8:03 - Robots!
10:18 - Pruning
10:54 - Prioritization (A*)
12:17 - Varying state distances (Dijkstra)
14:20 - Outro

------------------

Source code: https://github.com/xiaoxiae/videos/tr...

Music:
► Thannoid (Normal + Swinging) by Blue Dot Sessions: https://app.sessions.blue/browse/trac...
► Cases to Rest (Normal + Minimal) by Blue Dot Sessions: https://app.sessions.blue/browse/trac...
► Are We Loose Yet (All Piano) by Blue Dot Sessions: https://app.sessions.blue/browse/trac...
► Slider by Blue Dot Sessions: https://app.sessions.blue/browse/trac...

Software used:
► Manim (animation software): https://github.com/ManimCommunity/manim/
► Kdenlive (video cutting): https://kdenlive.org/en/
► ffmpeg (audio/video processing): https://ffmpeg.org/
► arecord (audio recording): https://linux.die.net/man/1/arecord
► sox (audio processing): http://sox.sourceforge.net/
► Inkscape (vector image editing): https://inkscape.org/
► Gimp (raster image editing): https://gimp.org/
► Midjourney (AI image generator): https://www.midjourney.com/home/
► Stable Diffusion (AI image generator): https://stablediffusionweb.com/

Social media:
► Website (for other things I'm up to): https://slama.dev/
► Patreon (if you'd like to support me):   / ytoms  

Inspired by Martin Mareš's Programming 1 Course exercises.

Thanks to the guys at Polylog for collaborating on this video:    / @polylog7346  

Also thanks to Matěj Kripner for valuable feedback.

------------------

[EN] Wikipedia: State space search
https://en.wikipedia.org/wiki/State_s...

[EN] Wikipedia: A* search algorithm
https://en.wikipedia.org/wiki/A*_sear...