Diffusion Limited Aggregation

dla.go

package main

import (
	"fmt"
	"math"
	"math/rand"

	"github.com/ungerik/go-cairo"
)

func Round(a float64) float64 {
	if a < 0 {
		return math.Ceil(a - 0.5)
	}
	return math.Floor(a + 0.5)
}

type Key struct {
	X, Y int
}

type Point struct {
	X, Y float64
}

type Edge struct {
	A, B Point
}

func RandomPoint(d float64) Point {
	x := d * 0.9
	y := d * 0.9
	if rand.Float64() < 0.5 {
		x = -x
	}
	if rand.Float64() < 0.5 {
		y = -y
	}
	if rand.Float64() < 0.5 {
		x = d * (rand.Float64()*2 - 1)
	} else {
		y = d * (rand.Float64()*2 - 1)
	}
	return Point{x, y}
}

func (point Point) Key() Key {
	x := int(Round(point.X))
	y := int(Round(point.Y))
	return Key{x, y}
}

func (point Point) Distance(other Point) float64 {
	return math.Hypot(point.X-other.X, point.Y-other.Y)
}

func (point Point) Outside(size float64) bool {
	return point.X < -size || point.Y < -size || point.X > size || point.Y > size
}

func (point Point) Walk() Point {
	a := rand.Float64() * 2 * math.Pi
	x := point.X + math.Cos(a)
	y := point.Y + math.Sin(a)
	return Point{x, y}
}

type Model struct {
	Active   []Point
	Inactive []Point
	Edges    []Edge
	Grid     map[Key]Point
	Size     float64
}

func NewModel(size float64, count int) *Model {
	model := Model{}
	model.Size = size
	model.Grid = make(map[Key]Point)
	model.Active = make([]Point, count)
	return &model
}

func (model *Model) Reset() {
	for i := range model.Active {
		model.Active[i] = model.RandomPoint()
	}
}

func (model *Model) Anchor(point, parent Point) {
	model.Grid[point.Key()] = point
	model.Inactive = append(model.Inactive, point)
	model.Edges = append(model.Edges, Edge{parent, point})
}

func (model *Model) Test(point Point) (Point, bool) {
	key := point.Key()
	for dy := -2; dy <= 2; dy++ {
		for dx := -2; dx <= 2; dx++ {
			x := key.X + dx
			y := key.Y + dy
			if other, ok := model.Grid[Key{x, y}]; ok {
				if point.Distance(other) < 1.414 {
					return other, true
				}
			}
		}
	}
	return point, false
}

func (model *Model) RandomPoint() Point {
	for {
		point := RandomPoint(model.Size)
		if _, ok := model.Test(point); !ok {
			return point
		}
	}
}

func (model *Model) Step() {
	for i, point := range model.Active {
		point = point.Walk()
		if point.Outside(model.Size) {
			point = model.RandomPoint()
		}
		model.Active[i] = point
		if parent, ok := model.Test(point); ok {
			// if rand.Float64() < 0.1 {
			model.Anchor(point, parent)
			model.Active[i] = model.RandomPoint()
			// }
		}
	}
}

func (model *Model) Render(scale float64) *cairo.Surface {
	size := int(2 * model.Size * scale)
	dc := cairo.NewSurface(cairo.FORMAT_ARGB32, size, size)
	dc.SetLineCap(cairo.LINE_CAP_ROUND)
	dc.SetLineJoin(cairo.LINE_JOIN_ROUND)
	dc.SetSourceRGB(1, 1, 1)
	dc.Paint()
	dc.Translate(model.Size*scale, model.Size*scale)
	dc.SetSourceRGB(0, 0, 0)
	dc.SetLineWidth(2)
	// for _, point := range model.Inactive {
	// 	x := point.X * scale
	// 	y := point.Y * scale
	// 	dc.NewSubPath()
	// 	dc.Arc(x, y, 1, 0, 2*math.Pi)
	// }
	// dc.Fill()
	for _, edge := range model.Edges {
		x1 := edge.A.X * scale
		y1 := edge.A.Y * scale
		x2 := edge.B.X * scale
		y2 := edge.B.Y * scale
		dc.MoveTo(x1, y1)
		dc.LineTo(x2, y2)
	}
	dc.Stroke()
	return dc
}

func main() {
	model := NewModel(200, 10000)
	model.Anchor(Point{0, 0}, Point{0, 0})
	// model.Anchor(Point{-100, 0}, Point{-100, 0})
	// model.Anchor(Point{100, 0}, Point{100, 0})
	model.Reset()
	i := 0
	previous := 0
	for len(model.Inactive) < 10000 {
		model.Step()
		count := len(model.Inactive)
		if count != previous {
			previous = count
			fmt.Println(i, count)
		}
		i++
	}
	surface := model.Render(4)
	surface.WriteToPNG("out.png")
}