The unique challenge with MiniGolf Endless MMO was to create an endless series of golf holes with the usual obstacles like trees, rough, bunkers and water and find a balance of difficulty and playability. I'm pretty pleased with the result and I thought the community might enjoy reading about how it was achieved.
The algo follows these basic steps
Seed random number generator based on the hole number
This is required so that everyone plays the same layout - vital when we have online replay sharing and high scores!
Get the ranges for the random parameters based on the hole number
This provides the difficulty curve. After about hole 50 the parameter ranges are wide open. You'll still see easy holes sometimes but can also now see some really nasty ones ;)
Place start and end points
End point north of start. The maximum distance grows as the hole number increases.
Use random walk to carve a path
The entire map is initialised to pure trees at the start. Starting at the tee we move one tile at a time with probability of moving away from the goal of slightly lower than 50%. I found 40-45% provided a nice gnarly value, but we go as low as 25% for some more direct easy holes. The photo shows this step.
Widen the fairway
We then apply a couple of rounds of widening. We simply take every single fairway point from the current narrow path and replace it with a circle of fairway of random radius. This carves out a nice gouge in the trees. We encroach onto the fairway from the tree-line with rough subsequently.
We pick random fairway/rough to convert into bunkers and water. After the initial seed locations are selected (the number of which is a function of the hole number randomisation) we widen them using the 'kernel replace' method we used to make the fairway before. The result is reasonably natural placement of the obstacles.
However we have a problem! Once water is involved this can render the course unplayable. In principle the entire thing could be flooded! We determine whether the flag can still be reached from the tee using best-first-search. If a path cannot be found we remove water near to the point on the path closest to the destination flag. This ends up pushing a fairway path back through the water hazards ensuring we always have some way to complete the course. It isn't perfect and in the presence of wind some holes will still be very challenging, but mostly it guarantees a route from beginning to end.
Not strictly part of the procedural generation, but we do use the randomisation to place decorative features like special tiles to break up the environment. Autotiling is a standard algo so I'll save that for another post!
Hope you enjoyed this read!