Batman and the algorithms
summary
Shows Monte Carlo integration for the Batman logo using 2,000,000 samples with the Mersenne Twister PRNG and reports ~0.01% error, and demonstrates the tradeoff: dropping to 20,000 samples cuts runtime from ~4,000 ms to ~30 ms while increasing error. Implements real‑time pathfinding for a minigame, compares Dijkstra and A, finds a bad heuristic makes A slower, then fixes heuristics (Manhattan=10, diagonal=14, squared Euclidean to avoid sqrt) adds a tie‑breaker and considers navmesh alternatives.
AI-written summary · about
chapters (36)
- 0:00Introduction and speaker intro
- 1:10About the speaker and motivation
- 2:15Real-life pool tiling problem
- 3:42Monte Carlo integration explained
- 6:33Random number generators and bias
- 8:19Measuring algorithm performance
- 9:02Integrating the Batman symbol
- 10:50Balancing samples and speed
- 11:11Pathfinding in a Batman minigame
- 12:36Dijkstra's algorithm basics
- 15:29Google Maps and Dijkstra's limits
- 16:57A* algorithm introduction
- 17:43Manager's demand vs research
- 18:05A* in action on a grid
- 19:30Handling blocked paths
- 20:16Benchmarking A* vs Dijkstra
- 20:58Heuristic function in A*
- 22:48A* algorithm step-by-step
- 25:18Optimal vs shortest path
- 25:40Choosing the right heuristic
- 26:41Manhattan distance explained
- 27:24Diagonal distance heuristic
- 28:07Euclidean distance and square roots
- 29:55Tie breaker in heuristics
- 31:22Fast square root approximation
- 33:09Obstacles and algorithm efficiency
- 33:52Alternative map representations
- 34:15Why learn algorithms
- 34:57Q&A session begins
- 35:19Where to learn algorithms
- 36:23Choosing algorithms for scenarios
- 37:06Scaling heuristics and admissibility
- 37:46Games implemented by the speaker
- 38:27Learning path for graphics
- 39:31Building a 2D game engine
- 40:13Remembering algorithm principles
related talks
59mGame AI 4N00bz
01h 00mCritical Path Coding
59mPlaying Video Games One Frame at a Time
38mProcedural Generation at Runtime: From Basic to Complex by Example
53mLive-Coding Maze Generation Algorithms
59mWriting, Rewriting and Re-Rewriting Armello's AI System
01h 01mThe Forgotten AI of Video Games
32mAI and Minecraft