Unstable Universe (Part 3)
Welcome to part 3 of the technical devlog.
Haven’t read the other entries? Go to the devlog overview.
Expansions: Creating a better Node List
There are three expansions for this game that (mostly) add more nodes. My experience from previous games tells me that I can’t simply allow such a huge list, because then each type would only appear 1 or 2 times on the board. This makes games extremely random and unbalanced, whilst making it more complex: each player needs to remember how 20+ unique nodes work!
I, therefore, took the following approach.
Each node has a Category (like “Nature”) and one or more Action Types (like “Cutting” or “Moving”). I do this for all games now, because it allows me to easily balance all parts of the game, while keeping them varied.
If you look at the expansions, you’ll see that they ALWAYS contain each Category and each Action Type at least once. The “Cutting” action is contained at least three times, because it’s such a vital action.
No matter what expansion you pick, no matter which game you play, you will always have a set of nodes that contains all possible actions and categories this game has to offer.
Once I have this system, I can use it when generating the board:
Initialize an empty list.
Pick one random node from each Category, and add it.
Pick one random node for each Action Type, and add it.
Fill the remaining space with random nodes (that aren’t already in the list).
What’s the remaining space? Well, I know the number of nodes on the board (usually around 80). I also gave each node a “min” and “max” value, remember? Whilst adding nodes, I sum the average ( (min+max)/2 ), until it goes above the total number of nodes. That’s when I know that there are enough nodes to fill the board, but not too many.
What if a node requires other nodes to function? Yeah, that’s a big problem I encountered for the first time in the last game I made. Luckily, I had time to come up with much simpler (and better) solutions for this particular game.
For example: the Critters node requires you to collect Stardust. Adding one node without the other is literally useless, as they both do nothing. So, each node has a requirements setting that holds a list of required nodes.
When such a node is added, it automatically loops through its “requirements” list, and adds those as well (if they aren’t already in the list).
This means we can sometimes “overshoot” the maximum, but that’s not a big deal. It just means one node type will have one or two fewer nodes on the board than would be ideal.
But, won’t this add many duplicate nodes? For example, if a node has Category X and Action Type Y, it would be added twice (both in step 2 and step 3)! Of course, that was the last problem that needed solving.
At the start, I have two lists containing all possibilities (all categories and all actionTypes).
Whenever I add a node, I check if its Category is still in the list of categories. If so, I remove it. The same thing is done for Action Types.
This means that, when I add such a node with Category X and Action Type Y, both these elements are removed from their respective list, so they won’t be encountered any more in steps 2 and 3.
Hopefully the code clarifies any issues with this explanation:
1function createBetterNodeCollection() {
2 var tempNodes = {}, name = '', curNodeData = { sum: 0, categories: [], actionTypes: [] };
3
4 // Step 1) For each category and action type, add ONE random node to the selection
5 curNodeData.categories = [/* list of all the categories as strings */];
6 curNodeData.actionTypes = [/* list of all the action types as strings */]
7
8 while(curNodeData.categories.length > 0) {
9 name = this.getRandomNodeOfType('category', curNodeData.categories[0], tempNodes, NODE_RNG);
10 this.addNodeToCollection(tempNodes, name, curNodeData)
11 }
12
13 while(curNodeData.actionTypes.length > 0) {
14 name = this.getRandomNodeOfType('actionType', curNodeData.actionTypes[0], tempNodes);
15 this.addNodeToCollection(tempNodes, name, curNodeData)
16 }
17
18 // Step 2) Count how many "cutting nodes" we have => we want at least 3
19 var cuttingNodesInSet = 0, minCuttingNodes = 3;
20 for(var name in tempNodes) {
21 if(tempNodes[name].actionTypes.includes("Cutting")) {
22 cuttingNodesInSet++;
23 }
24 }
25
26 while(cuttingNodesInSet < minCuttingNodes) {
27 name = this.getRandomNodeOfType('actionType', 'Cutting', tempNodes);
28 if(name == null) { break; }
29
30 cuttingNodesInSet++;
31 this.addNodeToCollection(tempNodes, name, curNodeData);
32 }
33
34 // Step 3) As long as we still have space left, keep adding more nodes (that we don't have yet)
35 const errorMargin = 5;
36 const maxPointsToFill = this.points.length - 12 - errorMargin; // all points - starting nodes - some margin
37 while(curNodeData.sum < maxPointsToFill && Object.keys(tempNodes).length < Object.keys(NODES).length) {
38 do {
39 name = this.getRandom(NODES, this.totalNodeProbability);
40 } while(tempNodes[name] != undefined);
41 this.addNodeToCollection(tempNodes, name, curNodeData);
42 }
43
44 // finally, swap the old (full) NODES list with the new one
45 NODES = tempNodes;
46}
47
48function addNodeToCollection(list, name, curNodeData) {
49 // if it's already in the list, don't add it again
50 if(list[name] != undefined) { return; }
51
52 var node = NODES[name];
53 list[name] = node;
54
55 // update total sum (we stop filling the list when we have enough for the whole board)
56 var nodeMin = node.min || 0, nodeMax = node.max || nodeMin;
57 var diff = Math.ceil((nodeMin + nodeMax) * 0.5) + 1;
58 curNodeData.sum += diff;
59
60 // check if category needs to be removed from list
61 var catInd = curNodeData.categories.indexOf(node.category)
62 if(catInd > -1) {
63 curNodeData.categories.splice(catInd, 1);
64 }
65
66 // check if action type(s) need to be removed from list
67 for(var i = 0; i < node.actionTypes.length; i++) {
68 var atp = node.actionTypes[i];
69 var atpInd = curNodeData.actionTypes.indexOf(atp);
70
71 if(atpInd > -1) {
72 curNodeData.actionTypes.splice(atpInd, 1);
73 }
74 }
75
76 // check if this node requires any other nodes; if so, add those as well
77 var requirements = node.requirements || [];
78 for(var i = 0; i < requirements.length; i++) {
79 var req = requirements[i]
80 this.addNodeToCollection(list, req, curNodeData)
81 }
82}
83
84function getRandomNodeOfType(what = 'category', tp, nodesList) {
85 var list = {}, totalProb = 0;
86 for(var name in NODES) {
87 if(nodesList[name] != undefined) { continue; }
88 var n = NODES[name]
89
90 if(what == 'category' && n.category == tp) {
91 list[name] = n;
92 totalProb += n.prob;
93 } else if(what == 'actionType' && n.actionTypes.includes(tp)) {
94 list[name] = n;
95 totalProb += n.prob;
96 }
97 }
98
99 // in this case, "getRandom()" is a default function that randomly draws nodes from a list, following weighted probabilities
100 // but it can be any function that randomly selects one element from a list
101 return this.getRandom(list, totalProb);
102}Expansions: Area Detection I
This was the hardest algorithm to figure out for this game.
As I mentioned at the start, I’d only created grid-based boards until now. Finding the empty areas between roads/connections is easy there. (You start with a random empty square, then check if its neighbors are empty, and repeat that until all neighbors are filled with something.)
This time, none of that would work. Nodes could be literally anywhere on the board and the edges could be any length or angle.
Fortunately, a memory sprang at the back of my mind that said something like “can’t you find polygons by always going clockwise?” Turns out that particular memory was correct.
Here’s the idea:
Go through all nodes and sort edges by angle. (We already have this information from placing the power dots.)
Now go through all nodes again:
Go through all edges around the node.
Any time you encounter a node, pick the next edge from its list of edges. (Because this list is sorted by angle, the next edge will always be the first one you encounter counter clockwise.)
Repeat until you’re back at your starting node.
It’s quite simple in summarized form on paper, but it has some exceptions and technicalities that made it hard to implement.
Exception #1: if we do this, then we get many duplicate polygons. (Because we create the same polygon for every node within it.) Instead, each edge should only be used in two polygons exactly.
(Because, well, an edge, basically cuts a space in half, so there is a space on either side. Two spaces, two polygons in which this edge falls.)
To solve this, I keep track of whether an edge has already been used coming from this particular node. If so, don’t ever use it again. This means an edge is always used exactly twice: A->B, and B->A
Because we always go counter clockwise, these must represent the two different polygons.
Exception #2: there are no edges at the boundary of the paper! (I hadn’t even considered this, until it screwed me over and it took hours to fix.)
Because there are no edges there, you can never find polygons with those nodes, because you can never return to the starting node. (On top of that, there isn’t always a clockwise node to go to if you’re in the corner of the paper.)
In the end, I wrote a function “addTemporaryEdges()”, which does exactly what it says. It connects all nodes at the boundary (mostly the starting nodes) with straight lines, and it connects corner nodes on both sides.
Calling this function before finding the areas, solved all issues.
1function findEnclosedAreas() {
2 this.areas = [];
3
4 // initialize "connection used" to false for each edge
5 for(var i = 0; i < this.points.length; i++) {
6 var p = this.points[i];
7
8 p.connectionUsed = [];
9 for(var c = 0; c < p.connections.length; c++) {
10 p.connectionUsed[c] = false;
11 }
12 }
13
14 for(var i = 0; i < this.points.length; i++) {
15 var p = this.points[i];
16
17 // for each connection ...
18 for(var c = 0; c < p.connections.length; c++) {
19 var conn = p.connections[c];
20
21 // ignore edges that have already been used
22 if(p.connectionUsed[c]) { continue; }
23
24 // start a new area
25 var area = [p], areaDone = false, failedArea = false;
26 var curNode = conn, prevNode = p;
27
28 p.connectionUsed[c] = true;
29
30 while(!areaDone) {
31 // add current node to area
32 area.push(curNode);
33
34 // find location of previous point in list of connections
35 // (so we know the ANGLE at which we entered the node, so we can pick the one immediately clockwise to it)
36 var indexByAngle = -1;
37 for(var cc = 0; cc < curNode.connections.length; cc++) {
38 if(curNode.connections[cc] == prevNode) {
39 indexByAngle = cc;
40 }
41 }
42
43 // now pick the NEXT connection after it
44 var newIndex = (indexByAngle + 1) % curNode.connections.length;
45 var newNode = curNode.connections[newIndex];
46
47 // remember that the connection we will follow next, has already been used from this node
48 // NOTE: Don't use the connection we used to GET here, as that should be saved on the node we CAME FROM
49 curNode.connectionUsed[newIndex] = true;
50
51 // set new current and previous node
52 prevNode = curNode
53 curNode = newNode
54
55 // if we're back at our starting node, we're done
56 if(curNode == p) {
57 areaDone = true;
58 }
59 }
60
61 // finally, add the new area we found to the global list
62 this.areas.push(area);
63 }
64 }
65}Expansions: Area Detection II
Great! Now we have all areas on the board (in the form of a list of nodes, in clockwise order).
However, I need the areas to place things inside it. Both “expedition nodes” and “landmarks” can appear in the center of an area, and they need quite a lot of space. How do we know which areas are big enough? And how do we find a suitable position?
Step 1: average the position of all nodes. This gives the “true” average of the polygon. However, if the area is weirdly shaped (like an L-shape), this doesn’t automatically mean it’s the best location to place something.
Step 2: calculate the shortest distance from the average to the nodes of the polygon. This essentially determines the “largest circle” we can draw around the center before we hit something.
If this circle is large enough – great, we can place something here!
If it’s too small – too bad, leave this area alone (for now)
Step 3: let’s revisit that relaxation technique from before!
Relax the “center point”, considering only the nodes of this area. Just like before, this means that this point is pushed away if it gets too close to one particular node. In almost all cases, this means that the point ends up in the location with the most space.
I don’t apply this technique on polygons with only 3 or 4 nodes. Why not? Firstly: there’s nowhere to go. The center of such an area is already the (near) optimal center. Secondly: relaxation doesn’t work. The point would just go through the empty spaces between the nodes, because there isn’t enough to push it back.
Step 4: use this point to place something inside this area!
1function findSuitableAreas() {
2 this.suitableAreas = [];
3
4 for(var i = this.areas.length - 1; i >= 0; i--) {
5 var a = this.areas[i].slice(), numNodes = a.length, nodeRemoveCounter = 0;
6 var center = null
7 var areaIsSuitable = false;
8
9 do {
10
11 // first, find the center point
12 center = [0,0];
13 var tempNumNodes = (numNodes - nodeRemoveCounter);
14 for(var p = 0; p < tempNumNodes; p++) {
15 center[0] += a[p].x / tempNumNodes;
16 center[1] += a[p].y / tempNumNodes;
17 }
18
19 // then find the distance to the closest node
20 // (aka "what's the biggest circle we can draw around the center that still fits within the polygon?")
21 var closestDist = Infinity;
22 for(var p = 0; p < numNodes; p++) {
23 var dist = Math.sqrt( (a[p].x - center[0]) * (a[p].x - center[0]) + (a[p].y - center[1]) * (a[p].y - center[1]))
24 closestDist = Math.min(closestDist, dist);
25 }
26
27 // if the center is too close to an edge node (of this enclosed area), try again, but change the center
28 // (basically, we remove the last node of the area, and keep trying that until it works or we've nothing left to remove)
29 if(closestDist <= someRadius) {
30 nodeRemoveCounter++;
31
32 if(numNodes - nodeRemoveCounter < 3) {
33 areaIsSuitable = false;
34 break;
35 }
36 } else {
37 areaIsSuitable = true;
38 }
39
40 } while(!areaIsSuitable);
41
42 if(areaIsSuitable) {
43
44 // create an area object, including some useful metrics
45 var dx = (this.centerNode.x - center[0]), dy = (this.centerNode.y - center[1])
46 var distanceToCenterNode = Math.sqrt( dx*dx + dy*dy )
47
48 var newArea = {
49 'tiles': a,
50 'center': center,
51 'dist': distanceToCenterNode
52 }
53
54 // then add it to the suitable areas list
55 this.suitableAreas.push(newArea);
56
57 // and remove it from the original areas list (so it isn't used by any other game mechanics)
58 this.areas.splice(i, 1);
59 }
60 }
61}
62
63
64//
65// When we actually want to use the area for something, we call this function on the CENTER of the area to relax it
66//
67function relaxExpeditionNode(c, area) {
68 const numSteps = 100;
69 const center = c.slice()
70 const equilibrium = 1.0
71 const edgePushoff = 0.4
72
73 // we can't really relax triangles or squares, as the node will just be pushed through the side (as there is no node there)
74 if(area.length <= 4) { return center; }
75
76 for(var i = 0; i < numSteps; i++) {
77 var moveVec = [0, 0];
78
79 for(var t = 0; t < area.length; t++) {
80 var surroundingNode = area[t];
81
82 var dx = surroundingNode.x - center[0], dy = surroundingNode.y - center[1]
83 var dist = Math.sqrt( dx*dx + dy*dy );
84 var force = Math.abs(dist - equilibrium)
85
86 if(dist < equilibrium) {
87 moveVec[0] += -dx * force;
88 moveVec[1] += -dy * force * (this.cfg.cellSizeY / this.cfg.cellSizeX);
89 }
90 }
91
92 // also push us off boundaries
93 if(center[0] < edgePushoff) { moveVec[0] += Math.abs(edgePushoff - center[0]) }
94 if(center[0] > this.cfg.resolutionX - edgePushoff) { moveVec[0] -= this.cfg.resolutionX - center[0] + edgePushoff }
95
96 if(center[1] < edgePushoff) { moveVec[1] += Math.abs(edgePushoff - center[1]) }
97 if(center[1] > this.cfg.resolutionY - edgePushoff) { moveVec[1] -= this.cfg.resolutionY - center[1] + edgePushoff }
98
99 center[0] += moveVec[0] * 1.0 / (0.1*numSteps + 1);
100 center[1] += moveVec[1] * 1.0 / (0.1*numSteps + 1);
101 }
102
103 return center;
104}Below is an image that shows the expedition nodes (light red circles, with even more circles inside) being placed at the approximate best location within each area:
Expansions: Natural Resources
Whenever an area is too small to fit a large object (like an expedition or landmark), I try to fit smaller ones: natural resources.
These can be placed anywhere within the area, as long as they don’t overlap anything else (the nodes, edges, or other resources).
To do this, I use an old technique called shrinking the polygon:
Calculate the center of the polygon.
Shrink: subtract the center position from all points, scale them down (by multiplying with a value < 1), then add back whatever you subtracted.
- This is standard procedure for scaling things. You translate it so that the origin (0,0) is at the center, then scale it, then put it back where it was.
While doing this, also calculate the bounding box. This is the smallest box that can fit around the whole area. It’s nothing more than the largest X distance and largest Y distance between nodes.
Now I simply sample random points within the bounding box.
They are not within the shrunk polygon? Try again.
They are too close to a node from this area? Try again.
They are too close to another natural resource? Try again.
Lastly, I rotate the resources randomly and vary their amount based on a rough approximation of area size.
1function addNaturalResources() {
2 this.naturalResources = [];
3
4 for(var i = 0; i < this.areas.length; i++) {
5 var a = this.areas[i];
6
7 // find center of polygon
8 var center = [0,0];
9 var numEdgeNodes = 0;
10 for(var t = 0; t < a.length; t++) {
11 center[0] += a[t].x / a.length;
12 center[1] += a[t].y / a.length;
13
14 if(a[t].edgePoint) {
15 numEdgeNodes++;
16 }
17 }
18
19 var numResources = Math.floor(Math.random()*4) + 1;
20
21 // natural resources look ugly (and unbalanced) in areas connected to edge, so
22 // 1) ignore any areas where more than HALF the points are edge points
23 if(numEdgeNodes >= Math.round(a.length*0.5)) { continue; }
24
25 // 2) and only allow 1-2 natural resources in areas with few nodes
26 if(a.length <= 4) { numResources = Math.floor(Math.random()*2) + 1;}
27
28 // shrink polygon towards center
29 // also immediately find the bounding box
30 var minX = Infinity, maxX = -Infinity, minY = Infinity, maxY = -Infinity;
31 var scaleFactor = 0.7;
32 var poly = [];
33 for(var t = 0; t < a.length; t++) {
34 var dx = (a[t].x - center[0]) * scaleFactor + center[0];
35 var dy = (a[t].y - center[1]) * scaleFactor + center[1];
36
37 minX = Math.min(dx, minX);
38 maxX = Math.max(dx, maxX);
39
40 minY = Math.min(dy, minY);
41 maxY = Math.max(dy, maxY);
42
43 poly.push({ 'x': dx, 'y': dy })
44 }
45
46 // randomly place points within bounding box
47 // if they are also inside the polygon, yay! Save it!
48 var tempResourceList = [];
49 const maxTries = 200;
50
51 for(var r = 0; r < numResources; r++) {
52 var point = { 'x': 0, 'y': 0 };
53 var outsidePolygon = false, tooCloseToNode = false, tooCloseToResource = false;
54 var locationNotSuitable = false;
55
56 var tries = 0
57 do {
58 point.x = RNG() * (maxX-minX) + minX;
59 point.y = RNG() * (maxY-minY) + minY;
60
61 outsidePolygon = !this.pointInsidePolygon(point, poly);
62
63 if(!outsidePolygon) {
64 tooCloseToNode = (this.closestDistToPolygonNode(point, a) <= someRadius);
65
66 if(!tooCloseToNode) {
67 tooCloseToResource = (this.closestDistToResource(point, tempResourceList) <= someOtherRadius);
68 }
69 }
70
71 locationNotSuitable = (outsidePolygon || tooCloseToNode || tooCloseToResource);
72
73 tries++;
74 if(tries >= maxTries) { break; }
75
76 } while(locationNotSuitable)
77
78 // if we failed to find anything (probably not enough space), just ignore this one and continue
79 if(locationNotSuitable) { continue; }
80
81 var nr = {
82 'x': point.x,
83 'y': point.y,
84 'type': this.getRandom(NATURAL_RESOURCES, this.totalNaturalResourceProbability, RNG)
85 }
86
87 tempResourceList.push(nr);
88 this.naturalResources.push(nr);
89 }
90
91 }
92}
93
94//
95// These are just default helper functions for finding closest distance to something
96// or checking if a point is inside a polygon
97//
98function closestDistToResource(point, list) {
99 var minDist = Infinity;
100
101 for(var i = 0; i < list.length; i++) {
102 var dx = (point.x - list[i].x)*this.cfg.cellSizeX, dy = (point.y - list[i].y)*this.cfg.cellSizeY
103 minDist = Math.min(dist, Math.sqrt( dx*dx + dy*dy ));
104 }
105
106 return minDist / Math.min(this.cfg.cellSizeX, this.cfg.cellSizeY);
107}
108
109function closestDistToPolygonNode(point, poly) {
110 var minDist = Infinity;
111
112 for(var i = 0; i < poly.length; i++) {
113 var dx = (poly[i].x - point.x)*this.cfg.cellSizeX, dy = (poly[i].y - point.y)*this.cfg.cellSizeY
114 dist = Math.sqrt( dx*dx + dy*dy )
115
116 minDist = Math.min(dist, minDist);
117 }
118
119 return minDist / Math.min(this.cfg.cellSizeX, this.cfg.cellSizeY);
120}
121
122function pointInsidePolygon(point, vs) {
123 // ray-casting algorithm based on
124 // https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html/pnpoly.html
125
126 var csX = this.cfg.cellSizeX, csY = this.cfg.cellSizeY;
127 var x = point.x * csX, y = point.y * csY;
128
129 var inside = false;
130 for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
131 var xi = vs[i].x * csX, yi = vs[i].y * csY;
132 var xj = vs[j].x * csX, yj = vs[j].y * csY;
133
134 var intersect = ((yi > y) != (yj > y))
135 && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
136 if (intersect) inside = !inside;
137 }
138
139 return inside;
140}Here’s how that looks:
Expansions: Tiny Nodes
Last but not least, but certainly the least in size, are the tiny nodes.
These are placed on edges to modify what they do (or can’t do). They are optional to visit and own. (Their usefulness highly depends on your strategy, personal mission and what other players are doing. So it’s not fun to force players to use them all the time.)
For example, a Triangle turns the edge into a one-way route: you can only move over it in the direction the triangle points.
These were very simple to add. (Fortunately, after that whole mess with the area detection algorithm!)
Go through all nodes.
Go through all edges of this node.
If one endpoint of the edge already has more than X tiny nodes, ignore it. (Each edge has two endpoints: the node it came from and the node it’s going to. The value X is simply a maximum on the number of Tiny Nodes per node.)
Otherwise, calculate the average ( (node1+node2)/2) and place a random Tiny Node there.
Also calculate the angle ( Math.atan2(node2.y – node1.y, node2.x – node1.x) ) and rotate the Tiny Node to match.
That’s it! A simple, small addition that adds huge implications to the gameplay.
1function addTinyPoints() {
2 // IMPORTANT NOTE: these nodes were called "intermediary points" before they became tiny nodes, so that's still everywhere in the code
3 this.intermediaryPoints = [];
4
5 const minPointDistance = 0.5;
6 const maxPointsPerNode = 2;
7
8 for(var i = 0; i < this.points.length; i++) {
9 var p = this.points[i];
10
11 if(p.edgePoint) { continue; }
12
13 for(var c = 0; c < p.connections.length; c++) {
14 var conn = p.connections[c];
15
16 // enforce a strict maximum of X intermediary points surrounding each node
17 if(p.iPointsCreated >= maxPointsPerNode || conn.iPointsCreated >= maxPointsPerNode) {
18 break;
19 }
20
21 // don't consider connections twice!
22 if(conn.intermediaryPointsExhausted) { continue; }
23
24 // don't allow connecting with an edge node!
25 // (first step of the whole game should not have a tiny node)
26 if(conn.edgePoint) { continue; }
27
28 var iPoint = {
29 x: (p.x + conn.x)*0.5,
30 y: (p.y + conn.y)*0.5,
31 type: this.getRandom(TINY_NODES, this.totalTinyNodeProbability, NODE_RNG),
32 angle: Math.atan2(conn.y - p.y, conn.x - p.x)
33 }
34
35 this.intermediaryPoints.push(iPoint)
36
37 p.iPointsCreated++;
38 conn.iPointsCreated++;
39 }
40
41 p.intermediaryPointsExhausted = true;
42 }
43}Check the small shapes (circles, triangles, etc.) halfway edges on the image below for the result:
Conclusion
Hopefully this devlog was interesting to read and you’ve learnt many awesome techniques for generating random worlds for games.
It’s really mostly about practice though: as I create more and more of these games, I find it easier to solve common problems with random generation, and also dare venture more “out of the box”. A year ago I wouldn’t even have known the first step – how to place points semi-randomly on the board – but look where we are now!
So the least I can say is: hopefully this devlog inspired you to make your own projects a reality, no matter how challenging or innovative they are.
If you like what you see, please try any of my games and give me some feedback, or support me any other way!
Until the next devlog,
Pandaqi