Project 4: The Chaos Game (Fractals, Probability, and Geometry)

Build a deterministic chaos-game simulator that generates self-similar fractals and explains why random-looking steps converge to rigid geometric structure.

Quick Reference

Attribute Value
Difficulty Level 2 (Intermediate)
Time Estimate 8-14 hours
Main Language Python
Alternatives JavaScript, Julia, C++
Key Topics Iterated function systems, affine transforms, random processes, coordinate mapping
Deliverable CLI tool that generates fractal point clouds and image/ASCII previews
Observable Outcome Deterministic fractal output from fixed seed and parameters

Learning Objectives

By the end of this project, you should be able to:

  1. Explain why repeated random affine transformations can converge to a deterministic attractor.
  2. Implement a chaos-game iteration pipeline using fixed seeds for reproducibility.
  3. Convert mathematical coordinates into raster/image coordinates without distortion.
  4. Distinguish burn-in transients from steady-state sampling.
  5. Compare point-density behavior under different transformation probabilities.
  6. Diagnose incorrect fractal output by checking transforms, scaling, and RNG state.
  7. Validate your implementation with deterministic golden runs.
  8. Connect fractal generation to real-world procedural graphics and simulation workflows.

Theory Needed

1) Iterated Function Systems (IFS)

An IFS is a finite set of functions repeatedly applied to a point. In the chaos game, each iteration picks one function at random (using a probability distribution), transforms the current point, and uses that transformed point as the next state. Over many iterations, the point trajectory spends most of its time on a geometric attractor.

Key idea: randomness is in function selection, not in the target shape.

ASCII mental model:

Initial point p0
    |
    v
Choose transform T_i with probability w_i
    |
    v
p1 = T_i(p0)
    |
    v
Choose transform T_j
    |
    v
p2 = T_j(p1)
    |
    v
... repeated many times ...
    |
    v
Point cloud concentrates on attractor (fractal)

2) Affine Contractions and Why They Matter

Most chaos-game fractals use affine maps:

p' = A p + b

Where:

  • p is a 2D point vector
  • A is a 2x2 matrix (scale/rotate/shear)
  • b is a translation vector

For stable convergence, maps should be contractive (roughly: they shrink distances on average). If transformations are not contractive, points may diverge or fill broad regions without fractal structure.

Sierpinski triangle intuition:

  • Choose one of three triangle vertices.
  • Move halfway from current point to chosen vertex.
  • Repeat.

That “halfway” move is a contraction with scale 1/2.

3) Probabilities, Ergodic Intuition, and Density

Each transform has a selection probability. Equal probabilities often yield symmetric patterns. Unequal probabilities change density (where points appear more often), sometimes without changing the underlying support shape.

Important distinction:

  • Geometric support: where points can appear.
  • Density measure: how often they appear in each region.

This project trains you to reason about both.

4) Coordinate Systems and Rasterization

Mathematical coordinates (continuous) must map into pixel coordinates (discrete). You need:

  1. Bounding box estimation (min_x, max_x, min_y, max_y).
  2. Normalization to [0, 1].
  3. Scaling to output dimensions (width, height).
  4. Vertical-axis handling (many image buffers have origin at top-left).

ASCII mapping diagram:

Math space (origin center-ish)             Pixel space (origin top-left)

y ^                                         y
  |                                         v
  |      * point                            +---------------------> x
  +-----> x                                  (0,0)

map_x = floor((x - min_x)/(max_x - min_x) * (W-1))
map_y = floor((1 - (y - min_y)/(max_y - min_y)) * (H-1))

5) Determinism and Experimental Discipline

Randomized systems are testable when seeded. A fixed seed must produce identical outputs (or identical summary stats) for fixed inputs.

Use deterministic settings for:

  • reproducible debugging
  • regression tests
  • golden transcript verification

Pseudo-logic for deterministic run:

seed_rng(4242)
current_point <- (0.123, 0.456)
repeat burn_in + sample_count times:
  i <- weighted_random_choice(weights)
  current_point <- apply_transform(i, current_point)
  if iteration > burn_in:
    plot_or_count(current_point)

Project Spec

What You Will Build

A CLI application that:

  1. Loads a named transform set (sierpinski, optional others later).
  2. Runs chaos-game iterations with controlled seed and burn-in.
  3. Produces:
    • point statistics (bounding box, occupancy, density hotspots)
    • an ASCII preview for terminal verification
    • optional grayscale image output (e.g., PGM/PNG via a separate writer)

Out of scope for this project:

  • GPU rendering
  • animation/UI
  • anti-aliased production-quality renderer

Functional Requirements

  1. Accept CLI parameters: fractal type, points, burn-in, seed, output size.
  2. Validate transform definitions and probability normalization.
  3. Record points after burn-in only.
  4. Render deterministic ASCII preview from accumulated density.
  5. Emit summary metrics suitable for test assertions.

Non-Functional Requirements

  • Reproducibility: identical output for identical args and seed.
  • Performance: at least 100k iterations in a few seconds on a laptop.
  • Reliability: fail fast on invalid transforms or impossible bounds.

Data Shapes (Conceptual)

Transform:
  name: string
  A: [[a11, a12], [a21, a22]]
  b: [bx, by]
  weight: float

RunConfig:
  points: int
  burn_in: int
  seed: int
  width: int
  height: int
  mode: "ascii" | "image"

RunSummary:
  occupied_cells: int
  total_cells: int
  bbox: [min_x, max_x, min_y, max_y]
  top_hotspots: list[(x, y, hits)]

Real World Outcome

You should be able to run a fixed command and compare your terminal output line-by-line with this deterministic transcript.

Deterministic CLI transcript:

$ python chaos_game.py \
  --fractal sierpinski \
  --points 50000 \
  --burn-in 100 \
  --seed 4242 \
  --width 81 \
  --height 41 \
  --mode ascii

[INFO] seed=4242
[INFO] fractal=sierpinski maps=3
[INFO] total_iterations=50100 (burn_in=100, sampled=50000)
[INFO] bbox x=[0.0000, 0.9999] y=[0.0000, 0.8659]
[INFO] occupied_cells=1038/3321 (31.25%)
[INFO] top_hotspots=(40,1):92 (20,20):88 (60,20):87 (10,35):79 (70,35):78
[ASCII PREVIEW]
                                        *
                                       * *
                                      *   *
                                     * * * *
                                    *       *
                                   * *     * *
                                  *   *   *   *
                                 * * * * * * * *
                                *               *
                               * *             * *
                              *   *           *   *
                             * * * *         * * * *
[INFO] wrote outputs/sierpinski_seed4242_ascii.txt

Success signal: your summary values should match exactly for the same implementation choices; if your rasterization differs, the geometric structure and deterministic consistency must still hold.

Solution Architecture

High-level architecture:

+-------------------+
| CLI Argument Layer|
+---------+---------+
          |
          v
+-------------------+      +-----------------------+
| Config Validation |----->| Transform Repository  |
+---------+---------+      +-----------+-----------+
          |                            |
          v                            v
+-------------------+      +-----------------------+
| RNG + Iteration   |----->| Point Accumulator     |
| Engine            |      | (density grid/stats)  |
+---------+---------+      +-----------+-----------+
          |                            |
          v                            v
      +---+----------------------------+---+
      | Renderer (ASCII/Image) + Reporter |
      +------------------------------------+

Key Components

Component Responsibility Design Choice
TransformSet Stores affine maps + weights Keep immutable after validation
ChaosEngine Runs seeded iterations Separate from rendering for testability
DensityGrid Converts points to hit counts Integer grid enables deterministic text output
Reporter Prints stats + output path Enables golden transcript comparison

Algorithm Overview

Core loop (conceptual pseudocode):

function run_chaos(config, transform_set):
  rng <- seeded_rng(config.seed)
  p <- initial_point_from_seed(rng)
  grid <- empty_grid(config.width, config.height)
  stats <- init_stats()

  repeat i from 1 to config.burn_in + config.points:
    t <- weighted_pick(transform_set, rng)
    p <- apply_affine(t, p)
    update_bbox(stats, p)

    if i > config.burn_in:
      cell <- map_point_to_cell(p, stats_or_calibration_bbox, config)
      increment(grid, cell)

  return summarize(grid, stats)

Complexity:

  • Time: O(points)
  • Space: O(width * height) for density grid

Tradeoff note:

  • One-pass dynamic bbox can distort mapping early; two-pass (calibrate then render) is cleaner and more stable for deterministic snapshots.

Implementation Guide

Phase 1: Baseline Data Definitions

  1. Define transform data shape and validation rules.
  2. Create named transform sets (start with Sierpinski only).
  3. Add probability normalization check (sum approximately 1.0).

Checkpoint: loading transform set prints validated summary.

Phase 2: Deterministic Iteration Engine

  1. Build seedable RNG wrapper.
  2. Implement weighted transform selection.
  3. Implement affine update and burn-in skipping.

Checkpoint: deterministic sequence test (same seed => same first N transformed points).

Phase 3: Mapping and Rendering

  1. Choose raster mapping strategy (recommended: calibration + render).
  2. Accumulate density counts on a fixed grid.
  3. Render ASCII by density thresholds ( , ., *, #).

Checkpoint: rough Sierpinski shape is visible with 10k+ points.

Phase 4: Reporting and CLI UX

  1. Print run metadata and summary stats.
  2. Save ASCII dump to output directory.
  3. Ensure errors are explicit (bad args, invalid transforms, impossible ranges).

Checkpoint: transcript-style output is stable across runs.

Testing

Deterministic Tests

  1. Same seed + same config => exact same summary hash.
  2. Different seed => different hotspot distribution (but same broad geometry).

Geometry/Logic Tests

  1. weighted_pick empirical frequencies approximate configured weights.
  2. Mapped cells are always within [0, width-1] x [0, height-1].
  3. Burn-in count reduces sampled points exactly as expected.

CLI Regression Test Transcript

$ pytest tests/test_chaos_game_determinism.py -q
....
4 passed in 0.18s

$ python chaos_game.py --fractal sierpinski --points 20000 --burn-in 50 --seed 4242 --mode summary
[INFO] seed=4242
[INFO] sampled=20000
[INFO] checksum=5f7f2d77

Interpretation: a checksum-based summary gives you a compact regression target.

Pitfalls

Symptom Likely Cause Fix
Output is a blob, not a triangle Wrong transform coefficients or missing contraction Re-check A matrices and vertex logic
Run is non-reproducible RNG seeded inconsistently or seed ignored in one path Centralize RNG creation in one component
Pattern is upside-down Y-axis mapping mismatch Apply explicit vertical inversion in raster step
Sparse/noisy preview Too few points or excessive burn-in Increase points, tune burn-in proportion
Edge clipping Incorrect bbox/mapping formula Add boundary assertions and clamp logic

Extensions

  1. Add Barnsley fern transform set and compare density maps.
  2. Support weighted palettes to visualize visit frequency.
  3. Export CSV of sampled points for external plotting.
  4. Add mode to compare two seeds side-by-side.
  5. Implement deterministic two-pass renderer with quantile-based tone mapping.

Real-World Connections

  1. Procedural graphics: fractal generation in art, games, and texture synthesis.
  2. Scientific visualization: attractor exploration in dynamical systems.
  3. Compression intuition: compact rule sets generate complex structures.
  4. Probabilistic modeling: repeated stochastic rules with stable long-run behavior.

Resources

  • Michael F. Barnsley, Fractals Everywhere.
  • Heinz-Otto Peitgen et al., Chaos and Fractals.
  • Gilbert Strang, Linear Algebra and Its Applications (affine transforms background).
  • Robert L. Devaney, A First Course in Chaotic Dynamical Systems.

Self-Assessment

Answer before marking complete:

  1. Why does random transform selection still produce a deterministic attractor shape?
  2. What role does contraction play in chaos-game convergence?
  3. Why is burn-in necessary in practice?
  4. What failure mode appears when mapping math-space to pixels incorrectly?
  5. How would unequal transform probabilities change visual output?
  6. What exact conditions are needed for deterministic reruns?
  7. If your output is mirrored or rotated, what part of the pipeline do you inspect first?
  8. How would you verify correctness without visually inspecting the image?

Completion Criteria

  • CLI accepts all required parameters and rejects invalid inputs clearly.
  • Fixed-seed run produces deterministic summary and saved artifact.
  • Sierpinski structure is clearly visible at target point count.
  • Tests cover deterministic behavior, mapping bounds, and burn-in logic.
  • Output includes a transcript-compatible summary block.
  • You can explain the attractor mechanism and mapping pipeline from memory.