In which we continue to play with something like wave function collapse.

But First…

#

Package Up that WFC-ish Code

#

Now the WFC-ish code gets to go into a package, oddly enough, called wfcish. The interface will likely be awkward at first, as the front end calls functions like wfcish.RSTM() with all of the function parameters to define the variant.

🐟 ➜ tree --gitignore
.
├── check_maps.sh
├── cmd
│   ├── estm
│   │   ├── main.go
│   │   └── main_test.go
│   ├── mapeater
│   │   ├── main.go
│   │   └── main_test.go
│   ├── randotiles
│   │   ├── main.go
│   │   └── main_test.go
│   └── rstm
│       ├── main.go
│       └── main_test.go
...
├── pkg
│   ├── wfcish
│   │   ├── wfcish.go
│   │   └── wfcish_test.go
│   └── world
│       ├── world.go
│       └── world_test.go
...
├── testdata
│   └── maps
│       ├── Annwn.txt
│       ├── Axe Glacier.txt
│       ├── Eridu.txt
│       ├── Hell.txt
...

Slightly Less Radically Simple

#

In order to move from the Radically Simple Tiled Model to something akin to Heaton’s Even Simpler Tiled Model, we need to add directionality to our rules.

18
19
20
21
22
23
24
25
26
27

type Offset struct {
  X, Y int
}

// Allowed neighbor rule
type NeighborRule struct {
  HomeGraphic     string
  NeighborGraphic string
  Offsets         []Offset
}

Instead of using directions like up/down or north/south, and then translating those into offsets, we can directly add a list of offsets to each rule instead.

Let’s see how well this works. For consistency, we’ll go through the same sequence we did with the radically simple model.

First, ignoring the edges and tile frequency:

Still awfully wall-heavy, and again with breakable walls ([]) on the edge of the world (not a good idea). Let’s pay attention to the edges now:

Unbreakable edges now (/\), but still filled in. Now we take into account the frequency of the original tiles:

..but that doesn’t seem to get us anything on a small map where walls are the most common thing. So let’s guarantee the same number of each tile:

But we can collapse eventually, especially if we cheat and pick a random seed we’ve already seen work:

Does that look better than what we had with the Radically Simply Tiled Model?

Annwn level 2
RSTM4:                        ESTM4:
/\/\/\/\/\/\/\/\/\/\/\/\/\    /\/\/\/\/\/\/\/\/\/\/\/\/\
/\[][][][][][][][][][][]/\    /\[][][][][][][][][][][]/\
/\[][]. []up[]. [][]--[]/\    /\[][]. up[][]dn. . . []/\
/\[]| . . . . . []. . []/\    /\[][]--[][][]. . . . []/\
/\[][][][]. . [_. dn. []/\    /\[][]. . . . . . . . []/\
/\[]. . []. []. . []. []/\    /\[][][_[][]. [][]. . []/\
/\[]. []. []. . . . . []/\    /\[][]. . . . . | . . []/\
/\[][][][][][][][][][][]/\    /\[][][][][][][][][][][]/\
/\/\/\/\/\/\/\/\/\/\/\/\/\    /\/\/\/\/\/\/\/\/\/\/\/\/\

A little more reasonable, on this map. What about something a little more involved?

Annwn level 1
RSTM4:                                       ESTM4:
                    /\/\/\                                      /\/\/\
        /\/\/\/\/\  /\. /\                          /\/\/\/\/\  /\/\/\
        /\. . --/\/\/\/\/\/\/\                      /\. /\. /\/\/\/\/\/\/\
      /\/\/\/\/\/\. . . . . /\/\/\                /\/\CC/\--/\/\/\. . /\/\/\/\
      /\CC. /\| /\. | /\. /\/\. /\                /\/\{}. . /\/\. . . . /\/\/\
      /\. /\/\/\/\/\. . --. /\. /\/\/\/\          /\o . /\--/\. /\. . /\~~/\/\/\/\/\
      /\. /\. ::/\. . . . . /\. . /\/\/\/\        /\::MM/\. . . /\. /\/\/\/\{}. /\/\/\
      /\. /\. . /\. /\. BR. . /\/\pb. . /\        /\. /\/\/\. /\. . /\. /\. . /\. . /\
      /\~~. --/\. /\. . . . /\/\/\. . . /\        /\/\. /\/\. . . /\. /\/\/\/\. . . /\
/\/\/\/\. /\/\. . . --. /\. . /\. /\. --/\  /\/\/\/\/\. . . /\. . . /\/\/\/\. /\. ~~/\
/\{}/\/\. /\. MM. /\/\MM/\. . . CC/\. /\/\  /\. /\/\. . /\. ~~. . . . /\/\/\/\. . . /\
/\/\/\~~~~. --/\/\/\/\/\. /\. /\/\. . . /\  /\. . . /\. . . . . . . /\/\. /\/\/\. . /\
/\. . /\/\. /\/\o . . CC. --. /\. /\. /\/\  /\/\. . /\. . . . . . . /\/\. . . /\. . /\
/\. /\::. . /\/\. /\. /\. . /\/\. . . . /\  /\/\. . . . . . /\. . . /\. . /\/\/\/\. /\
/\/\/\. /\::/\/\/\. o . . /\::/\. . . /\/\  /\/\/\. . . . /\/\. ~~/\. . . /\/\/\/\/\/\
    /\/\/\. /\. ~~. /\. /\. . . /\==/\/\/\      /\. . . /\/\. . . /\::==--/\/\. /\/\/\
    /\{}/\. /\/\/\. . . /\. . . . . /\          /\. . . /\/\----CCo o . . /\. /\/\
    /\/\/\. /\{}/\~~~~. . . . /\. . /\          /\/\/\. /\/\--LK| VDpbCC{}. /\. /\
      /\/\/\/\/\/\. . . /\CC. /\. /\/\            /\/\/\. /\--| --==--CC/\. /\MM/\
    /\/\. MM/\. . . . . . . . . /\/\/\          /\/\/\/\. . | BR. . . MR/\. . . /\
    /\/\/\/\/\/\. CC. . . /\. . /\{}/\/\        /\. /\/\::--~~CCCC/\. . /\. /\. /\/\
    /\/\/\--. /\/\/\. . MR. . . /\/\/\/\        /\MM/\/\. . . {}::/\. . . /\. /\/\/\
    /\{}/\/\/\. . . --. . . /\| . /\LK/\        /\. /\/\. . . . . /\/\. /\. /\/\. /\
    /\/\/\o . /\/\. . /\==. . /\/\/\/\/\        /\/\. . /\. . . /\. /\. /\/\. /\/\/\
    /\CC/\/\. --. . VD/\. /\. /\/\/\/\          /\. /\~~{}. /\/\/\. /\/\/\/\/\/\/\
    /\/\/\/\/\/\/\/\/\/\/\/\/\/\                /\/\/\/\/\/\/\/\/\/\/\/\/\/\

A little more consistent, perhaps. Can we do better by looking further?

Whither STM?

#

After the Even Simpler, should we tackle the Simpler? Well, this tile set doesn’t really have orientation, except for doors. So adding orientation doesn’t give us much.

eXtended Simple Tiled Model

#

Let’s try extending the constraints beyond the immediate neighbors. This seems like a happy medium between the tiled model and the bitmap model of wave function collapse, and of course gives us yet another parameter to tweak.

So first we tweak the rule derivation code (good thing we were handling offsets instead of cardinal/ordinal directions):

662
663
664
665
666
667
668
669
670
671
672
673
674
675
676

func DeriveRuleSetExtended(cells map[world.CellKey]world.Cell, distance int, ignoreNulls bool) []NeighborRule {
  neighborRules := make([]NeighborRule, 0, len(cells)*8*distance+1)

  // Initially build up a big list of neighbor rules, ignoring duplication.
  for cellKey, cell := range cells {
    if ignoreNulls && cell.Graphic == "  " {
      continue
    }
    for relX := -distance; relX <= distance; relX++ {
      for relY := -distance; relY <= distance; relY++ {
        if relX == 0 && relY == 0 {
          continue
        }
        neighborKey := world.CellKey{X: cellKey.X + relX, Y: cellKey.Y + relY, Z: cellKey.Z}
...

Then do something very similar for enforcing the edge and rule constraints.

820

func SetEdgesExtended(waveMap *WaveMapContents, rules []NeighborRule, distance int) {

1308

func ApplyRulesExtended(waveMap *WaveMapContents, ruleSet []NeighborRule, cellKey world.CellKey, distance int) error {

Wire through the appropriate glue, cut-and-paste a lot, and we’re ready to try it out. My goodness, we have a lot of command-line parameters now.

21
22
23
24
25
26
27
28
29
30
31
32
33
34

  cliMapname          = flag.String("mapname", "", "name of source map")
  cliMaplevel         = flag.Int("maplevel", 0, "which source map level to read")
  cliMethod           = flag.String("method", "xstm4", "which method to use")
  cliNeighborDistance = flag.Int("neighbor-distance", 1, "how far to consider neighbors")
  cliMaxRetries       = flag.Int("max-retries", 1, "max times to retry a collapse")
  cliFPC              = flag.Uint("frames-per-collapse", 0, "frames per collapse")
  cliTPF              = flag.Duration("time-per-frame", time.Millisecond, "time per frame in ms")
  cliStyled           = flag.Bool("styled", false, "use styled output")
  cliSeed             = flag.Int64("seed", 0, "random seed to use")
  cliMaxSeed          = flag.Int64("max-seed", 0, "maximum random seed to use (when -match-original is set)")
  cliSeekOriginal     = flag.Bool("seek-original", false, "increment seed until output matches original map")
  cliSeekValid        = flag.Bool("seek-valid", false, "increment seed until output is valid")
  cpuprofile          = flag.String("cpuprofile", "", "write cpu profile to `file`")
  memprofile          = flag.String("memprofile", "", "write memory profile to `file`")

But Does It Help?

#

Lets compare considering a single neighbor to considering more.

First, ignoring edges and weights:

Huh, not much to see. Let’s consider the edges while looking at neighbors of neighbors:

Unimpressive. Now if we weight the randomness by tile frequency as well:

Same. As usual, I’m really interested in the case where we strictly maintain the tile frequency.

With a neighbor distance of 1, 2, or 3; we have a lot of trouble collapsing the map successfully:

With a distance of 4, we do get a valid map pretty quickly; and with 5, even more quickly.

But wait, that looks familiar.

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

Oh, we’re just getting exact copies of the original map. I guess that’s to be expected, given the small size of this particular map.

Maybe it works better on larger maps?

That looks nice, but doesn’t collapse the map successfully. There must be at least one set of random decisions that work, because the original map must be achievable (assuming I have a correct implementation); but it doesn’t come up in the first half million seeds.

The big spoiler, as the algorithm works in from the edges, is the existance of tiles that only show up one or a few times. They’re late to be chosen by being unpopular, and also have the most restrictive rules. We’ll have to figure out something to do about that. Tomorrow.

One More Thing

#

As we add more considerations to the algorithm, it unsurprisingly gets slower and slower. Luckily the Go toolset has a lot of included functionality for benchmarking and profiling, so it’s clear where the system is spending its time.

It’s particularly enlightening to see when a lot of time is being used by “checking” functions, like in this case NeighborRules.hasOffset(). Are we using the right data structure? Do we need to cache the results of an inefficient lookup/calculation?

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

type Offset struct {
  X, Y int
}

// Allowed neighbor rule
type NeighborRule struct {
  HomeGraphic     string
  NeighborGraphic string
  Offsets         []Offset
}

func (r *NeighborRule) hasOffset(offset Offset) bool {
  for _, rOffset := range r.Offsets {
    if rOffset.X == offset.X && rOffset.Y == offset.Y {
      return true
    }
  }
  return false
}

Well, that’s not great. Checking for membership that often, only a hash set will do.

23
24
25
26
27
28
29
30
31

type NeighborRule struct {
  HomeGraphic     string
  NeighborGraphic string
  Offsets         map[Offset]bool
}

func (r *NeighborRule) hasOffset(offset Offset) bool {
  return r.Offsets[offset]
}

Ok, that was easy. And makes me wonder if we need all those calls to StringToUint16. We convert the tile strings from the mapfile into uint16 for easier usage (given that the tiles are all two eight-bit ASCII characters), and should really only be doing that in IO sections.

1312
1313
1314
1315
1316
1317
1318
1319
1320
1321

        // Collect the tiles that are allowed for this neighbor
        okTiles := make([]uint16, 0, 100)
        for _, rule := range ruleSet {
          if cellTile != world.StringToUint16(rule.HomeGraphic) {
            continue
          }
          if rule.hasOffset(Offset{X: relX, Y: relY}) {
            okTiles = append(okTiles, world.StringToUint16(rule.NeighborGraphic))
          }
        }

Let’s stop using strings in the rules, and instead convert those over to uint16…

Pruning any surprises out of the hierarchy is certainly useful, but it won’t necessarily lead you to:

1. Matching the data structures more closely to the pattern of usage. In this case, enforcing the rules considers: one tile -> many offsets -> many potential tiles. Matching this one->many->many relationship in our data structure would be optimal.

2. Reasonable concurrency. The big glaring non-Go-like aspect of this code is that it’s purely linear, with no concurrency at all (except for the garbage collector, I suppose). Performing the expensive operations concurrently will most likely be the biggest performance boost we can do (at least on typical modern hardware).

gitch-aura-djinn New Day 12 Code