SpecializedSource checked

Space Colonization Algorithm

Generates branching structures by growing toward nearby attraction points.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Procedural Generation
Difficulty: Advanced
Family: Growth Simulation
Tier: Specialized
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready

Overview

The Space Colonization Algorithm creates tree- or vein-like forms by repeatedly extending branches in the averaged direction of nearby attractors.

Core Concepts

attraction pointgrowth directionbranch tipkill radius

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(points * branches)

Average

O(iterations * points * branches)

Worst

O(iterations * points * branches)

Space

O(points + branches)

When to Use

Use when organic branching should respond to a target volume or point cloud.
Use when tree generation is a central requirement.

When Not to Use

Avoid when a grammar-like branching pattern with strict symbolic rules is required.
Avoid when the generator cannot enforce the playability, connectivity, or style constraints required.

What It Does

Places attraction points
Finds attractors near branch tips
Extends branches toward averaged directions

Use Cases

Tree generation
Leaf vein patterns
Organic branching structures

Inputs

Attraction points
Kill radius
Influence radius
Step length

Outputs

Branch graph

Key Formulas (1)

Growth direction

direction = normalize(∑(normalize(attractor − branch_tip)))

direction = normalize(sum(normalize(attractor - branch_tip)))

Averages directions from a branch tip toward its nearby attraction points.

Pseudocode

1.Scatter attraction points in a growth volume
2.For each attractor, find nearby branch tips
3.Average directions from tips to attractors
4.Grow new branch segments
5.Remove attractors reached by branches

Canonical Example

Input: attractors form a leaf shape
Output: branches fill the leaf with veins
Explanation: Branch tips grow toward nearby attraction points until they are consumed.

Implementation Notes

Visualize attraction points, influence radius, and kill radius while tuning.
Expose seed, scale, and constraint parameters so outputs can be reproduced.
Keep a tiny example with expected output beside the implementation.

Common Pitfalls

Poor radius settings can stop growth early or create tangled branches.
Random-looking output can still contain repeated patterns, dead ends, or invalid regions.
Not defining boundary, empty, or degenerate inputs before implementation.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show branch tips advancing toward a cloud of attraction points.

Step 1 of 5: Scatter attraction points in a growth volume

generated-grid

Notes

Spatial indexing is important for large attraction point sets.

Sources (1)

What each reference supports for this entry.