So as the topic states, i was just curios if others have any tips, or advice on how to do procedural generated tiled layout of something?
In my case im trying to take a collection of buildings and generate a tiled city layout for rendering as an way to interact with the buildings in my game. But getting the algorithm to give back a logical organic looking city in a tiled layout is proving harder than i first thought. Here is an example of what i can make so far, but i need to add grass,water,and tree tiles in in a sensible manner, except im not really sure how to make it sensible and not random. So far all buildings are placed based on a relationship scoring of things around them.
Three ideas come to mind myself but kind of depend on the kind of city you want to generate.
Weighted Random Walk
The first one is a variation of a simple random walk algorithm to generate roads then build off of there.
When doing simple cave gen I tend to start a handful of agents at the center of the map and have them wonder outward randomly for a fix number of steps. This results in really organic caves but by adjusting the chance they change direction each step you can get more structured grid layouts but with enough variation to look organic.
From there you can identify the blocks the walkers created and fill them with buildings according to what you want. Personally since most cities tend to grow outward I would have larger buildings and commercial centers be more likely near the starting position of the walkers and along really long sections of roads with residential becoming more likely the further you get from the city center.
Room/Block Based Generation
Another option I could see is an adaptation of the process described here:
Instead of rooms you could think of them as city blocks which you can generate with a range of sizes and other data (like zoning, density, ect) and use this method to randomly spread out the blocks. Instead of randomly selecting rooms then calculating a graph of how they are connected you could align the blocks and then between them generate the roads.
I dont know how well it might work but I always thought this was an interesting proc gen method and I could see it work with some modification.
Simulated Growth With Cellular Automata
You could use Cellular Automata to simulate a cities growth. Have each building be a cell and then you can set rules for each cell to decide what should and should not be placed there. You can then generate roads along the edges of the cell to divide up the city into a few grids.
This works almost a bit like the weighted random walk but is more controllable and customizable, and instead of generating roads and using that to inform you city layout it generates the buildings based on rules and then you can block them up with roads.
While more around cave gen this blog post is a quite a good resource for basic Cellular Automata:
Final Word
While I describe 3 methods above generally speaking you don’t usually use just one. You can combine multiple methods for a variety of effects depending on your needs. For example you could use Room/Block based gen to decide on the general block layout, Cellular Automata to generate the buildings in those blocks, and then random walk to generate roads.
It really depends more or less what gets you the result you are looking for and may require some experimentation.
EDIT: Forgot about Wave Function Collapse
I forgot about WFC. This algorithm is really simple on the face of it and produces some really good results. Basically every cell contains what can be in it (usually a set of IDs) and then you pick one at random in a random cell. Each tile piece contains what tiles can connect to it so when placed removes any invalid tiles from the cells around it.
You then pick the cell with the least number of possible combinations and then randomly pick one of those. You continue until all cells are filled or no more cells can be filled without violating the set constraints.
This is a really cool algorithm and if I remember is one of the ways Townscraper generates the town as the player builds. You can also set the constraints manually or generate them from examples. It can break down a bit though on more complicated layouts (for example it may understand that a door needs two wall tiles and nothing in front and behind it, but doesn’t fully understand it needs an enclosed space as well though you could fix this with a more complex solver).
So basically the natural terrain? I’d look into the random map generation for various strategy games and port something over. Since it’s background and not foreground it doesn’t have to be the best, just not distracting. You can get a lot of the way there with a simple fractal heightmap, water level, and river-drawing algorithm. Grass and trees go where the slope and ground wetness are right (I honestly have no idea, but you can look it up). Otherwise, the ground is dirt, I guess. Of course, where there are buildings the green stuff is paved over, but typically people don’t make land out of water to build on.
Bonus, maybe: A simplistic algorithm for placing rareish things:
Hmmm, interesting! Not sure i want to start over from scratch, and the wave function collapse is a very interesting approach, For now im sticking to what i have alreay build taking insperation from these to improve it, In the future on a rewrite, I knda like the idea of doing a geometric road layout using:
then filling in the buildings with a modified wave form colapse, just not sure a wave form colapse would work in my case.
Any how soneed to flood filll some grass and trees into the islands of nothing but for now heres where im at:
Like i said before there is a map of tile relations to score any given tile placement, and the algorithm flips between expanding roads and greedy filling non road tiles, need to tweak some relationship values but im pretty happy with the general appearance, as this layout is entirely cosmetic. I’ll probably rework this again when the sdf render is completed to get better visual coherency.
Thanks all for your suggestions and reading material!
So update, i did end up totally rewriting the generation algorithm, it now uses a Poisson-disc inspired method to pick road intersection points, which works out way better than randomly trying to place roads. The main difference is i chose not to generate all the points at once and rather incrementally build road networks using the Poisson-disc constraints to all existing intersections to pick a new intersection, then expand roads to that new intersection.
Some interesting gotchas to avoid parallel roads for anyone following in my footsteps, to avoid directly adjacent parallel roads, i had to constrain a new intersections and new road segment to be less than 2r length where r is the minimum distance between two intersections. This normally would not work on a floating point gird, but as my grid is an integer gird this does mathematically work. In c++ i found i can correctly round any euclidean distance calculated between two points towards zero by first taking the absolute value, then casting it to an int as in c++ casting a positive float to an int simply discards the floating point value so anything between say 1 and 2 becomes 1. Keep in mind if you were thinking to use floor without taking the absolute value, if your distance is negative you could end up rounding something like -3.7 down, which would be -4 not -3 which in distance terms -4 is larger than -3 meaning you rounded the distance up.
