1// Package pack lays out a field as tiles of arbitrary shape (manifest v3).2// A tile is a union of axis-aligned rectangles whose every maximal3// horizontal and vertical run of cells (a line) has even length >= 4. Tiles4// may overlap by any set of cells; uncovered cells are holes. Deterministic5// per seed.6//7// Kinds: "scatter" drops shapes at random positions, sizes and orientations,8// growing one cluster from the seed tile; "grid" is X-by-X squares of side9// N on a pitch of N-1 (the phase-1 standard and the envelope test);10package pack1112import (13 "crypto/sha256"14 "encoding/binary"15 "errors"16 "fmt"17 "math/rand/v2"18 "sort"19)2021const (22 MinN = 6 // smallest square side the square packers draw23 MaxN = 16 // largest side of anything2425 MinLine = 4 // shortest line a shape may have (even)26)2728// MFor is the decided cap on solutions-alone for a tile of the given cell29// count: 2 up to 64 cells, 3 up to 196, 4 beyond.30func MFor(cells int) int {31 switch {32 case cells <= 64:33 return 234 case cells <= 196:35 return 336 default:37 return 438 }39}4041// MByN is MFor for an n-by-n square (kept for the square kinds).42func MByN(n int) int { return MFor(n * n) }4344type Params struct {45 Seed string `json:"seed"`46 Salt string `json:"salt,omitempty"` // extra rng salt (gen re-packs a layout that cannot be given)47 G int `json:"G"` // cells per side of the field48 Kind string `json:"kind"` // scatter | grid49 // grid: every tile the same size50 N int `json:"n,omitempty"`51 // scatter: target share of the field covered (default 0.72), cell count52 // range of a tile (default 16..256), share of drops that are unions of53 // two rectangles (default 0.4).54 Coverage float64 `json:"coverage,omitempty"`55 MinCells int `json:"min_cells,omitempty"`56 MaxCells int `json:"max_cells,omitempty"`57 Compound float64 `json:"compound,omitempty"`58 // scatter: after the drop loop, holes larger than this many cells are59 // filled with small tiles under the same rule (default 24); smaller60 // holes are the gaps and stay61 MaxHole int `json:"max_hole,omitempty"`62 // chunk mode (scatter only): tiles are placed inside Region (x0, y0,63 // w, h on the G field; zero means the whole field); Fixed are immutable64 // tiles from neighbouring chunks in field coordinates with their real65 // ids, which count as cluster members for contact, overlap and66 // containment but are not emitted; new tile ids start at IDBase.67 Region [4]int `json:"region,omitempty"`68 Fixed []Tile `json:"fixed,omitempty"`69 IDBase int `json:"id_base,omitempty"`70 // Accept, when set, is asked about every candidate that shares a cell71 // with a fixed tile (the generator answers with a feasibility check of72 // the candidate over the fixed tiles' cells: a line of the candidate73 // lying inside a fixed tile is fixed too, and need not be balanced).74 // Accept, when set, is asked whether a candidate that touches placed tiles75 // can be completed together with the placed NEW tiles it touches (fixed76 // context is the caller's business); a false rejects the candidate77 Accept func(t Tile, touched []Tile) bool `json:"-"`78}7980// Tile is a shape placed on the field: a bounding box and the rectangles81// (local coordinates) whose union is the shape.82type Tile struct {83 ID int `json:"id"`84 X0 int `json:"x0"`85 Y0 int `json:"y0"`86 W int `json:"w"`87 H int `json:"h"`88 Rects [][4]int `json:"rects"` // local [lx, ly, rw, rh]; rects may overlap89 Cells int `json:"cells"`90 M int `json:"m"`91}9293// Overlap is the set of cells a tile shares with one other tile.94type Overlap struct {95 With int `json:"with"`96 Cells int `json:"cells"`97 Ids []int `json:"-"` // shared global cell ids (y*G+x), sorted98}99100// Layout is a packing. Tiles are the emitted tiles, ids IDBase+index;101// Fixed echoes the immutable context tiles (chunk mode). Overlaps and102// Owners are indexed by position in All() (Tiles then Fixed), not by id.103type Layout struct {104 G int `json:"G"`105 Kind string `json:"kind"`106 SeedTile int `json:"seed_tile"` // index into Tiles107 Tiles []Tile `json:"tiles"`108 Overlaps [][]Overlap `json:"overlaps"` // per All() index, sorted by With (an All() index)109 Report Report `json:"report"`110 Region [4]int `json:"region,omitempty"`111 Fixed []Tile `json:"fixed,omitempty"`112 IDBase int `json:"id_base,omitempty"`113}114115// All lists the emitted tiles followed by the fixed context tiles; it is116// the index space of Overlaps and Owners.117func (L *Layout) All() []Tile {118 if len(L.Fixed) == 0 {119 return L.Tiles120 }121 return append(append([]Tile(nil), L.Tiles...), L.Fixed...)122}123124type Report struct {125 Tiles int `json:"tiles"`126 Coverage float64 `json:"coverage"` // covered cells / G*G127 Holes int `json:"holes"` // 4-connected uncovered components inside the cluster's bounding box128 HoleCells int `json:"hole_cells"`129 MeanHole float64 `json:"mean_hole"`130 ByCells map[string]int `json:"by_cells"` // tiles per cell-count bucket131 Overlaps int `json:"overlaps"` // tile pairs sharing a cell132 MeanOverlap float64 `json:"mean_overlap"`133 Compound int `json:"compound"` // non-rectangular tiles134 MaxHole int `json:"max_hole,omitempty"`135 Filled int `json:"filled,omitempty"` // tiles added by the hole-fill pass136 Stopped string `json:"stopped,omitempty"`137 Salt int `json:"salt,omitempty"` // scatter: rng salt that produced a pinnable layout138}139140// Rect is a rectangle in field or pitch coordinates.141type Rect struct {142 X0, Y0, W, H int143}144145func rngFor(parts ...string) *rand.Rand {146 h := sha256.New()147 for _, s := range parts {148 h.Write([]byte(s))149 h.Write([]byte{0})150 }151 sum := h.Sum(nil)152 return rand.New(rand.NewPCG(binary.LittleEndian.Uint64(sum[:8]), binary.LittleEndian.Uint64(sum[8:16])))153}154155// ---------------------------------------------------------------- shapes156157// Mask returns the tile's cells as a local W*H boolean grid.158func (t Tile) Mask() []bool {159 m := make([]bool, t.W*t.H)160 for _, r := range t.Rects {161 for y := r[1]; y < r[1]+r[3]; y++ {162 for x := r[0]; x < r[0]+r[2]; x++ {163 if x >= 0 && y >= 0 && x < t.W && y < t.H {164 m[y*t.W+x] = true165 }166 }167 }168 }169 return m170}171172// Lines lists every maximal horizontal run, then every maximal vertical173// run, of the shape's cells as local indexes ly*W+lx in order along the run.174func (t Tile) Lines() [][]int {175 return maskLines(t.Mask(), t.W, t.H)176}177178func maskLines(mask []bool, W, H int) [][]int {179 var out [][]int180 for y := 0; y < H; y++ {181 x := 0182 for x < W {183 if !mask[y*W+x] {184 x++185 continue186 }187 var run []int188 for x < W && mask[y*W+x] {189 run = append(run, y*W+x)190 x++191 }192 out = append(out, run)193 }194 }195 for x := 0; x < W; x++ {196 y := 0197 for y < H {198 if !mask[y*W+x] {199 y++200 continue201 }202 var run []int203 for y < H && mask[y*W+x] {204 run = append(run, y*W+x)205 y++206 }207 out = append(out, run)208 }209 }210 return out211}212213// ValidShape checks the shape rules: every line has even length >= MinLine,214// the cells are 4-connected, and the bounding box has no unused row or215// column.216func ValidShape(mask []bool, W, H int) error {217 if len(mask) != W*H || W <= 0 || H <= 0 {218 return errors.New("mask does not match its bounding box")219 }220 cells := 0221 for _, m := range mask {222 if m {223 cells++224 }225 }226 if cells == 0 {227 return errors.New("empty shape")228 }229 lines := maskLines(mask, W, H)230 for _, run := range lines {231 if len(run)%2 != 0 || len(run) < MinLine {232 return fmt.Errorf("line of length %d (need even, >= %d)", len(run), MinLine)233 }234 }235 // uniqueness has to be satisfiable with room to spare: per orientation236 // and length L, at most half of the distinct valid lines of length L237 // may be needed (rows come first in maskLines, then columns)238 rows := 0239 for y := 0; y < H; y++ {240 x := 0241 for x < W {242 if mask[y*W+x] {243 rows++244 for x < W && mask[y*W+x] {245 x++246 }247 } else {248 x++249 }250 }251 }252 for _, part := range [][][]int{lines[:rows], lines[rows:]} {253 byLen := map[int]int{}254 for _, run := range part {255 byLen[len(run)]++256 }257 for L, n := range byLen {258 if n > DistinctLines(L)/2 {259 return fmt.Errorf("%d parallel lines of length %d, at most %d allowed (half of the %d distinct valid lines)", n, L, DistinctLines(L)/2, DistinctLines(L))260 }261 }262 }263 for y := 0; y < H; y++ {264 used := false265 for x := 0; x < W; x++ {266 used = used || mask[y*W+x]267 }268 if !used {269 return fmt.Errorf("row %d of the bounding box is unused", y)270 }271 }272 for x := 0; x < W; x++ {273 used := false274 for y := 0; y < H; y++ {275 used = used || mask[y*W+x]276 }277 if !used {278 return fmt.Errorf("column %d of the bounding box is unused", x)279 }280 }281 // 4-connectivity282 start := -1283 for i, m := range mask {284 if m {285 start = i286 break287 }288 }289 seen := make([]bool, W*H)290 stack := []int{start}291 seen[start] = true292 reached := 0293 for len(stack) > 0 {294 c := stack[len(stack)-1]295 stack = stack[:len(stack)-1]296 reached++297 x, y := c%W, c/W298 for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {299 nx, ny := x+d[0], y+d[1]300 if nx < 0 || ny < 0 || nx >= W || ny >= H {301 continue302 }303 id := ny*W + nx304 if mask[id] && !seen[id] {305 seen[id] = true306 stack = append(stack, id)307 }308 }309 }310 if reached != cells {311 return errors.New("shape is not 4-connected")312 }313 return nil314}315316var distinctCache = map[int]int{}317318// DistinctLines counts the binary lines of even length L that are balanced319// and have no three equal cells in a row: 6 at L=4, 14 at 6, 34 at 8, 84 at320// 10, 208 at 12, 518 at 14, 1296 at 16. Enumerated, and memoised.321func DistinctLines(L int) int {322 if n, ok := distinctCache[L]; ok {323 return n324 }325 count := 0326 var rec func(pos, ones int, a, b int8)327 rec = func(pos, ones int, a, b int8) {328 if ones > L/2 || pos-ones > L/2 {329 return330 }331 if pos == L {332 count++333 return334 }335 for v := int8(0); v <= 1; v++ {336 if pos >= 2 && a == v && b == v {337 continue338 }339 rec(pos+1, ones+int(v), b, v)340 }341 }342 rec(0, 0, -1, -1)343 distinctCache[L] = count344 return count345}346347// normalise trims a tile's bounding box to its cells and recounts.348func (t *Tile) normalise() {349 minX, minY, maxX, maxY := 1<<30, 1<<30, -1, -1350 for _, r := range t.Rects {351 minX = min(minX, r[0])352 minY = min(minY, r[1])353 maxX = max(maxX, r[0]+r[2])354 maxY = max(maxY, r[1]+r[3])355 }356 for i := range t.Rects {357 t.Rects[i][0] -= minX358 t.Rects[i][1] -= minY359 }360 t.X0 += minX361 t.Y0 += minY362 t.W, t.H = maxX-minX, maxY-minY363 t.Cells = 0364 for _, m := range t.Mask() {365 if m {366 t.Cells++367 }368 }369 t.M = MFor(t.Cells)370}371372// globalCells lists the tile's cells as field ids y*G+x.373func (t Tile) globalCells(G int) []int {374 mask := t.Mask()375 out := make([]int, 0, t.Cells)376 for ly := 0; ly < t.H; ly++ {377 for lx := 0; lx < t.W; lx++ {378 if mask[ly*t.W+lx] {379 out = append(out, (t.Y0+ly)*G+t.X0+lx)380 }381 }382 }383 return out384}385386// globalLines is Lines in field ids.387func (t Tile) globalLines(G int) [][]int {388 lines := t.Lines()389 out := make([][]int, len(lines))390 for i, run := range lines {391 out[i] = make([]int, len(run))392 for k, li := range run {393 out[i][k] = (t.Y0+li/t.W)*G + t.X0 + li%t.W394 }395 }396 return out397}398399// ---------------------------------------------------------------- layout400401// Owners returns, per field cell, the All() indexes of the tiles402// containing it.403func (L *Layout) Owners() [][]int {404 own := make([][]int, L.G*L.G)405 for i, t := range L.All() {406 for _, id := range t.globalCells(L.G) {407 own[id] = append(own[id], i)408 }409 }410 return own411}412413// Neighbours lists the All() indexes of the tiles sharing at least one414// cell with the tile at index t.415func (L *Layout) Neighbours(t int) []int {416 out := make([]int, 0, len(L.Overlaps[t]))417 for _, o := range L.Overlaps[t] {418 out = append(out, o.With)419 }420 return out421}422423func overlaps(L *Layout) [][]Overlap {424 own := L.Owners()425 shared := map[[2]int][]int{}426 for id, os := range own {427 for i := 0; i < len(os); i++ {428 for j := i + 1; j < len(os); j++ {429 a, b := os[i], os[j]430 if a > b {431 a, b = b, a432 }433 shared[[2]int{a, b}] = append(shared[[2]int{a, b}], id)434 }435 }436 }437 out := make([][]Overlap, len(L.All()))438 for k, ids := range shared {439 sort.Ints(ids)440 out[k[0]] = append(out[k[0]], Overlap{With: k[1], Cells: len(ids), Ids: ids})441 out[k[1]] = append(out[k[1]], Overlap{With: k[0], Cells: len(ids), Ids: ids})442 }443 for i := range out {444 sort.Slice(out[i], func(a, b int) bool { return out[i][a].With < out[i][b].With })445 }446 return out447}448449func report(L *Layout) Report {450 G := L.G451 r := Report{Tiles: len(L.Tiles), ByCells: map[string]int{}}452 own := L.Owners()453 rx0, ry0, rx1, ry1 := L.regionBox()454 covered := 0455 for y := ry0; y < ry1; y++ {456 for x := rx0; x < rx1; x++ {457 if len(own[y*G+x]) > 0 {458 covered++459 }460 }461 }462 r.Coverage = float64(covered) / float64((rx1-rx0)*(ry1-ry0))463 for _, t := range L.Tiles {464 r.ByCells[bucket(t.Cells)]++465 if len(t.Rects) > 1 && t.Cells != t.W*t.H {466 r.Compound++467 }468 }469 total := 0470 for _, os := range L.Overlaps {471 for _, o := range os {472 r.Overlaps++473 total += o.Cells474 }475 }476 r.Overlaps /= 2477 if r.Overlaps > 0 {478 r.MeanOverlap = float64(total) / float64(2*r.Overlaps)479 }480 for _, h := range holesOf(own, G, L.Tiles, L.regionSlice()...) {481 r.Holes++482 r.HoleCells += len(h.cells)483 }484 if r.Holes > 0 {485 r.MeanHole = float64(r.HoleCells) / float64(r.Holes)486 }487 return r488}489490// regionBox is the placement region as a half-open box (the whole field491// when Region is zero).492func (L *Layout) regionBox() (x0, y0, x1, y1 int) {493 return regionBoxOf(L.Region, L.G)494}495496func (L *Layout) regionSlice() []int {497 x0, y0, x1, y1 := L.regionBox()498 return []int{x0, y0, x1, y1}499}500501func regionBoxOf(r [4]int, G int) (x0, y0, x1, y1 int) {502 if r[2] == 0 || r[3] == 0 {503 return 0, 0, G, G504 }505 return r[0], r[1], min(G, r[0]+r[2]), min(G, r[1]+r[3])506}507508// hole is a 4-connected component of uncovered cells inside the cluster's509// bounding box, with its own bounding box.510type hole struct {511 cells []int512 x0, y0, x1, y1 int513}514515func holesOf(own [][]int, G int, tiles []Tile, box ...int) []hole {516 bx0, by0, bx1, by1 := G, G, 0, 0517 for _, t := range tiles {518 bx0, by0 = min(bx0, t.X0), min(by0, t.Y0)519 bx1, by1 = max(bx1, t.X0+t.W), max(by1, t.Y0+t.H)520 }521 if len(box) == 4 {522 bx0, by0 = max(bx0, box[0]), max(by0, box[1])523 bx1, by1 = min(bx1, box[2]), min(by1, box[3])524 }525 seen := make([]bool, G*G)526 var out []hole527 for y := by0; y < by1; y++ {528 for x := bx0; x < bx1; x++ {529 start := y*G + x530 if len(own[start]) > 0 || seen[start] {531 continue532 }533 h := hole{x0: G, y0: G}534 stack := []int{start}535 seen[start] = true536 for len(stack) > 0 {537 c := stack[len(stack)-1]538 stack = stack[:len(stack)-1]539 h.cells = append(h.cells, c)540 cx, cy := c%G, c/G541 h.x0, h.y0 = min(h.x0, cx), min(h.y0, cy)542 h.x1, h.y1 = max(h.x1, cx+1), max(h.y1, cy+1)543 for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {544 nx, ny := cx+d[0], cy+d[1]545 if nx < bx0 || ny < by0 || nx >= bx1 || ny >= by1 {546 continue547 }548 id := ny*G + nx549 if !seen[id] && len(own[id]) == 0 {550 seen[id] = true551 stack = append(stack, id)552 }553 }554 }555 sort.Ints(h.cells)556 out = append(out, h)557 }558 }559 return out560}561562func bucket(cells int) string {563 switch {564 case cells <= 32:565 return "16-32"566 case cells <= 64:567 return "33-64"568 case cells <= 128:569 return "65-128"570 default:571 return "129-256"572 }573}574575// Pack builds a layout. Errors only on bad parameters.576func Pack(p Params) (*Layout, error) {577 if p.Kind == "" {578 p.Kind = "scatter"579 }580 if p.G < MinN {581 return nil, fmt.Errorf("G must be at least %d", MinN)582 }583 parts := []string{"pack", p.Seed, p.Kind, fmt.Sprint(p.G)}584 if p.Salt != "" {585 parts = append(parts, p.Salt)586 }587 rng := rngFor(parts...)588 L := &Layout{G: p.G, Kind: p.Kind, Region: p.Region, Fixed: p.Fixed, IDBase: p.IDBase}589 if p.Kind != "scatter" && (p.Region != [4]int{} || len(p.Fixed) > 0 || p.IDBase != 0) {590 return nil, fmt.Errorf("chunk mode (region, fixed, id_base) is scatter only")591 }592 switch p.Kind {593 case "scatter":594 // a layout can come out with a tile no neighbour can pin (seed595 // tile boxed in by context); re-draw with a salted rng, bounded596 var err error597 for salt := 0; salt < 8; salt++ {598 r := rng599 if salt > 0 {600 r = rngFor(append(append([]string(nil), parts...), fmt.Sprint("salt", salt))...)601 }602 L = &Layout{G: p.G, Kind: p.Kind, Region: p.Region, Fixed: p.Fixed, IDBase: p.IDBase}603 if err = scatter(L, p, r); err == nil {604 L.Report.Salt = salt605 break606 }607 }608 if err != nil {609 return nil, err610 }611 case "grid":612 squares, err := squarePack(p, rng)613 if err != nil {614 return nil, err615 }616 for i, r := range squares {617 n := r.W + 1618 t := Tile{ID: i, X0: r.X0, Y0: r.Y0, W: n, H: n, Rects: [][4]int{{0, 0, n, n}}, Cells: n * n, M: MFor(n * n)}619 L.Tiles = append(L.Tiles, t)620 }621 L.SeedTile = rng.IntN(len(L.Tiles))622 default:623 return nil, fmt.Errorf("unknown packer %q", p.Kind)624 }625 L.Overlaps = overlaps(L)626 rep := report(L)627 rep.Stopped, rep.MaxHole, rep.Filled, rep.Salt = L.Report.Stopped, L.Report.MaxHole, L.Report.Filled, L.Report.Salt628 L.Report = rep629 return L, nil630}631632// squarePack lays the grid kind in pitch space (a tile of side n is a633// square of side n-1; tiles are disjoint there and share a border of cells634// in field space) and returns the squares sorted by y then x.635func squarePack(p Params, rng *rand.Rand) ([]Rect, error) {636 S := p.G - 1637 var squares []Rect638 switch p.Kind {639 case "grid":640 if p.N < MinN || p.N > MaxN || p.N%2 != 0 {641 return nil, fmt.Errorf("grid needs even n in %d..%d", MinN, MaxN)642 }643 s := p.N - 1644 if S%s != 0 {645 return nil, fmt.Errorf("G-1 = %d is not a multiple of n-1 = %d", S, s)646 }647 for y := 0; y < S; y += s {648 for x := 0; x < S; x += s {649 squares = append(squares, Rect{x, y, s, s})650 }651 }652 }653 sort.Slice(squares, func(i, j int) bool {654 if squares[i].Y0 != squares[j].Y0 {655 return squares[i].Y0 < squares[j].Y0656 }657 return squares[i].X0 < squares[j].X0658 })659 return squares, nil660}661662// ---------------------------------------------------------------- scatter663664// scatterState is the growing cluster: an owner index and, per placed665// tile, its cells and lines in field ids.666type scatterState struct {667 G int668 own [][]int // per cell, keys of the tiles covering it669 tiles map[int]Tile670 cells map[int][]int671 lines map[int][][]int672 stamp []int // per cell, the candidate id that last covered it673 cand int674 // placement region (half-open) and the cells counted for coverage675 rx0, ry0, rx1, ry1 int676 accept func(t Tile, touched []Tile) bool // joint feasibility of a candidate with the placed new tiles it touches677}678679func newScatterState(G int, region [4]int) *scatterState {680 s := &scatterState{G: G, own: make([][]int, G*G), tiles: map[int]Tile{}, cells: map[int][]int{}, lines: map[int][][]int{}}681 s.rx0, s.ry0, s.rx1, s.ry1 = regionBoxOf(region, G)682 return s683}684685// place registers a tile under key (fixed context tiles use negative686// keys, emitted tiles their index).687func (s *scatterState) place(key int, t Tile) {688 cells := t.globalCells(s.G)689 for _, id := range cells {690 s.own[id] = append(s.own[id], key)691 }692 s.tiles[key] = t693 s.cells[key] = cells694 s.lines[key] = t.globalLines(s.G)695}696697func (s *scatterState) inRegion(t Tile) bool {698 return t.X0 >= s.rx0 && t.Y0 >= s.ry0 && t.X0+t.W <= s.rx1 && t.Y0+t.H <= s.ry1699}700701// geom is a shape's cells and lines as local indexes, computed once per702// shape and translated per candidate position.703type geom struct {704 cells []int705 lines [][]int706}707708func geomOf(t Tile) geom {709 mask := t.Mask()710 g := geom{lines: maskLines(mask, t.W, t.H)}711 for i, in := range mask {712 if in {713 g.cells = append(g.cells, i)714 }715 }716 return g717}718719// accepts applies the placement rule to a candidate against the placed720// tiles: inside the field, touching the cluster, and for every touched721// tile the shared cells number at least MinLine, contain a whole line722// (length >= MinLine) of either tile, are at most a quarter of the smaller723// tile, and add at most two cells that would have three or more owners.724// Containment is impossible under the quarter rule.725func (s *scatterState) accepts(t Tile) (bool, string) {726 return s.acceptsAs(t, geomOf(t), false)727}728729// acceptsAs is accepts with the fill-pass variant: a filler additionally730// keeps at least half of its cells unshared in total (pinned on two or731// three sides it is still a puzzle), while the per-neighbour quarter cap732// and the whole-line requirement stay. g is the candidate's geometry.733func (s *scatterState) acceptsAs(t Tile, g geom, filler bool) (bool, string) {734 if !s.inRegion(t) {735 return false, "outside"736 }737 if s.stamp == nil {738 s.stamp = make([]int, s.G*s.G)739 }740 s.cand++741 at := func(li int) int { return (t.Y0+li/t.W)*s.G + t.X0 + li%t.W }742 // shared cells per touched tile, and cells that would get a third owner743 type touch struct{ id, cells, triple int }744 var touched []touch745 total := 0746 for _, li := range g.cells {747 id := at(li)748 s.stamp[id] = s.cand749 os := s.own[id]750 if len(os) > 0 {751 total++752 }753 for _, o := range os {754 k := -1755 for i := range touched {756 if touched[i].id == o {757 k = i758 break759 }760 }761 if k < 0 {762 touched = append(touched, touch{id: o})763 k = len(touched) - 1764 }765 touched[k].cells++766 if len(os) >= 2 {767 touched[k].triple++768 }769 }770 }771 if len(touched) == 0 {772 return false, "isolated"773 }774 if filler && total*2 > t.Cells {775 return false, "filler more than half shared"776 }777 for _, tc := range touched {778 if tc.cells < MinLine {779 return false, "overlap too small"780 }781 smaller := min(t.Cells, s.tiles[tc.id].Cells)782 if tc.cells*4 > smaller {783 return false, "overlap too large"784 }785 if tc.cells == smaller {786 return false, "containment"787 }788 if tc.triple > 2 {789 return false, "too many junction cells"790 }791 full := false792 for _, run := range g.lines {793 if len(run) < MinLine {794 continue795 }796 all := true797 for _, li := range run {798 if !s.ownedBy(at(li), tc.id) {799 all = false800 break801 }802 }803 if all {804 full = true805 break806 }807 }808 if !full {809 for _, run := range s.lines[tc.id] {810 if len(run) < MinLine {811 continue812 }813 all := true814 for _, id := range run {815 if s.stamp[id] != s.cand {816 all = false817 break818 }819 }820 if all {821 full = true822 break823 }824 }825 }826 if !full {827 return false, "no whole line in overlap"828 }829 }830 if s.accept != nil && len(touched) > 0 {831 var news []Tile832 for _, tc := range touched {833 if tc.id >= 0 {834 news = append(news, s.tiles[tc.id])835 }836 }837 if !s.accept(t, news) {838 return false, "infeasible with its neighbours over the fixed context"839 }840 }841 return true, ""842}843844func (s *scatterState) ownedBy(id, o int) bool {845 for _, w := range s.own[id] {846 if w == o {847 return true848 }849 }850 return false851}852853// drawShape draws a shape at the origin: an even-sided rectangle, or with854// probability compound the union of two intersecting even-sided rectangles855// at an even offset (L, T, plus, stepped). Sizes keep the cell count in856// [minCells, maxCells].857func drawShape(rng *rand.Rand, minCells, maxCells int, compound float64) Tile {858 even := func(lo, hi int) int { return lo + 2*rng.IntN((hi-lo)/2+1) }859 for {860 w, h := even(MinLine, MaxN), even(MinLine, MaxN)861 t := Tile{Rects: [][4]int{{0, 0, w, h}}}862 if rng.Float64() < compound {863 w2, h2 := even(MinLine, MaxN), even(MinLine, MaxN)864 // even offset such that the rectangles intersect865 dx := even(-(w2 - 2), w-2)866 dy := even(-(h2 - 2), h-2)867 t.Rects = append(t.Rects, [4]int{dx, dy, w2, h2})868 }869 t.normalise()870 if t.W > MaxN || t.H > MaxN || t.Cells < minCells || t.Cells > maxCells {871 continue872 }873 if ValidShape(t.Mask(), t.W, t.H) != nil {874 continue875 }876 return t877 }878}879880// scatter grows one cluster from the seed tile: every drop is anchored to881// a random placed tile so its bounding box overlaps that tile's, at a882// jittered offset, and is kept when accepts says so. Stops at the coverage883// target or after maxReject consecutive rejections.884func scatter(L *Layout, p Params, rng *rand.Rand) error {885 G := p.G886 if p.Coverage == 0 {887 p.Coverage = 0.72888 }889 if p.MinCells == 0 {890 p.MinCells = 16891 }892 if p.MaxCells == 0 {893 p.MaxCells = 256894 }895 if p.Compound == 0 {896 p.Compound = 0.4897 }898 if p.MaxHole == 0 {899 p.MaxHole = 24900 }901 if p.MinCells < MinLine*MinLine || p.MaxCells > MaxN*MaxN || p.MinCells > p.MaxCells {902 return fmt.Errorf("scatter cell range %d..%d out of %d..%d", p.MinCells, p.MaxCells, MinLine*MinLine, MaxN*MaxN)903 }904 if G < MaxN {905 return fmt.Errorf("scatter needs G >= %d", MaxN)906 }907 const maxReject = 4000908 st := newScatterState(G, p.Region)909 st.accept = p.Accept910 if st.rx1-st.rx0 < MaxN || st.ry1-st.ry0 < MaxN {911 return fmt.Errorf("scatter region %v is smaller than %d cells", p.Region, MaxN)912 }913 // fixed context tiles: members of the cluster, never emitted914 for k, f := range p.Fixed {915 st.place(-1-k, f)916 }917 // anchors are every placed tile, fixed or new918 anchors := append([]Tile(nil), p.Fixed...)919 covered := 0920 for y := st.ry0; y < st.ry1; y++ {921 for x := st.rx0; x < st.rx1; x++ {922 if len(st.own[y*G+x]) > 0 {923 covered++924 }925 }926 }927 seed := drawShape(rng, p.MinCells, p.MaxCells, p.Compound)928 seed.ID = p.IDBase929 seed.X0 = st.rx0 + rng.IntN(st.rx1-st.rx0-seed.W+1)930 seed.Y0 = st.ry0 + rng.IntN(st.ry1-st.ry0-seed.H+1)931 if len(p.Fixed) > 0 {932 // the seed must not sit on the context: draw positions (and, past933 // the first few hundred, smaller shapes) until it is clear of every934 // fixed tile or accepted as an overlap of one; a region so crowded935 // that nothing lands is a packing failure, never a silent overlap936 placed := false937 for try := 0; try < 2000 && !placed; try++ {938 if try > 0 && try%200 == 0 {939 // smaller shapes land more easily; never below 8x8, which940 // drawShape could not satisfy under the shape rules941 seed = drawShape(rng, p.MinCells, max(64, p.MaxCells/(1+try/200)), p.Compound)942 seed.ID = p.IDBase943 }944 seed.X0 = st.rx0 + rng.IntN(st.rx1-st.rx0-seed.W+1)945 seed.Y0 = st.ry0 + rng.IntN(st.ry1-st.ry0-seed.H+1)946 clear := true947 for _, id := range seed.globalCells(G) {948 if len(st.own[id]) > 0 {949 clear = false950 break951 }952 }953 if clear {954 placed = true955 break956 }957 if ok, _ := st.accepts(seed); ok {958 placed = true959 }960 }961 if !placed {962 // nothing lands as a drop: try the fill pass's small shapes over963 // the region's free cells under the filler rule, largest first964 var free []int965 for y := st.ry0; y < st.ry1; y++ {966 for x := st.rx0; x < st.rx1; x++ {967 if len(st.own[y*G+x]) == 0 {968 free = append(free, y*G+x)969 }970 }971 }972 rng.Shuffle(len(free), func(a, b int) { free[a], free[b] = free[b], free[a] })973 fillers:974 for si, shape := range fillShapes {975 sg := fillGeoms[si]976 evals := 0977 for _, c := range free {978 for _, li := range sg.cells {979 evals++980 if evals > 400 {981 continue fillers982 }983 t := shape984 t.Rects = append([][4]int(nil), shape.Rects...)985 t.ID = p.IDBase986 t.X0, t.Y0 = c%G-li%shape.W, c/G-li/shape.W987 if !st.inRegion(t) {988 continue989 }990 if ok, _ := st.acceptsAs(t, sg, true); ok {991 seed = t992 placed = true993 break fillers994 }995 }996 }997 }998 }999 if !placed {1000 // the context covers the region: nothing to generate here (a1001 // grown ring's chunk under its neighbours' tiles); an empty1002 // layout, not a failure1003 L.Report.Stopped = "covered"1004 return nil1005 }1006 }1007 L.Tiles = append(L.Tiles, seed)1008 st.place(0, seed)1009 anchors = append(anchors, seed)1010 L.SeedTile = 01011 for _, id := range st.cells[0] {1012 if len(st.own[id]) == 1 && id%G >= st.rx0 && id%G < st.rx1 && id/G >= st.ry0 && id/G < st.ry1 {1013 covered++1014 }1015 }1016 target := int(p.Coverage * float64((st.rx1-st.rx0)*(st.ry1-st.ry0)))1017 rejects := 01018 for covered < target {1019 if rejects >= maxReject {1020 L.Report.Stopped = "rejections"1021 break1022 }1023 // compound drops are rejected more often than rectangles, so the1024 // draw probability is steered by the accepted share1025 pc := p.Compound1026 if n := len(L.Tiles); n >= 5 {1027 share := max(0.05, float64(compoundCount(L.Tiles))/float64(n))1028 pc = min(0.95, max(0.05, p.Compound*p.Compound/share))1029 }1030 t := drawShape(rng, p.MinCells, p.MaxCells, pc)1031 a := anchors[rng.IntN(len(anchors))]1032 // bounding boxes overlap: X0 in [a.X0-t.W+1, a.X0+a.W-1]1033 t.X0 = a.X0 - t.W + 1 + rng.IntN(a.W+t.W-1)1034 t.Y0 = a.Y0 - t.H + 1 + rng.IntN(a.H+t.H-1)1035 t.ID = p.IDBase + len(L.Tiles)1036 ok, _ := st.accepts(t)1037 if !ok {1038 rejects++1039 continue1040 }1041 rejects = 01042 key := len(L.Tiles)1043 L.Tiles = append(L.Tiles, t)1044 st.place(key, t)1045 anchors = append(anchors, t)1046 for _, id := range st.cells[key] {1047 if len(st.own[id]) == 1 {1048 covered++1049 }1050 }1051 }1052 if L.Report.Stopped == "" {1053 L.Report.Stopped = "coverage"1054 }1055 // the seed tile is the one tile placed touching nothing; if no later1056 // drop overlapped it by a whole line it cannot be pinned by any1057 // neighbour and the generator's "an alternative differs inside an1058 // overlap region" is unsatisfiable for it. Drop a tile onto it now.1059 if !st.pinnable(0) {1060 seed := L.Tiles[0]1061 placed := false1062 for try := 0; try < 4000 && !placed; try++ {1063 t := drawShape(rng, p.MinCells, p.MaxCells, p.Compound)1064 t.X0 = seed.X0 - t.W + 1 + rng.IntN(seed.W+t.W-1)1065 t.Y0 = seed.Y0 - t.H + 1 + rng.IntN(seed.H+t.H-1)1066 t.ID = p.IDBase + len(L.Tiles)1067 if ok, _ := st.accepts(t); !ok {1068 continue1069 }1070 key := len(L.Tiles)1071 L.Tiles = append(L.Tiles, t)1072 st.place(key, t)1073 placed = st.pinnable(0)1074 }1075 if !placed {1076 return fmt.Errorf("seed tile %d (%dx%d at %d,%d) admits no neighbour with a whole-line overlap", seed.ID, seed.W, seed.H, seed.X0, seed.Y0)1077 }1078 }1079 L.Report.MaxHole = p.MaxHole1080 L.Report.Filled = fillHoles(L, p, st, rng)1081 for k := range L.Tiles {1082 if !st.pinnable(k) {1083 t := L.Tiles[k]1084 return fmt.Errorf("tile %d (%dx%d at %d,%d) has no overlap of at least %d cells", t.ID, t.W, t.H, t.X0, t.Y0, MinLine)1085 }1086 }1087 return nil1088}10891090// pinnable reports whether placed tile key shares at least MinLine cells1091// with some other member of the cluster (fixed or new): the precondition1092// for a neighbour to be able to pin it.1093func (s *scatterState) pinnable(key int) bool {1094 counts := map[int]int{}1095 for _, id := range s.cells[key] {1096 for _, o := range s.own[id] {1097 if o != key {1098 counts[o]++1099 if counts[o] >= MinLine {1100 return true1101 }1102 }1103 }1104 }1105 return false1106}11071108// fillShapes are the small valid shapes the fill pass draws from, largest1109// first: 8x8, 8x6, 6x8, 6x6, the notched 6x6 (four corners), and every L1110// or T union of two of those rectangles at an even offset that fits a1111// 12x12 box, deduplicated by mask.1112var fillShapes = func() []Tile {1113 bases := [][2]int{{8, 8}, {8, 6}, {6, 8}, {6, 6}}1114 seen := map[string]bool{}1115 var out []Tile1116 add := func(rects [][4]int) {1117 t := Tile{Rects: rects}1118 t.normalise()1119 if t.W > 12 || t.H > 12 || ValidShape(t.Mask(), t.W, t.H) != nil {1120 return1121 }1122 key := fmt.Sprint(t.W, t.H, t.Mask())1123 if seen[key] {1124 return1125 }1126 seen[key] = true1127 out = append(out, t)1128 }1129 for _, b := range bases {1130 add([][4]int{{0, 0, b[0], b[1]}})1131 for _, c := range bases {1132 for dx := -(c[0] - 2); dx <= b[0]-2; dx += 2 {1133 for dy := -(c[1] - 2); dy <= b[1]-2; dy += 2 {1134 add([][4]int{{0, 0, b[0], b[1]}, {dx, dy, c[0], c[1]}})1135 }1136 }1137 }1138 }1139 for _, corner := range [][4]int{{0, 0, 2, 2}, {4, 0, 2, 2}, {0, 4, 2, 2}, {4, 4, 2, 2}} {1140 // 6x6 minus a 2x2 corner, as two overlapping rectangles1141 var rects [][4]int1142 if corner[1] == 0 {1143 rects = [][4]int{{0, 2, 6, 4}, {2 - corner[0]/2, 0, 4, 6}}1144 } else {1145 rects = [][4]int{{0, 0, 6, 4}, {2 - corner[0]/2, 0, 4, 6}}1146 }1147 add(rects)1148 }1149 sort.SliceStable(out, func(i, j int) bool { return out[i].Cells > out[j].Cells })1150 return out1151}()11521153var fillGeoms = func() []geom {1154 out := make([]geom, len(fillShapes))1155 for i, sh := range fillShapes {1156 out[i] = geomOf(sh)1157 }1158 return out1159}()11601161// fillHoles covers every hole larger than MaxHole with small shapes1162// (fillShapes, largest that can land first) placed so the shape covers a1163// cell of the hole and is accepted under the filler rule (acceptsAs),1164// until every remaining hole is at most MaxHole or a hole takes no shape1165// at any position. Holes at or under MaxHole are left alone: they are the1166// gaps. Positions are enumerated, not sampled: for each hole cell in a1167// seeded order, every offset that puts the shape over that cell, with a1168// budget per shape. After a placement the hole is re-flooded locally (it1169// may have split) and the pieces go back on the work list. Returns the1170// number of tiles added.1171func fillHoles(L *Layout, p Params, st *scatterState, rng *rand.Rand) int {1172 const perShape = 120 // position evaluations per shape and hole1173 G := L.G1174 added := 01175 bx0, by0, bx1, by1 := clusterBox(L.Tiles, G)1176 bx0, by0, bx1, by1 = max(bx0, st.rx0), max(by0, st.ry0), min(bx1, st.rx1), min(by1, st.ry1)1177 work := holesOf(st.own, G, L.Tiles, bx0, by0, bx1, by1)1178 for len(work) > 0 {1179 h := work[len(work)-1]1180 work = work[:len(work)-1]1181 if len(h.cells) <= p.MaxHole {1182 continue1183 }1184 order := append([]int(nil), h.cells...)1185 rng.Shuffle(len(order), func(a, b int) { order[a], order[b] = order[b], order[a] })1186 placed := false1187 shapes:1188 for si, shape := range fillShapes {1189 // a filler keeps at least half of its cells unshared, so it1190 // needs at least that many hole cells to land on1191 if shape.Cells > 2*len(h.cells) {1192 continue1193 }1194 sg := fillGeoms[si]1195 evals := 01196 for _, c := range order {1197 cx, cy := c%G, c/G1198 for _, li := range sg.cells {1199 evals++1200 if evals > perShape {1201 continue shapes1202 }1203 t := shape1204 t.Rects = append([][4]int(nil), shape.Rects...)1205 t.ID = p.IDBase + len(L.Tiles)1206 t.X0, t.Y0 = cx-li%shape.W, cy-li/shape.W1207 if ok, _ := st.acceptsAs(t, sg, true); !ok {1208 continue1209 }1210 key := len(L.Tiles)1211 L.Tiles = append(L.Tiles, t)1212 st.place(key, t)1213 added++1214 placed = true1215 break shapes1216 }1217 }1218 }1219 if !placed {1220 continue // stuck: geometry admits no filler here1221 }1222 // re-flood what is left of this hole; it may have split1223 seen := map[int]bool{}1224 for _, c := range h.cells {1225 if len(st.own[c]) > 0 || seen[c] {1226 continue1227 }1228 piece := floodHole(st.own, G, c, bx0, by0, bx1, by1, seen)1229 work = append(work, piece)1230 }1231 }1232 return added1233}12341235func clusterBox(tiles []Tile, G int) (x0, y0, x1, y1 int) {1236 x0, y0, x1, y1 = G, G, 0, 01237 for _, t := range tiles {1238 x0, y0 = min(x0, t.X0), min(y0, t.Y0)1239 x1, y1 = max(x1, t.X0+t.W), max(y1, t.Y0+t.H)1240 }1241 return1242}12431244// floodHole collects the uncovered 4-connected component containing start,1245// within the box, marking seen.1246func floodHole(own [][]int, G, start, bx0, by0, bx1, by1 int, seen map[int]bool) hole {1247 h := hole{x0: G, y0: G}1248 stack := []int{start}1249 seen[start] = true1250 for len(stack) > 0 {1251 c := stack[len(stack)-1]1252 stack = stack[:len(stack)-1]1253 h.cells = append(h.cells, c)1254 cx, cy := c%G, c/G1255 h.x0, h.y0 = min(h.x0, cx), min(h.y0, cy)1256 h.x1, h.y1 = max(h.x1, cx+1), max(h.y1, cy+1)1257 for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {1258 nx, ny := cx+d[0], cy+d[1]1259 if nx < bx0 || ny < by0 || nx >= bx1 || ny >= by1 {1260 continue1261 }1262 id := ny*G + nx1263 if !seen[id] && len(own[id]) == 0 {1264 seen[id] = true1265 stack = append(stack, id)1266 }1267 }1268 }1269 sort.Ints(h.cells)1270 return h1271}12721273// UnfillableHoles counts the holes over MaxHole whose centroid lies inside1274// the convex hull of the tiles' corners: pockets the geometry could not1275// close (holes outside the hull are the field's ragged edge, not gaps).1276func (L *Layout) UnfillableHoles(maxHole int) int {1277 var pts [][2]int1278 for _, t := range L.Tiles {1279 pts = append(pts, [2]int{t.X0, t.Y0}, [2]int{t.X0 + t.W, t.Y0}, [2]int{t.X0, t.Y0 + t.H}, [2]int{t.X0 + t.W, t.Y0 + t.H})1280 }1281 hull := convexHull(pts)1282 n := 01283 for _, h := range holesOf(L.Owners(), L.G, L.Tiles, L.regionSlice()...) {1284 if len(h.cells) <= maxHole {1285 continue1286 }1287 sx, sy := 0.0, 0.01288 for _, c := range h.cells {1289 sx += float64(c%L.G) + 0.51290 sy += float64(c/L.G) + 0.51291 }1292 if insideHull(hull, sx/float64(len(h.cells)), sy/float64(len(h.cells))) {1293 n++1294 }1295 }1296 return n1297}12981299func convexHull(pts [][2]int) [][2]int {1300 sort.Slice(pts, func(i, j int) bool {1301 if pts[i][0] != pts[j][0] {1302 return pts[i][0] < pts[j][0]1303 }1304 return pts[i][1] < pts[j][1]1305 })1306 cross := func(o, a, b [2]int) int { return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]) }1307 var lower, upper [][2]int1308 for _, p := range pts {1309 for len(lower) >= 2 && cross(lower[len(lower)-2], lower[len(lower)-1], p) <= 0 {1310 lower = lower[:len(lower)-1]1311 }1312 lower = append(lower, p)1313 }1314 for i := len(pts) - 1; i >= 0; i-- {1315 p := pts[i]1316 for len(upper) >= 2 && cross(upper[len(upper)-2], upper[len(upper)-1], p) <= 0 {1317 upper = upper[:len(upper)-1]1318 }1319 upper = append(upper, p)1320 }1321 return append(lower[:len(lower)-1], upper[:len(upper)-1]...)1322}13231324func insideHull(hull [][2]int, x, y float64) bool {1325 for i := range hull {1326 a, b := hull[i], hull[(i+1)%len(hull)]1327 if (float64(b[0]-a[0]))*(y-float64(a[1]))-(float64(b[1]-a[1]))*(x-float64(a[0])) < 0 {1328 return false1329 }1330 }1331 return true1332}13331334func compoundCount(tiles []Tile) int {1335 n := 01336 for _, t := range tiles {1337 if t.Cells != t.W*t.H {1338 n++1339 }1340 }1341 return n1342}