Skip to content

A Lua toolkit for computational geometry on a grid

License

Notifications You must be signed in to change notification settings

nhartland/forma

Repository files navigation

Build Status Coverage Status License

forma

2D grid shape generation in Lua

forma is a utility library for the procedural generation and manipulation of shapes on a two dimensional grid or lattice. It came about as part of experiments in making roguelike games. forma is therefore particularly suited (but not limited) to the generation of roguelike environments.

Features

  • A spatial-hashing pattern class for fast lookup of active cells.
  • Pattern manipulators such as the addition, subtraction, rotation and reflection of patterns.
  • Rasterisation algorithms for 2D primitives, e.g lines, circles, squares and Bezier curves.
  • A very flexible cellular automata implementation with
    • Synchronous and asynchronous updates
    • Combination of multiple rule sets
  • Pattern sampling algorithms including
    • Random (white noise) sampling
    • Perlin noise sampling
    • Poisson-disc sampling
    • Mitchell's best-candidate sampling
  • Algorithms for subpattern finding including
    • Flood-fill contiguous segment finding
    • Convex hull finding
    • Pattern edge and surface finding
    • Binary space partitioning
    • Voronoi tessellation / Lloyd's algorithm

Results can be nested to produce complex patterns, and all of these methods are able to use custom distance measures and definitions of the cellular neighbourhood (e.g Moore, von Neumann).

Examples

-- Generate a square box to run the CA inside
local domain = primitives.square(80,20)

-- CA initial condition: 800-point random sample of the domain
local ca = subpattern.random(domain, 800)

-- Moore (8-cell) neighbourhood 4-5 rule
local moore = automata.rule(neighbourhood.moore(), "B5678/S45678")

-- Run the CA until converged or 1000 iterations
local ite, converged = 0, false
while converged == false and ite < 1000 do
    ca, converged = automata.iterate(ca, domain, {moore})
    ite = ite+1
end

-- Access a subpattern's cell coordinates for external use
for icell in ca:cells() do
    -- local foo = bar(icell)
    -- or
    -- local foo = bar(icell.x, icell.y)
end

-- Find all 4-contiguous segments of the CA pattern
-- Uses the von-neumann neighbourhood to determine 'connectedness'
-- but any custom neighbourhood can be used.
local segments = subpattern.segments(ca, neighbourhood.von_neumann())

-- Print a representation to io.output
subpattern.print_patterns(domain, segments)

Installation

forma is compatible with Lua 5.1, 5.2, 5.3 and LuaJIT 2.0, 2.1. The library is written in pure Lua, no compilation is required. Including the project is as simple as including the forma directory in your project or Lua path.

The easiest way to do this is via LuaRocks. To install the latest stable version use:

    luarocks install forma

Alternatively you can try the dev branch with:

    luarocks install --server=http://luarocks.org/dev forma

Documentation

Documentation is hosted here.

Generating the documentation requires

Simply running

ldoc --output contents --dir docs .

in the root directory should generate all the required pages.

Testing

Unit tests and coverage reports are provided. The test suite requires

To run the tests use

./run_tests.sh