301 Days (redux)

Another metric leap year of gamedev experiments and such

New Day 11 - Wave and Collapse Pt 1

Sep 1, 2023 - 15 minute read - NewDaysglitch-aura-djinn

Coast collapsing, waves crashing.

In which we start to play around with wave function collapse. Ish.


But First…

Package Up that Map Code

Ok, let’s push that map code into a package and the main function off into a subdirectory. Since map is a reserved word, we’ll just start building a world package. And we’ll name the read-parse-reproduce-print code mapeater just for fun. Roughly following the norms in golang-standards/project-layout for now:

$ tree --gitignore
.
├── check_maps.sh
├── cmd
│   └── mapeater
│       ├── main.go
│       └── main_test.go
├── go.mod
├── go.sum
├── go.work
├── pkg
│   └── world
│       ├── world.go
│       └── world_test.go
├── README.md
└── testdata
    ├── fuzz
    └── maps
        ├── Annwn.txt
        ├── Axe Glacier.txt
...

Let’s Try Something Fun

As nostalgic as I am for old game maps, one of the treasured memories is exploring them for the first time. And one way to keep that exploration itch scratched is to keep generating new terrain. Hence a fascination with one of the key features of “Roguelike” games, procedural generation of levels. So it was my habitual attendance of the Roguelike Celebration and Brian Bucklew’s presentation that introduced me to Wave Function Collapse.

Then I saw it on The Coding Train and elsewhere, and added it to the big list of things to try out someday. This seems like as good a day as any, especially to play with the maps and code that I have at hand.

As a small level to mess with, we’ll use the Ruined Tavern Cellar from Annwn. It’s just 9x13, but should provide an minimal interesting set of rules.

<z>-25</z> <x>38</x> <y>18</y> <n>Ruined Tavern Cellar</n>
/\/\/\/\/\/\/\/\/\/\/\/\/\
/\[][][][][][][][][][][]/\
/\[]dn. []. . . []. up[]/\
/\[]. . []. [][][]--[][]/\
/\[][_[][]. . . []. . []/\
/\[]. . []. [][][]. . []/\
/\[]. . . . . . | . . []/\
/\[][][][][][][][][][][]/\
/\/\/\/\/\/\/\/\/\/\/\/\/\

Just Random Tiles

As a basis for comparison, let’s start with generating a new map using just random tiles, limited to the tiles that are used within an input map.

randotiles/main.go GitLab
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
func randotiles1(header world.MapHeader, contents world.MapContents) string {
	cellTypes := collectCellTypes(contents.Cells)

	newMap := world.MapContents{
		Cells: make(map[world.CellKey]world.Cell, len(contents.Cells)),
	}

	for key := range contents.Cells {
		newMap.Cells[key] = world.Cell{
			Graphic: cellTypes[rand.Intn(len(cellTypes))],
		}
	}

	return world.MapToString(header, newMap)
}
<z>-25</z> <x>38</x> <y>18</y> <n>Ruined Tavern Cellar</n>
[_/\dnup[_--up/\--dndnup|
updn| /\/\[]| . dn. dn| /\
--up------/\dn[]dn----. |
up[]/\| dn. --up[_| --[][]
. /\[_[]up. /\[]--/\| | [_
dnup----[_. /\| []. /\| dn
[]| | . up[_[_dn[]. [][]dn
| dnup[]up/\up| . up| . [_
| up/\dn. [_[]| updn--/\.

The original had one up and one down stair, but this looks a little more Escher-esque. Maybe we should pay a little attention to tile frequency.

Weighted Random Tiles

Now when we pick a tile for a cell, let’s weight the choices by their frequency in the original map:

randotiles/main.go GitLab
76
77
78
79
80
81
82
83
84
85
86
87
func randotiles2(header world.MapHeader, contents world.MapContents) string {
	cellTypes := countCellTypes(contents.Cells)

	newMap := world.MapContents{
		Cells: make(map[world.CellKey]world.Cell, len(contents.Cells)),
	}
	for key := range contents.Cells {
		newMap.Cells[key] = world.Cell{Graphic: weightedRandomString(cellTypes)}
	}
	result := world.MapToString(header, newMap)
	return result
}
<z>-25</z> <x>38</x> <y>18</y> <n>Ruined Tavern Cellar</n>
. []/\[]. . . /\/\/\[][]/\
/\. []. /\[]. /\. []/\up.
. [][]/\[]. []. /\. /\. []
/\/\[]. /\[]/\[]--/\[]. .
[]/\/\[]/\. . . /\/\. [][]
/\[][]/\. /\/\. . . [][]/\
[][_/\/\/\[_/\. . /\. [].
[][]. /\[]/\. /\[_. /\[][]
/\[][][][]. . . . []/\. /\

Better. But what if we want to make sure we use each tile the same number of times it was used in the original?

Tile Shuffle

Now when we pull a weighted random tile, we’ll remove it from the pile:

randotiles/main.go GitLab
100
101
102
103
104
105
106
107
108
109
110
111
112
113
func randotiles3(header world.MapHeader, contents world.MapContents) string {
	cellTypes := countCellTypes(contents.Cells)

	newMap := world.MapContents{
		Cells: make(map[world.CellKey]world.Cell, len(contents.Cells)),
	}
	for key := range contents.Cells {
		graphic := weightedRandomString(cellTypes)
		newMap.Cells[key] = world.Cell{Graphic: graphic}
		cellTypes[graphic]--
	}
	result := world.MapToString(header, newMap)
	return result
}
<z>-25</z> <x>38</x> <y>18</y> <n>Ruined Tavern Cellar</n>
. []. /\[]. [][][][]. [][]
/\--/\/\/\/\. [][]. /\[][]
[]/\/\/\[][]/\. [][][]/\[]
[]/\[]/\/\[][]/\[]/\/\. /\
. /\up/\/\. . . []. /\/\.
. [_[]/\[]dn[][][]. /\/\.
/\[]/\/\[][]/\/\. /\[][][]
. /\[][]| [][][]/\/\. /\/\
. . []. []. []. []. []/\/\

At least this way there’s a consistent set of stairs, but I still wouldn’t say that it resembles the original map. Time to collapse some wave functions or something.

Radically Simple Tiled Model

One of the oft-cited yet approachable texts on wave function collapse is Robert Heaton’s 2018-12-17 post The Wavefunction Collapse Algorithm explained very clearly. In it, he references the Simple Tiled Model of WFC, and introduces an Even Simpler Tiled Model. Let’s go one step further, and start with a Radically Simple Tiled Model.

In the Simple Tiled Model, we use predefined tiles and consider only their immediate neighbors. In the Even Simpler Tiled Model, we ignore the orientation of the tiles. For the Radically Simple, let’s ignore the position of the neighbors, and only limit what tile can appear beside what tile. That is, instead of the rules looking like (SEA, COAST, LEFT), we just have (SEA, COAST).

How Simple Can We Get?

For a first pass, we just grab a minimal-entropy cell at random, pull one of its potential tiles at random, and disallow the appropriate neighbors; rinse and repeat.

cmd/rstm/main.go GitLab
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
func rstm1(header world.MapHeader, contents world.MapContents, rng *rand.Rand) string {
	// Using termenv to move the cursor back to home without clearing the screen,
	//   for smoother animation.
	output := termenv.NewOutput(os.Stdout)

	// gather the tiles based on the source map; each weight will be 1 in this case.
	initialWeights := gatherTiles(contents.Cells)

	// initialize the wave map, with all identical cells based on those weights.
	waveMap := createWaveMap(contents, initialWeights)

	// Gather the rule set from the source map.
	ruleSet := deriveRuleSet(contents.Cells)

	// Settings for pretty display while running.
	dispPerCollapse := 2
	sleepPerDisp := 10 * time.Millisecond

	// Now collapse the map.
	collapseMap(waveMap, ruleSet, dispPerCollapse, header, output, sleepPerDisp, rng)

	// Convert the map to a string to return.
	return world.MapToString(header, waveMapToContents(waveMap, rng))
}
cmd/rstm/main.go GitLab
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
func collapseMap(waveMap WaveMapContents, ruleSet []NeighborRule, dispPerCollapse int, header world.MapHeader,
	output *termenv.Output, sleepPerDisp time.Duration, rng *rand.Rand) {
	// Loop until there are no cells with entropy.
	for maxEntropy(waveMap) > 1 {
		// Gather the cells with minimum entropy and choose one.
		minEntropyCellList := minEntropyCells(waveMap)
		randIndex := rng.Intn(len(minEntropyCellList))
		cellToCollapse := minEntropyCellList[randIndex]

		// Collapse the cell, then apply the rules to its neighbors.
		collapseCell(waveMap, cellToCollapse, rng)
		applyRules(waveMap, ruleSet, cellToCollapse)

		// Display the map, in the upper-left corner of the terminal. For cells
		//   that haven't been collapsed, we choose a possible tile at random, so
		//   displaying multiple times with a chosen interval can make for a nice
		//   animation.
		for i := 0; i < dispPerCollapse; i++ {
			textMap := world.MapToString(header, waveMapToContents(waveMap, rng))
			output.MoveCursor(0, 0)
			fmt.Print(textMap)
			time.Sleep(sleepPerDisp)
		}
	}
}

Yes, I did some work on making it animate nicely while it’s running. I use termenv to move the cursor without clearing the screen (which was too flickery), and lipgloss to embed ANSI bold/color codes in the tile graphics:

cmd/rstm/main.go GitLab
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
func waveMapToContents(waveMap WaveMapContents, rng *rand.Rand) world.MapContents {
	contents := world.MapContents{Cells: make(map[world.CellKey]world.Cell, len(waveMap.Cells))}
	minEntropy := minEntropy(waveMap)
	for key, cell := range waveMap.Cells {
		style := lipgloss.NewStyle()
		cellEntropy := calculateEntropy(cell)
		if cell.numPossibleTiles() != 1 { // cell not yet collapsed
			style = style.Bold(false).Foreground(lipgloss.Color("#6C6C6C"))
			if cellEntropy == minEntropy { // one of the cells with minimum entropy
				style = style.Background(lipgloss.Color("#F0F0F0"))
			}
			// choose a possible tile at random
			whichTile := rng.Intn(cell.numPossibleTiles())
			contents.Cells[key] = world.Cell{Graphic: style.Render(cell.possibleTiles()[whichTile])}
		} else { // collapsed cell
			style = style.Bold(true)
			contents.Cells[key] = world.Cell{Graphic: style.Render(cell.possibleTiles()[0])}
		}
	}
	return contents
}

I’m only scratching the surface of lipgloss here, but I do like how it turned out:

RSTM1 sample

That is quite a lot of stairs, though.

A Literal Edge Case

In this application, where we’re taking a source map and generating a (hopefully) similar new map, we should try for a similar edge treatment as well. Unfortunately what we have so far will easily place an open tile at the edge of the map, which is guaranteed to give the game server fits if a player or NPC goes there.

In the original map files, an unreachable cell is represented by two space characters (" "), so we’ll just use that as a special “null” tile. While compiling the rules, just default to that as the neighbor’s tile; so if we don’t find one of the neighbors, we’ll include the rule which identifies the edge tile.

cmd/rstm/main.go GitLab
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
func deriveRuleSet2(cells map[world.CellKey]world.Cell) []NeighborRule {
	neighborRules := make(map[NeighborRule]bool)

	for cellKey, cell := range cells {
		for relX := -1; relX <= 1; relX++ {
			for relY := -1; relY <= 1; relY++ {
				if relX == 0 && relY == 0 {
					continue
				}
				neighborKey := world.CellKey{X: cellKey.X + relX, Y: cellKey.Y + relY, Z: cellKey.Z}
				neighborGraphic := "  " // default to null
				if neighbor, success := cells[neighborKey]; success {
					neighborGraphic = neighbor.Graphic
				}
				neighborRules[NeighborRule{
					homeGraphic:     cell.Graphic,
					neighborGraphic: neighborGraphic,
				}] = true
				neighborRules[NeighborRule{
					homeGraphic:     neighborGraphic,
					neighborGraphic: cell.Graphic,
				}] = true
			}
		}
	}
...

Out of the set of rules that are (" ", x), we can collect the xs and get a set of potential edge tiles; then we can clear anything else out of the edge cells' weights.

cmd/rstm/main.go GitLab
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
func edgeCandidates(rules []NeighborRule) []string {
	result := []string{}
	for _, rule := range rules {
		if rule.neighborGraphic == "  " {
			result = append(result, rule.homeGraphic)
		}
	}

	// make result deterministic by sorting it
	sort.SliceStable(result, func(i, j int) bool {
		return result[i] < result[j]
	})

	return result
}

func setEdges(waveMap *WaveMapContents, rules []NeighborRule) {
	edgePossibleTiles := edgeCandidates(rules)
	for cellKey, cell := range waveMap.Cells {
		if cell.numPossibleTiles() <= 1 {
			continue // Already collapsed
		}

		if hasMissingNeighbor(*waveMap, cellKey) {
			// Neighbor is missing or null tile, remove non-edge tiles
			newWeights := make(map[string]int)
			for _, tile := range edgePossibleTiles {
				newWeights[tile] = cell.weights[tile]
			}
			waveMap.Cells[cellKey] = SuperpositionCell{weights: newWeights}
		}
	}
}

Here’s what the process looks like now:

cmd/rstm/main.go GitLab
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
func rstm2(header world.MapHeader, contents world.MapContents, rng *rand.Rand) string {
	// Using termenv to move the cursor back to home without clearing the screen,
	//   for smoother animation.
	output := termenv.NewOutput(os.Stdout)

	// gather the tiles based on the source map; each weight will be 1 in this case.
	initialWeights := gatherTiles2(contents.Cells)

	// initialize the wave map, with all identical cells based on those weights.
	waveMap := createWaveMap2(contents, initialWeights)

	// Gather the rule set from the source map.
	ruleSet := deriveRuleSet2(contents.Cells)

	setEdges(&waveMap, ruleSet)

	// Settings for pretty display while running.
	dispPerCollapse := 2
	sleepPerDisp := 50 * time.Millisecond

	// Now collapse the map.
	collapseMap2(&waveMap, ruleSet, dispPerCollapse, header, output, sleepPerDisp, rng)

	// Convert the map to a string to return.
	return world.MapToString(header, waveMapToContents(waveMap, rng))
}

But there are two complications: First, because we process the null and edge cells differently, we can start out with multiple cells that are already collapsed. Second, the additional constraints cause dead-end collapses to cause more often. So we maintain a list of collapsed cells that we need to apply the rules to, and also a backup of the WaveMapContents to revert to in case we hit a dead end (detected as a cell with zero possible tiles).

cmd/rstm/main.go GitLab
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
func collapseMap2(waveMap *WaveMapContents, ruleSet []NeighborRule, dispPerCollapse int, header world.MapHeader,
	output *termenv.Output, sleepPerDisp time.Duration, rng *rand.Rand) {
	var newCollapsed []world.CellKey
	var err error

	bakWaveMap := &WaveMapContents{Cells: waveMap.Cells}
  copyWaveMap(bakWaveMap, waveMap)

	// Handle pre-collapsed tiles
  nowCollapsed := collapsedTiles(waveMap)

	// Loop until there are no cells with entropy.
	for maxEntropy(*waveMap) > 1 {
		if len(nowCollapsed) == 0 {
			// Gather the cells with minimum entropy and choose one.
			minEntropyCellList := minEntropyCells(*waveMap)
			randIndex := rng.Intn(len(minEntropyCellList))
			cellToCollapse := minEntropyCellList[randIndex]

			// Collapse the cell, add it to the list.
			collapseCell(*waveMap, cellToCollapse, rng)
			nowCollapsed = append(nowCollapsed, cellToCollapse)
		}

		for len(nowCollapsed) > 0 {
      // While we have collapsed cells that haven't been processed, pop one off of the queue and
      // apply the rules.
			currCollapsed := nowCollapsed[0]
			nowCollapsed = nowCollapsed[1:]
			newCollapsed, err = applyRules2(*waveMap, ruleSet, currCollapsed)
			if err != nil {
        // If we've hit an impossible map, restore from backup
        fmt.Println(err)
        copyWaveMap(waveMap, bakWaveMap)
        nowCollapsed = collapsedTiles(waveMap)
				continue
			}
      nowCollapsed = unionOfCellKeys(nowCollapsed, newCollapsed)
		}
...

Let’s see how well this works:

RSTM2 sample

Now we see way too much of the edge tiles. (BTW, /\ is solid rock, so makes sense for the edge in a lot of cases. [] is a wall, but usually one that can be destroyed.)


Weighted Random Again

Ok, let’s start paying attention to the tile frequency and see if that gives us a more reasonable map.

$ go run cmd/rstm/main.go --mapname Annwn --maplevel 2 --method rstm3 --seek-valid --seed 14

<z>-25</z> <x>38</x> <y>18</y> <n>Ruined Tavern Cellar</n>
/\/\/\/\/\/\/\/\/\/\/\/\/\
/\/\/\[][]/\[]/\[][][]/\/\
/\[][]/\[][][]/\/\/\[]/\/\
/\/\[][][]. [][][][][]/\/\
/\[]/\[]. . . [][][][]/\/\
/\[]/\[][]. [][][][]/\[]/\
/\[][][]dn. []/\[][]/\[]/\
/\[][][][][][][]/\[][]/\/\
/\/\/\/\/\/\/\/\/\/\/\/\/\

Interesting, but a little dense. Since most of the tiles in the original are solid, that’s to be expected. What if we make sure that every tile is represented?

RSTM3 neverending sample

Hmm, if we have to iterate through many attempts to get a valid map, we should spend some time making the process a bit faster…


Jareth pushing forward the clock

Much refactoring and optimizing occurs, along with a more formal command line…


Tile Shuffle With Radically Simple Rules

Ok, so now let’s make sure every tile in the original is represented in the new map. We count all of the original tiles to make the initial weights for non-edge tiles, so we’ll just keep those in a “typical cell” attached to the wave map.

cmd/rstm/main.go GitLab
32
33
34
35
36
37
type WaveMapContents struct {
  cellArray                 []*SuperpositionCell
  TypicalCell               *SuperpositionCell
  XOffset, YOffset, ZOffset int
  Xdim, Ydim, Zdim          int
}

Every time we collapse a cell, we decrement that tile’s weight in the TypicalCell; if that takes it down to zero, we remove that tile as an option from all of the non-collapsed cells.

cmd/rstm/main.go GitLab
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
func decreaseWeights(waveMap *WaveMapContents, collapsedCell world.CellKey) error {
	// fmt.Println("decreasing weight of", collapsedCell, waveMap.Cells[collapsedCell])
	tile := waveMap.getCell(collapsedCell.X, collapsedCell.Y, collapsedCell.Z).only()
	if waveMap.TypicalCell.decrementWeight(tile) {
		// Decrementing caused tile's removal, remove from all active cells
		xSize, ySize, zSize := waveMap.getDimensions()
		for x := 0; x < xSize; x++ {
			for y := 0; y < ySize; y++ {
				for z := 0; z < zSize; z++ {
					cell := waveMap.getCell(x, y, z)
					if cell == nil || cell.isCollapsed() {
						// the cell itself should already be collapsed, so this skips that too.
						continue
					}
					cell.zeroWeight(tile)
					if cell.numPossibleTiles() < 1 {
						cellKey := world.CellKey{X: x, Y: y, Z: z}
						return errors.New(fmt.Sprint("After decreasing weight of tile ", uint16ToString(tile), "(", tile, ") in cell ",
							cellKey, "has no possible tiles", cell))
					}
				}
			}
		}
	}

	return nil
}

Of course now we have two things that can invalidate a map: either a cell winds up with no options after we apply the rules, or it has no options after all of its potential tiles are used up elsewhere.

Annwn 2 - A few retries necessary.

We can resolve some maps with a few retries, but others are less cooperative.

Annwn 1 - Needs more than 10 retries.

I’ll be curious, as I implement less radically simple rules, to see if the maps are then actually quicker to collapse successfully. Tomorrow.


One More Thing

As I was trying to fuzz test these functions, eager to see the mutated maps that might bring out some bugs in my code, I ran into some unexpected and confusing failures.

=== RUN   Fuzz_rstm4
fuzz: elapsed: 0s, gathering baseline coverage: 0/172 completed
fuzz: elapsed: 3s, gathering baseline coverage: 31/172 completed
fuzz: elapsed: 6s, gathering baseline coverage: 34/172 completed
fuzz: elapsed: 9s, gathering baseline coverage: 34/172 completed
failure while testing seed corpus entry: Fuzz_rstm4/seed#10
fuzz: elapsed: 12s, gathering baseline coverage: 35/172 completed
fuzz: elapsed: 12s, gathering baseline coverage: 35/172 completed
Tests skipped: 0
--- FAIL: Fuzz_rstm4 (12.28s)
    fuzzing process hung or terminated unexpectedly: exit status 2
=== NAME
FAIL
exit status 1
FAIL    gitlab.com/301days/glitch-aura-djinn/cmd/rstm   12.288s

After some digging, it turns out the Go fuzzing tool has a hardcoded 10-second timeout for the fuzz target:

src/internal/fuzz/worker.go GitHub
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
func RunFuzzWorker(ctx context.Context, fn func(CorpusEntry) error) error {
	comm, err := getWorkerComm()
	if err != nil {
		return err
	}
	srv := &workerServer{
		workerComm: comm,
		fuzzFn: func(e CorpusEntry) (time.Duration, error) {
			timer := time.AfterFunc(10*time.Second, func() {
				panic("deadlocked!") // this error message won't be printed
			})
			defer timer.Stop()
			start := time.Now()
			err := fn(e)
			return time.Since(start), err
		},
		m: newMutator(),
	}
	return srv.serve(ctx)
}

Fuzzing small, quick targets makes sense to hit many potential inputs within a limited time; but I think there’s some value in fuzzing larger (slower) systems as well. Given that one of the things to catch with your fuzzing is inputs that slow or deadlock the target, there’re two options: more configuration of timeouts (which assumes the developer has a good understanding of reasonable times), or some analysis to identify outliers and flag them as potential(?) problems.


More to come

gitch-aura-djinn New Day 11 Code