Voronoi in pico8

voronoi.lua

-- grabbed from http://www.lexaloffle.com/bbs/?pid=28105

function jitter(points)
  for i = 1, #points do
    p = points[i]
    p.x += rnd(2) - 1
    p.y += rnd(2) - 1
  end
end

function near(x, y, points)
  local p1
  local d1 = 0x7fff
  
  for i = 1, #points do
    local p0 = points[i]
    local dx, dy = (x - p0.x)/16, (y - p0.y)/16
    
    local d0 = dx*dx + dy*dy
    if d0 < d1 then
       p1, d1 = p0, d0
    end
  end
  
  return p1.c
end

function near2(x, y, points)
  local p1, p2
  local d1, d2 = 0x7fff, 0x7fff
  
  for i = 1, #points do
    local p0 = points[i]
    local dx, dy = (x - p0.x)/16, (y - p0.y)/16
    
    local d0 = dx*dx + dy*dy
    if d0 < d1 then
       p2, d2 = p1, d1
       p1, d1 = p0, d0
     elseif d0 < d2 then
      p2, d2 = p0, d0
    end
  end
  
  return 8*(sqrt(d2) - sqrt(d1)), p1.c
end

function brute(points, res)
  for y = 0, 128 do
    for x = 0, 128 do
      local c = near(x, y, points)
      pset(x, y, c)
    end
  end
  
  return "brute"
end

function vorocell(s, cx, cy, points, res)
  local x0, y0 = s*cx, s*cy
  
  if s <= res then
    local c = near(x0 + 0.5, y0 + 0.5, points)
    rectfill(x0, y0, x0 + s, y0 + s, c)
  else
    local s2 = s/2
    local rl, c = near2(x0 + s2, y0 + s2, points)
    
    if rl > s2*1.41 then
      rectfill(x0, y0, x0 + s, y0 + s, c)
    else
      local cx2 = cx*2
      local cy2 = cy*2
      
      vorocell(s2, cx2 + 0, cy2 + 0, points, res)
      vorocell(s2, cx2 + 1, cy2 + 0, points, res)
      vorocell(s2, cx2 + 0, cy2 + 1, points, res)
      vorocell(s2, cx2 + 1, cy2 + 1, points, res)
    end
  end
end

function subdivide(points, res)
  vorocell(128, 0, 0, points, shl(1, res - 1))
  
  return "subdivide"
end

function runlength(points, res, frame)
  for y = frame%res, 128, res do
    local x = 0
    while x < 128 do
      local rl, c = near2(x, y, points)
      
      -- Clamp the run length to 1.
      -- Rounding helps remove aliasing.
      rl = max(1, flr(rl + 0.5))
      
      line(x, y, x + rl, y, c)
      x += rl
    end
  end
  
  return "runlength"
end

function montecarlo(points, res)
  for i = 0, res*50 do
    local x, y = rnd(128), rnd(128)
    local rl, c = near2(x, y, points)
    circfill(x, y, rl, c)
  end
  
  return "montecarlo"
end

local points = {}
local res = 1
local frame = 0

local rendermethod = 1
local rendermethods = {
  brute,
  subdivide,
  runlength,
  montecarlo
}

function _init()
  for i = 0, 15 do
    add(points, {x = rnd(128), y = rnd(128), c = i})
  end
end

function _update()
  res -= (btnp(2) and 1 or 0)
  res += (btnp(3) and 1 or 0)
  res = max(res, 1)
  
  rendermethod += (btnp(1) and 1 or 0)
  rendermethod -= (btnp(0) and 1 or 0)
  rendermethod %= #rendermethods
end

function _draw()
  printh(rendermethod)
  local render = rendermethods[rendermethod + 1]
  local name = render(points, res, frame)
  
  rectfill(0, 0, #name*4, 5, 0)
  print(name, 0, 0, 7)
  
  local fps = "fps: "..(30/stat(1))
  rectfill(0, 6, #fps*4, 11, 0)
  print(fps, 0, 6, 7)
  
  frame += 1
  jitter(points)
end