Red Blob Games - Math and Algorithms

Guides

Hi! I make interactive visual explanations of math and algorithms, using motivating examples from computer games.

Learn	Introduction to A* and implementation guide
Also:	Dijkstra’s Algorithm, Breadth First Search
	Tower Defense pathfinding
Also:	Breadth First Search, Dijkstra Maps, Flow Field pathfinding
	Hexagonal grid reference and implementation guide
Also:	non-orthogonal bases, relation to cubes
	2D Visibility algorithm
Also:	sweep algorithms
	Intro to graph theory
Also:	how to represent grids as graphs
	Probability for RPG Damage
Also:	probability distributions, nonparametric distributions
	Line drawing
Also:	linear interpolation (lerp), supercover
	Curved roads
Also:	Bezier curves, circular arcs, biarcs
	Map generation from noise and noise function concepts
Also:	Simplex/Perlin Noise, signal processing
	Polygonal Map Generation and implementation guide
	[1]	Also: blue noise, Delaunay triangulation, Voronoi diagrams, water flow
	Pathfinding with A*
	[2]	Grid parts: tiles, edges, vertices for squares, hexagons, and triangles
	Grid edges	and tiles for square grids
	Pathfinding with circular obstacles
	[3]	Also: bitangents
	Guide to Delaunator
	[4]	, a Delaunay+Voronoi library
	Also:	mesh data structures, half-edges
	Noisy edges	out of straight lines
	Also:	area-constrained noisy paths
	Filled circles	on a grid
	All pairs shortest paths	for map analysis [5]

Play

I make fun demos while learning new things and writing explanations:

Mapgen4	map generator lets you draw your own terrain
	Procedural face generator (inspired by a Scott McCloud book)
Mapgen2	map generator
	Ellipse from lines (inspired by a 3blue1brown video)
	Modulo multiplication (inspired by a Mathologer video)
	Orbits of planets (inspired by a John Carlos Baez blog post)
	Noisy edges	using shaders
	Car blind spots [8]
	Bacterial cell	animation
	Conveyor belt editor (inspired by Factorio)
	Tiling a sphere with diagonal squares
	Tiling a sphere with hexagons
	Tiling a sphere with Voronoi
	Tiling a cube with squares
	Tiling a sphere with squares
	Organic cave maps
	Rounded cells	and Chaikin Curves
	Dyson hatching (inspired by a Watabou project)
	Triangle patterns	on a Delaunay mesh
	Shape transitions (inspired by a Dave Bees Bombs project)
	Reaction-diffusion

Ponder

I also explore ideas sometimes without writing a full guide:

	Alternative to Voronoi with rounder cells
	Procedurally generating names using pronunciations and neural networks
	Procedurally modifying spelling using pronunciations and letter-phoneme alignment
	Understanding the color yellow: why are there three primary colors in science but four primary colors in board games, crayons, etc.?
	Distance to seed points using Breadth First Search
	Homunculus: stretching and shrinking maps to match a game’s needs [9]
	Map generation with no code, only image filters
	Terrain shader experiments for filling triangles with various patterns
	Placing natural resources on a map
	Hexagon on Saturn [10]: can I recreate it?
	Procedural planet generation on a sphere using Voronoi+Delaunay
	Reshaping distributions [11]
	Signed distance fields [12]: quick visual explanation
	Railroads on a hex grid
	Game map design [13]: what should you show and not show?
	/r/roguelikedev summer event, 2020, 2021, 2022, 2023, where people in the reddit/discord communities make our own roguelikes over several weeks.

Meta

I’m working on a series of pages that explain how to make interactive guides:

	Tutorial about making interactive tutorials, including multiple diagrams and drag-and-drop. This shows how I write my interactive tutorials since 2015, using vue.js
	Event handlers for dragging objects around, my recommendations for mouse/touch event handling for modern browsers as of 2023.
	An older Tutorial about making interactive tutorials. This shows how I wrote my interactive tutorials from 2011–2015, using d3.js.
	Starter code you can study and copy, with versions using React, Vue, lit-html, vanille js, and Preact
	How I implement my interactive diagrams, part 1 [14]
	and part 2 [15]. This is a high level overview without being specific to any particular library.
	Little design elements I like to use — colors, shapes, controls, etc.
	Drag handles with constraints
	Arrows outside the diagrams [16], something I haven’t seen elsewhere, and haven’t used yet
	Responsive web design implementation for interactive diagrams (canvas, svg, webgl)
	Notes on how I made the A* pages and the tool I made for graph editing
	Blog posts [17] about my process and struggles
	Scrubbable numbers in ObservableHQ [18]
	Using Vue’s reactivity system with Canvas [19], which can also work with D3.
	Using Vue with KaTeX, proof of concept.
	Using Vue with pointerevents, quick example.
	Vue text modification using render functions for syntax highlighting, proof of concept.
	How to make diagram and text elements highlight together [20], with 10 lines of JavaScript. It’s a simple example that might help you get started.

Accompanying code is open source, under either the MIT License [21] or the Apache v2 License [22]. Both allow use in commercial projects. Other projects are found at at github/amitp [23] and github/redblobgames [24]. My project ideas board [25] is public.

About Me

I’ve been helping people make games since 1990. I wrote games earlier in life, with Solar Realms Elite [26] being the most well known [27], then worked on an environmental simulation game called BlobCity, then took a break for over a decade. The recent rise of indie, mobile, tablet, social, and web games have made me interested in game development again. My current passion is using interactivity on the web for learning, especially computer science and math. I’ve started with game development because it’s a rich source of interesting problems that can be explained visually. With modern web browsers, we can use explanations that don’t follow the formats used in magazines, technical papers, and books. We can combine learning by reading, learning by watching, and learning by doing [28].

I previously worked with Root-1 [29] on educational games, Wild Shadow Studios [30] on Realm of the Mad God, Peter Norvig on interactive diagrams for Artifical Intelligence: A Modern Approach [31], and Nonagon Games on A Chronicle of Misdeeds [32]. I’m currently working with Jetbolt Games [33] on Galactic Assault Squad [34].

If you’re in the Silicon Valley area and want to chat in person, email me at redblobgames@gmail.com. I’m especially interested in algorithms related to maps, procedural generation, and pathfinding, but love to chat about anything.

Welcome to Red Blob Games!

Guides

Play

Ponder

Meta

About Me