Algorithms¶
Classic game algorithms, each in one Lua file you can read top to bottom: a maze generator, terrain from noise, A* pathfinding and flocking. They build with physics boxes and balls so you can walk into the result.
Maze generation¶
The recursive backtracker (a depth-first search): start in a corner, step to a random neighbour you haven't visited, knocking down the wall between, and when every neighbour is visited, back up until one isn't. The result has exactly one path between any two cells. M makes a new one; the entrance faces where the player starts.
maze.lua
-- maze.lua: a new maze every time you press M. The recursive backtracker:
-- walk from cell to random unvisited cell, knocking down the wall between,
-- and back up when stuck. Every cell ends up reachable, by exactly one
-- path. (docs/cookbook/algorithms.md)
local W, H = 8, 8 -- cells across and deep
local CELL = 1.8 -- metres
local ORIGIN = Vec(-18, 0, 5) -- the maze's corner in the level
local WALL_H, THICK = 1.4, 0.2
local walls = {} -- body ids, to clear the old maze
local seed = 7
local function generate()
math.randomseed(seed)
-- open[x][z] = { east = bool, south = bool }: the walls knocked down.
local open, visited = {}, {}
for x = 1, W do
open[x], visited[x] = {}, {}
for z = 1, H do open[x][z] = { east = false, south = false } end
end
local stack = { { 1, 1 } }
visited[1][1] = true
while #stack > 0 do
local x, z = stack[#stack][1], stack[#stack][2]
-- The neighbours not visited yet.
local choices = {}
if x > 1 and not visited[x - 1][z] then table.insert(choices, { x - 1, z }) end
if x < W and not visited[x + 1][z] then table.insert(choices, { x + 1, z }) end
if z > 1 and not visited[x][z - 1] then table.insert(choices, { x, z - 1 }) end
if z < H and not visited[x][z + 1] then table.insert(choices, { x, z + 1 }) end
if #choices == 0 then
table.remove(stack) -- dead end: back up
else
local n = choices[math.random(#choices)]
local nx, nz = n[1], n[2]
-- Knock down the wall between (x, z) and (nx, nz).
if nx > x then open[x][z].east = true
elseif nx < x then open[nx][z].east = true
elseif nz > z then open[x][z].south = true
else open[x][nz].south = true end
visited[nx][nz] = true
table.insert(stack, { nx, nz })
end
end
return open
end
local function wall(cx, cz, sx, sz)
table.insert(walls, physics.box { pos = ORIGIN + Vec(cx, WALL_H / 2, cz), size = Vec(sx, WALL_H, sz),
color = Vec(0.45, 0.5, 0.65), static = true })
end
local function build()
for _, id in ipairs(walls) do physics.remove(id) end
walls = {}
local open = generate()
-- The outer walls, with a way in at the east side of the first row.
wall(W * CELL / 2, 0, W * CELL, THICK) -- north
wall(W * CELL / 2, H * CELL, W * CELL, THICK) -- south
wall(0, H * CELL / 2, THICK, H * CELL) -- west
wall(W * CELL, (H * CELL + CELL) / 2, THICK, (H - 1) * CELL) -- east, minus the entrance
-- Inside: each cell's east and south wall, unless knocked down.
for x = 1, W do
for z = 1, H do
if x < W and not open[x][z].east then wall(x * CELL, (z - 0.5) * CELL, THICK, CELL + THICK) end
if z < H and not open[x][z].south then wall((x - 0.5) * CELL, z * CELL, CELL + THICK, THICK) end
end
end
print(string.format("Maze %d: %d walls", seed, #walls))
end
build()
input.define("maze.new", "New maze", "M")
hook.Add("Think", "maze.keys", function()
if input.pressed("maze.new") then seed = seed + 1; build() end
end)
- The "recursion" is a list used as a stack:
table.insertpushes,table.removepops. It never runs out of stack however big the maze. math.randomseed(seed)makes the same seed give the same maze: handy for levels you want to share as a number.- Each cell only draws its east and south wall; the outer walls close the rest. That avoids placing every inside wall twice.
Terrain from noise¶
Value noise gives smooth random numbers across the ground: a random height at each whole-number point, eased between them. Adding a few layers of it, each twice as detailed and half as strong (fractal noise, or fBm), looks like hills. Height picks the colour: water, grass, rock, snow. N makes a new landscape.
terrain.lua
-- terrain.lua: hills from noise. Value noise gives smooth random numbers
-- over the ground; adding a few layers of it at different sizes (fractal
-- noise) looks like terrain. Each column's height and colour come from
-- it. N makes a new landscape. (docs/cookbook/algorithms.md)
local N = 20 -- columns across and deep
local STEP = 0.8 -- metres per column
local ORIGIN = Vec(2, 0, 4)
local columns = {}
local seed = 1
-- A fixed random number for each whole-number grid point (a hash).
local function lattice(ix, iz)
local h = (ix * 374761393 + iz * 668265263 + seed * 1442695041) % 2147483647
h = (h * h * 15731 + 789221) % 2147483647
return (h % 10000) / 10000 -- 0 .. 1
end
local function smooth(t) return t * t * (3 - 2 * t) end -- eases in and out
-- Value noise: blend the four grid points around (x, z).
local function noise(x, z)
local ix, iz = math.floor(x), math.floor(z)
local fx, fz = smooth(x - ix), smooth(z - iz)
local a, b = lattice(ix, iz), lattice(ix + 1, iz)
local c, d = lattice(ix, iz + 1), lattice(ix + 1, iz + 1)
local top = a + (b - a) * fx
local bottom = c + (d - c) * fx
return top + (bottom - top) * fz
end
-- Fractal noise: big gentle hills plus smaller and smaller bumps.
local function fbm(x, z)
local sum, amp, freq, total = 0, 1, 1, 0
for _ = 1, 4 do
sum = sum + noise(x * freq, z * freq) * amp
total = total + amp
amp, freq = amp * 0.5, freq * 2
end
return sum / total -- 0 .. 1
end
local function build()
for _, id in ipairs(columns) do physics.remove(id) end
columns = {}
for x = 0, N - 1 do
for z = 0, N - 1 do
local h = fbm(x * 0.15, z * 0.15)
local height = 0.2 + h * h * 4 -- squared: flatter valleys, sharper peaks
local color
if h < 0.35 then color = Vec(0.2, 0.45, 0.8) -- water
elseif h < 0.55 then color = Vec(0.35, 0.65, 0.3) -- grass
elseif h < 0.7 then color = Vec(0.5, 0.45, 0.35) -- rock
else color = Vec(0.95, 0.95, 0.97) end -- snow
table.insert(columns, physics.box { pos = ORIGIN + Vec(x * STEP, height / 2, z * STEP),
size = Vec(STEP, height, STEP), color = color, static = true })
end
end
end
build()
input.define("terrain.new", "New terrain", "N")
hook.Add("Think", "terrain.keys", function()
if input.pressed("terrain.new") then seed = seed + 1; build() end
end)
latticeis a hash: the same grid point always gives the same number, so the terrain doesn't depend on the order it's built in.smooth(smoothstep) is what hides the grid: without it, the slopes have visible creases at every grid line.- Squaring the height before using it flattens the valleys and sharpens
the peaks. Try
h ^ 3, or1 - math.abs(2 * h - 1)for ridges.
A* pathfinding¶
A* finds the shortest way around walls. It explores cells cheapest-first, where a cell's cost is the steps taken to reach it plus a guess at the steps left. As long as the guess never overestimates (here: the Manhattan distance, which ignores walls), the first path it finds to the goal is a shortest one. The red ball re-plans twice a second as you move, and the yellow dots show its plan.
astar.lua
-- astar.lua: a chaser that finds its way to you around walls with A*
-- (A-star), the path-finding most games use. The map is text; the path
-- it plans is shown as dots and re-planned twice a second as you move.
-- (docs/cookbook/algorithms.md)
local MAP = {
"##############",
"#............#",
"#..######....#",
"#.......#....#",
"#.......#..###",
"#..###..#....#",
"#....#.......#",
"#..####......#",
"#............#",
"#..#......#..#",
"#..#......#..#",
"#............#",
"##############",
}
local ORIGIN = Vec(-7, 0, -1) -- world position of the map's top-left cell
local SPEED = 3.5
local W, H = #MAP[1], #MAP
local function wallAt(x, z) return MAP[z]:sub(x, x) == "#" end
local function cellOf(p) return math.floor(p.x - ORIGIN.x) + 1, math.floor(p.z - ORIGIN.z) + 1 end
local function centre(x, z) return ORIGIN + Vec(x - 0.5, 0, z - 0.5) end
for z = 1, H do
for x = 1, W do
if wallAt(x, z) then
physics.box { pos = centre(x, z) + Vec(0, 0.5, 0), size = Vec(1, 1, 1), color = Vec(0.5, 0.52, 0.6), static = true }
end
end
end
-- A*: explore cells cheapest-first, where cost = steps so far (g) plus a
-- guess of the steps left (h, the Manhattan distance, never too high).
local function findPath(sx, sz, gx, gz)
local function key(x, z) return z * 1000 + x end
local open = { { x = sx, z = sz, g = 0, f = math.abs(gx - sx) + math.abs(gz - sz) } }
local came, best = {}, { [key(sx, sz)] = 0 }
while #open > 0 do
-- Take the open cell with the lowest f (a heap is faster for big maps).
local bi = 1
for i = 2, #open do if open[i].f < open[bi].f then bi = i end end
local cur = table.remove(open, bi)
if cur.x == gx and cur.z == gz then
local path, k = {}, key(gx, gz) -- walk back from the goal
while k do
table.insert(path, 1, { x = k % 1000, z = k // 1000 })
k = came[k]
end
return path
end
for _, d in ipairs({ { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }) do
local nx, nz = cur.x + d[1], cur.z + d[2]
if nx >= 1 and nx <= W and nz >= 1 and nz <= H and not wallAt(nx, nz) then
local g = cur.g + 1
local k = key(nx, nz)
if best[k] == nil or g < best[k] then
best[k], came[k] = g, key(cur.x, cur.z)
table.insert(open, { x = nx, z = nz, g = g, f = g + math.abs(gx - nx) + math.abs(gz - nz) })
end
end
end
end
return nil -- no way through
end
local chaser = physics.sphere { pos = centre(2, 2) + Vec(0, 0.4, 0), radius = 0.3, density = 300, color = Vec(0.95, 0.3, 0.3) }
local path, dots = nil, {}
local function showPath()
for _, id in ipairs(dots) do physics.remove(id) end
dots = {}
for _, c in ipairs(path or {}) do
table.insert(dots, physics.sphere { pos = centre(c.x, c.z) + Vec(0, 0.05, 0), radius = 0.06,
color = Vec(1, 0.8, 0.3), static = true })
end
end
local function plan()
local cx, cz = cellOf(physics.position(chaser))
local px, pz = cellOf(player.position())
if px < 1 or px > W or pz < 1 or pz > H or wallAt(px, pz) then path = nil
else path = findPath(cx, cz, px, pz) end
showPath()
end
timer.Create("astar.plan", 0.5, 0, plan) -- the first plan in half a second
hook.Add("Think", "astar.chase", function()
local v = physics.velocity(chaser)
if not path or #path < 2 then
physics.setVelocity(chaser, Vec(0, v.y, 0))
return
end
-- Head for the next cell on the path; drop cells as they're reached.
local at = physics.position(chaser)
local goal = centre(path[2].x, path[2].z)
local to = Vec(goal.x - at.x, 0, goal.z - at.z)
if to:length() < 0.2 then table.remove(path, 1) return end
local step = to:normalized() * SPEED
physics.setVelocity(chaser, Vec(step.x, v.y, step.z))
end)
- The map is text, so you can draw a level in the file.
#is a wall. - Picking the lowest
fby looking through every open cell is fine for a few hundred cells; for big maps use a binary heap. - To allow diagonal steps, add the four diagonal directions with a cost of 1.414 and use the octile distance as the guess.
- Following the path is the patrol recipe with the path as its waypoints.
Flocking¶
Craig Reynolds' boids (1986): each ball looks only at its neighbours and follows three rules. Separation: don't crowd them. Alignment: head the way they're heading. Cohesion: move toward their middle. Together they flock like birds or fish. These also keep inside a pen and drift after you.
flocking.lua
-- flocking.lua: boids. Thirty balls that flock like birds or fish from
-- three simple rules, each looking only at its neighbours: don't crowd
-- (separation), go the way they go (alignment), stay with them
-- (cohesion). They also keep inside a pen and drift after you.
-- (docs/cookbook/algorithms.md)
local COUNT = 30
local SEE = 2.5 -- how far a boid sees its neighbours, metres
local SPEED = 3
local PEN_MIN, PEN_MAX = Vec(-12, 0, -12), Vec(12, 0, 12)
local boids = {}
for i = 1, COUNT do
local a = i / COUNT * math.pi * 2
table.insert(boids, physics.sphere { pos = Vec(math.cos(a) * 4, 0.3, math.sin(a) * 4), radius = 0.2, density = 100,
friction = 0, color = Vec(0.3 + 0.7 * i / COUNT, 0.6, 1 - 0.6 * i / COUNT) })
end
hook.Add("Think", "flocking.update", function(dt)
-- Read everyone first, then move: every boid reacts to the same moment.
local pos, vel = {}, {}
for i, id in ipairs(boids) do
local p, v = physics.position(id), physics.velocity(id)
pos[i], vel[i] = Vec(p.x, 0, p.z), Vec(v.x, 0, v.z)
end
local me = player.position()
for i, id in ipairs(boids) do
local apart, heading, middle, n = Vec(0, 0, 0), Vec(0, 0, 0), Vec(0, 0, 0), 0
for j = 1, COUNT do
if j ~= i then
local offset = pos[i] - pos[j]
local d = offset:length()
if d < SEE and d > 0.001 then
apart = apart + offset / (d * d) -- closer pushes harder
heading = heading + vel[j]
middle = middle + pos[j]
n = n + 1
end
end
end
local steer = Vec(0, 0, 0)
if n > 0 then
steer = steer + apart * 1.5 -- separation
steer = steer + (heading / n - vel[i]) * 0.5 -- alignment
steer = steer + (middle / n - pos[i]) * 0.4 -- cohesion
end
steer = steer + (Vec(me.x, 0, me.z) - pos[i]):normalized() * 0.3 -- drift toward you
-- The pen: turn back near its edges.
if pos[i].x < PEN_MIN.x then steer = steer + Vec(3, 0, 0) end
if pos[i].x > PEN_MAX.x then steer = steer - Vec(3, 0, 0) end
if pos[i].z < PEN_MIN.z then steer = steer + Vec(0, 0, 3) end
if pos[i].z > PEN_MAX.z then steer = steer - Vec(0, 0, 3) end
local v = vel[i] + steer * (dt * 4)
if v:length() > SPEED then v = v:normalized() * SPEED end
physics.setVelocity(id, Vec(v.x, physics.velocity(id).y, v.z))
end
end)
- The weights (1.5, 0.5, 0.4) set the character: more separation is a loose swarm, more cohesion a tight school, more alignment a stream.
- Every boid reads every other one, so 30 boids is 870 checks a frame. For hundreds, put them in a grid of cells and only check the neighbouring cells.
Next: animation and IK.