Wondering Witches (Part 5)
Welcome to part 5 of my Technical Devlog for the game Wondering Witches!
Haven’t read the other entries? Go to the devlog overview.
Generating a “fair” Board
As I said before, this part took me the most time. I will only describe the code I ended up using, as describing numerous failed attempts doesn’t seem too interesting. But don’t let that fool you – it took me a long while to get here.
Splitting the board into sections
First of all, I wanted to give each player their own little part of the board. Their own garden to tend. If needed, you could cut the board into pieces so people wouldn’t need to huddle around a small piece of paper, but could mostly focus on what’s in front of them.
For this I just used a fixed distribution. With X players, the board is always split into the same shapes.
(Of course, I could have tried to make it dynamic, but what’s the point? It would only add unneeded complexity, whilst players don’t really care about how their pieces of the board are distributed on the original piece of paper.)
I saved this in the code as an array of rectangles: each shape had a start point (x,y) and a size (width, height).
1// divide the paper into rectangles based on player count
2var paperSectionsLibrary = {
3 'players-1': [[0,0,8,4]],
4 'players-2': [[0,0,4,4], [4,0,4,4]],
5 'players-3': [[0,0,5,2], [0,2,5,2], [5,0,3,4]],
6 'default': [[0,0,4,2], [4,0,4,2], [0,2,4,2], [4,2,4,2]],
7 'players-5': [[0,0,3,2], [3,0,3,2], [0,2,3,2], [3,2,3,2], [6,0,2,4]],
8}
9
10// grab the right setup if it exists, otherwise go to the default setup (which is used in most cases)
11var tempSectionKey = 'players-' + this.playerCount;
12this.paperSections = [];
13if(typeof(paperSectionsLibrary[tempSectionKey]) == 'undefined') {
14 this.paperSections = paperSectionsLibrary['default'];
15} else {
16 this.paperSections = paperSectionsLibrary[tempSectionKey];
17}
18
19// Create array of players + their own sections
20var playerArray = [];
21this.sections = [];
22for(var i = 0; i < this.paperSections.length; i++) {
23 playerArray[i] = i;
24 var s = this.paperSections[i];
25
26 this.sections[i] = [];
27 this.sections[i][0] = {
28 'rect': s,
29 'fullRect': new Phaser.Geom.Rectangle(s[0]*this.rectWidth, s[1]*this.rectHeight, s[2]*this.rectWidth, s[3]*this.rectHeight),
30 'cauldrons': [],
31 'spaceLeft': s[2]*s[3],
32 }
33
34 this.sections[i][1] = {
35 'rect': [(this.xLines - s[0] - s[2]), s[1], s[2], s[3]],
36 'fullRect': new Phaser.Geom.Rectangle((this.xLines - s[0] - s[2])*this.rectWidth, s[1]*this.rectHeight, s[2]*this.rectWidth, s[3]*this.rectHeight),
37 'cauldrons': [],
38 'spaceLeft': s[2]*s[3],
39 }
40}Creating a Cauldron distribution
The “naïve” way to distribute cauldrons, would be something like this:
Keep a counter of how many cauldron cells have been filled. (For example, “cauldronCellsLeft = 32”)
Start a loop.
Each iteration, try to fit a cauldron of random size on the paper.
Keep doing this until your counter has surpassed the maximum (“cauldronCellsLeft <= 0”)
This was the very first implementation when I just needed something to test. But what are the problems?
No guarantees on cauldron size. (If unlucky, you could end up with tons of minuscule cauldrons, or only three very big ones.)
Unsolvable games. If your recipe needs a cauldron of at least size 6, there must be at least one of those on the board.
Unfair distribution. Some players might get all the cauldrons (and no garden), and vice versa for the rest.
How to solve this? Using a technique very common to random generation: fixing the distribution up front.
Before trying to fit cauldrons, I fix a distribution, like this:
Create an empty list (an array in this case).
I want at least one cauldron of size X and one of size Y (to make levels solvable). Add these to the array.
Then, repeatedly add a new cauldron to the array of random size, until we’ve reached our exact fill percentage.
Finally, sort this array from largest to smallest.
The code looks like this:
1// Determine a cauldron distribution
2// Requirements:
3// * 32 cauldron cells in total
4// * Each player has at least one cauldron
5// * There must be one cauldron of length "codeLength"
6var maxCauldron = [3,2];
7if(!this.variableRecipe) { maxCauldron = [2,2]; }
8
9var totalCauldronCells = 32 - maxCauldron[0]*maxCauldron[1];
10this.cauldronDistribution = [maxCauldron];
11while(totalCauldronCells > 0) {
12 var tempSizeX = Math.floor(Math.random()*3)+1;
13 var tempSizeY = Math.floor(Math.random()*3)+1;
14
15 // prevent cauldrons greater than our budget allows
16 // (scale down to an approximately correct number)
17 if(tempSizeX*tempSizeY > totalCauldronCells) {
18 tempSizeX = totalCauldronCells;
19 tempSizeY = Math.round(totalCauldronCells*0.5);
20 }
21
22 // prevent cauldrons of 1 (or less)
23 if(tempSizeX*tempSizeY <= 1) {
24 tempSizeX = 2;
25 tempSizeY = 1;
26 }
27
28 // prevent cauldrons greater than 6
29 if(tempSizeX*tempSizeY > 6) {
30 tempSizeX = 3;
31 tempSizeY = 2;
32 }
33
34 // subtract from total
35 totalCauldronCells -= tempSizeX*tempSizeY;
36
37 // add to distribution
38 this.cauldronDistribution.push([tempSizeX, tempSizeY]);
39}
40
41// Sort the distribution descending (so we place the largest cauldrons first)
42this.cauldronDistribution.sort(function(a, b){ return b[0]*b[1] - a[0]*a[1] });When this process is done, we have a list with the exact cauldrons we want to place. If we manage to place all of them, we are certain the distribution is correct. (And if we start at the biggest cauldrons, the probability we’ll be able to place them all increases. Because smaller cauldrons are easier to fit at the end.)
Trying to fit cauldrons
Now that we have a distribution, we go back to being naïve again. This code is inside a loop that runs until all cauldrons have been placed:
For each player …
Choose a random side (front/back of the board)
Go through the list of cauldrons and find the largest cauldron that fits.
Rule #1: Obviously the cauldron cannot be larger than the available area.
Rule #2: If the total area for this player (front and back) combined has no space left (after placing the cauldron), do NOT place it! Why? Because this would leave a player with only cauldrons and NO gardens, which is unfair.
Place it.
Remember we placed it (discard/disable all cells we occupy and subtract from total)
There is a small chance this goes wrong. For whatever reason, everything doesn’t work out, we place gardens and special tiles at annoying locations, and we cannot place all the cauldrons.
In that case … I simply discard all progress and try again :p Sometimes solutions are quite simple.
1// go through all extra cells
2while(emptySpaces > 0) {
3 // find a random place (that still exists)
4 var gardenX, gardenY;
5 do {
6 gardenX = Math.floor(Math.random()*maxSizeX);
7 gardenY = Math.floor(Math.random()*maxSizeY);
8 } while(!section[gardenX][gardenY]);
9
10 // NOTE: section is the 2D array created earlier that is exactly the size of each player's own board
11
12 // start a garden here
13 var newGarden = [ [gardenX + x0, gardenY + y0] ];
14 section[gardenX][gardenY] = false;
15
16 // now we simply go through neighbours (again and again) until we decide to stop (we're large enough) or we must stop (nothing to explore anymore)
17 var cellsToCheck = [ [gardenX, gardenY] ];
18
19 // check the neighbours (in a random order)
20 var terminateLoop = false;
21 while(!terminateLoop) {
22 // grab the first cell on the list
23 var c = cellsToCheck.splice(0,1)[0];
24
25 emptySpaces--;
26
27 // check all the neighbours (in a random order)
28 var dirs = [[1,0], [0,1], [-1,0], [0,-1]];
29 dirs = shuffle(dirs);
30 for(var d = 0; d < 4; d++) {
31 var tempX = c[0] + dirs[d][0], tempY = c[1] + dirs[d][1];
32
33 // if out of bounds, ignore
34 if(tempX < 0 || tempX >= maxSizeX || tempY < 0 || tempY >= maxSizeY) { continue; }
35
36 // if non-existent, ignore
37 if(!section[tempX][tempY]) { continue; }
38
39 // now check probability: the larger we get, the less likely we are to grow
40 var probCutoff = 1.0 / (0.5*newGarden.length);
41 if(Math.random() > probCutoff) { continue; }
42
43 //
44 // we will grow!
45 //
46
47 // add this cell to the garden
48 newGarden.push([tempX + x0, tempY + y0]);
49
50 // and plan a check (for potentially growing further)
51 cellsToCheck.push([tempX, tempY]);
52
53 // and remember we lost a space
54 section[tempX][tempY] = false;
55 }
56
57 // terminate if there's nothing more to check
58 terminateLoop = (cellsToCheck.length <= 0);
59 }
60
61 // add the final garden to the list
62 this.gardens.push(newGarden);
63}Filling with gardens
So, at this moment we have a board filled with cauldrons, exactly 50% of it in fact.
We need to fill the gaps with gardens. It looks nicer, and is better for gameplay, if gardens have organic shapes, so we don’t want to fill the gaps completely with one garden every time.
For this, I took another simple “growing” solution:
Keep a list of all “empty” cells in a section. (When placing the cauldrons, I already update this list.)
Choose a random empty cell.
Check its neighbours. If any of them is available (not a cauldron, not out of bounds), grow the garden to include that cell with probability p.
What’s p? It’s a probability that gets smaller as the garden grows larger. This organically restricts garden size. The specific number in the current code is: 2.0/gardenSize. So, a garden of size 4, has a probability of growing further that’s equal to 2.0/4 = 50%
After growing, we have a set of gardens, which is just an array of all the cells it includes. This is immediately fed into the algorithm explained earlier, to determine the bounds of the garden and draw the right lines.
1// go through all extra cells
2while(emptySpaces > 0) {
3 // find a random place (that still exists)
4 var gardenX, gardenY;
5 do {
6 gardenX = Math.floor(Math.random()*maxSizeX);
7 gardenY = Math.floor(Math.random()*maxSizeY);
8 } while(!section[gardenX][gardenY]);
9
10 // NOTE: section is the 2D array created earlier that is exactly the size of each player's own board
11
12 // start a garden here
13 var newGarden = [ [gardenX + x0, gardenY + y0] ];
14 section[gardenX][gardenY] = false;
15
16 // now we simply go through neighbours (again and again) until we decide to stop (we're large enough) or we must stop (nothing to explore anymore)
17 var cellsToCheck = [ [gardenX, gardenY] ];
18
19 // check the neighbours (in a random order)
20 var terminateLoop = false;
21 while(!terminateLoop) {
22 // grab the first cell on the list
23 var c = cellsToCheck.splice(0,1)[0];
24
25 emptySpaces--;
26
27 // check all the neighbours (in a random order)
28 var dirs = [[1,0], [0,1], [-1,0], [0,-1]];
29 dirs = shuffle(dirs);
30 for(var d = 0; d < 4; d++) {
31 var tempX = c[0] + dirs[d][0], tempY = c[1] + dirs[d][1];
32
33 // if out of bounds, ignore
34 if(tempX < 0 || tempX >= maxSizeX || tempY < 0 || tempY >= maxSizeY) { continue; }
35
36 // if non-existent, ignore
37 if(!section[tempX][tempY]) { continue; }
38
39 // now check probability: the larger we get, the less likely we are to grow
40 var probCutoff = 1.0 / (0.5*newGarden.length);
41 if(Math.random() > probCutoff) { continue; }
42
43 //
44 // we will grow!
45 //
46
47 // add this cell to the garden
48 newGarden.push([tempX + x0, tempY + y0]);
49
50 // and plan a check (for potentially growing further)
51 cellsToCheck.push([tempX, tempY]);
52
53 // and remember we lost a space
54 section[tempX][tempY] = false;
55 }
56
57 // terminate if there's nothing more to check
58 terminateLoop = (cellsToCheck.length <= 0);
59 }
60
61 // add the final garden to the list
62 this.gardens.push(newGarden);
63}Conclusion
Wow, that was a long technical devlog. I think I actually explained (and provided code for) literally every part of the whole program.
Hopefully, it was interesting and you learned a lot from it!
If something was unclear, or you want to know more, or this inspired you for your own projects – let me know!
I’ve never seen this kind of hybrid between board and computer games before, especially not one where you can play using a single sheet of (blank) paper, so I wanted to share this knowledge and perhaps inspire others.
It took me quite a while to figure this stuff out, but now that it’s working, I find this concept to be really fun and easy to understand for everyone.
So that’s why I wrote this thorough explanation.
And as always, consider trying out the game at: Wondering Witches
Until the next devlog,
Pandaqi