See [Technical Devlog] Unstable Universe (Part 1) for Part 1 of this devlog.
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:
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.
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!
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:
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.
Here's how that looks:
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.
Check the small shapes (circles, triangles, etc.) halfway edges on the image below for the result:
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,