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:
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.
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.
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).
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.
funcrstm1(headerworld.MapHeader,contentsworld.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:=2sleepPerDisp:=10*time.Millisecond// Now collapse the map.
collapseMap(waveMap,ruleSet,dispPerCollapse,header,output,sleepPerDisp,rng)// Convert the map to a string to return.
returnworld.MapToString(header,waveMapToContents(waveMap,rng))}
funccollapseMap(waveMapWaveMapContents,ruleSet[]NeighborRule,dispPerCollapseint,headerworld.MapHeader,output*termenv.Output,sleepPerDisptime.Duration,rng*rand.Rand){// Loop until there are no cells with entropy.
formaxEntropy(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.
fori:=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:
funcwaveMapToContents(waveMapWaveMapContents,rng*rand.Rand)world.MapContents{contents:=world.MapContents{Cells:make(map[world.CellKey]world.Cell,len(waveMap.Cells))}minEntropy:=minEntropy(waveMap)forkey,cell:=rangewaveMap.Cells{style:=lipgloss.NewStyle()cellEntropy:=calculateEntropy(cell)ifcell.numPossibleTiles()!=1{// cell not yet collapsed
style=style.Bold(false).Foreground(lipgloss.Color("#6C6C6C"))ifcellEntropy==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])}}}returncontents}
I’m only scratching the surface of lipgloss here, but I do like how it turned out:
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.
funcderiveRuleSet2(cellsmap[world.CellKey]world.Cell)[]NeighborRule{neighborRules:=make(map[NeighborRule]bool)forcellKey,cell:=rangecells{forrelX:=-1;relX<=1;relX++{forrelY:=-1;relY<=1;relY++{ifrelX==0&&relY==0{continue}neighborKey:=world.CellKey{X:cellKey.X+relX,Y:cellKey.Y+relY,Z:cellKey.Z}neighborGraphic:=" "// default to null
ifneighbor,success:=cells[neighborKey];success{neighborGraphic=neighbor.Graphic}neighborRules[NeighborRule{homeGraphic:cell.Graphic,neighborGraphic:neighborGraphic,}]=trueneighborRules[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.
funcedgeCandidates(rules[]NeighborRule)[]string{result:=[]string{}for_,rule:=rangerules{ifrule.neighborGraphic==" "{result=append(result,rule.homeGraphic)}}// make result deterministic by sorting it
sort.SliceStable(result,func(i,jint)bool{returnresult[i]<result[j]})returnresult}funcsetEdges(waveMap*WaveMapContents,rules[]NeighborRule){edgePossibleTiles:=edgeCandidates(rules)forcellKey,cell:=rangewaveMap.Cells{ifcell.numPossibleTiles()<=1{continue// Already collapsed
}ifhasMissingNeighbor(*waveMap,cellKey){// Neighbor is missing or null tile, remove non-edge tiles
newWeights:=make(map[string]int)for_,tile:=rangeedgePossibleTiles{newWeights[tile]=cell.weights[tile]}waveMap.Cells[cellKey]=SuperpositionCell{weights:newWeights}}}}
funcrstm2(headerworld.MapHeader,contentsworld.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:=2sleepPerDisp:=50*time.Millisecond// Now collapse the map.
collapseMap2(&waveMap,ruleSet,dispPerCollapse,header,output,sleepPerDisp,rng)// Convert the map to a string to return.
returnworld.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).
funccollapseMap2(waveMap*WaveMapContents,ruleSet[]NeighborRule,dispPerCollapseint,headerworld.MapHeader,output*termenv.Output,sleepPerDisptime.Duration,rng*rand.Rand){varnewCollapsed[]world.CellKeyvarerrerrorbakWaveMap:=&WaveMapContents{Cells:waveMap.Cells}copyWaveMap(bakWaveMap,waveMap)// Handle pre-collapsed tiles
nowCollapsed:=collapsedTiles(waveMap)// Loop until there are no cells with entropy.
formaxEntropy(*waveMap)>1{iflen(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)}forlen(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)iferr!=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.)
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…
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.
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.
funcdecreaseWeights(waveMap*WaveMapContents,collapsedCellworld.CellKey)error{// fmt.Println("decreasing weight of", collapsedCell, waveMap.Cells[collapsedCell])
tile:=waveMap.getCell(collapsedCell.X,collapsedCell.Y,collapsedCell.Z).only()ifwaveMap.TypicalCell.decrementWeight(tile){// Decrementing caused tile's removal, remove from all active cells
xSize,ySize,zSize:=waveMap.getDimensions()forx:=0;x<xSize;x++{fory:=0;y<ySize;y++{forz:=0;z<zSize;z++{cell:=waveMap.getCell(x,y,z)ifcell==nil||cell.isCollapsed(){// the cell itself should already be collapsed, so this skips that too.
continue}cell.zeroWeight(tile)ifcell.numPossibleTiles()<1{cellKey:=world.CellKey{X:x,Y:y,Z:z}returnerrors.New(fmt.Sprint("After decreasing weight of tile ",uint16ToString(tile),"(",tile,") in cell ",cellKey,"has no possible tiles",cell))}}}}}returnnil}
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.
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.
funcRunFuzzWorker(ctxcontext.Context,fnfunc(CorpusEntry)error)error{comm,err:=getWorkerComm()iferr!=nil{returnerr}srv:=&workerServer{workerComm:comm,fuzzFn:func(eCorpusEntry)(time.Duration,error){timer:=time.AfterFunc(10*time.Second,func(){panic("deadlocked!")// this error message won't be printed
})defertimer.Stop()start:=time.Now()err:=fn(e)returntime.Since(start),err},m:newMutator(),}returnsrv.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.
