So you want to create a simple procedurally generated city? Well you have come to the right spot! I will be going over how I implemented a simple generation algorithm to create the city generation for Cash Force and how it is being used to provide endless mission for our getaways heists. Over the course of this post I will be going over the reason to use this generation method, why it was perfect for Cash Force, the algorithm, and ways to use it to create more powerful systems!
So Why This Method?
Cash Force being a VR game required a efficient and simple means of generating a world during run-time, without all the bells and whistles of other procedural generation systems. Most algorithms (as seen below) use rapidly expanding trees or path-finding algorithms to create multiple roads and district networks. All Cash Force needed was a portion of what this was offering and consistent exit points on the map. So after digging through countless methods I stumbled upon this simple solution by user Joe Jankowiak on creating a procedural generation system. What they proposed was using randomly generated rectangles on a set grid size to create consistent overlaps. Using the areas in which rectangles overlap, you can create your road pieces, and the resulting free areas can be randomly ID'd to act as different districts, zones, or environments. This solution was simple and perfect for Cash Force so I had to give it a look. Unfortunately the code reference was done on JSFiddle with JavaScript and had many optimization and logical issues. While some were solved in the stackoverflow post it was mentioned in, it needed some fine tuning.
Why Cash Force (and I) Love This Method
Besides the previously listed reasons of being a VR game that needed a simple and quick solution to procedural generation, there are many other reasons this method was perfect! First, the method has an consistent look to our desired city layout. The team was looking for a city block style to work with our tile based art style and AI system. This method of generation allowed for straight roads with intersection going vertical and horizontal, no curves. Second, we wanted easy reference to the road tiles to create mission paths for our getaway van to move across. Having reference to the road tiles is not something other algorithms don't do, but since this algorithms generates the "environment" and then the roads, we can get immediate access to the road tiles as they are generated and transition into our path-finding for the mission set. This also proves helpful as we want "engagement" points on the map for higher enemy encounters. Accessing the roads as they spawn gives the ability to adjust a tiles "type" before we even start path-finding. Finally, this method guarantees a certain amount of exit points on the sides of the map based on the given rectangle spawning size. Cash Force relies on having a spawn point in the map and path-finding to an exit points on one edge of the map. Since we can consistently create these exits, we don't need to put in an edge case to create these outlets for our mission escape.
How it Works!
The moment you've been waiting for, how does it work! As seen above we go through a few steps, with the last one (Mission Generation), being where additional functionality can be added for your unique game necessities. The core of the algorithm is the world generation. This is done using a simple method of rectangle generation in a bounded grid. A quick description of the algorithm is shown in the flowchart below.
Without diving too much into each step, the procedural creation works in 3 parts. First, a 2D grid is created and shuffled into a one dimensional array. We then grab tiles from this array and check if they have an ID set. If not, the tile generates a rectangle in the bounds of the grid starting at the tiles as the bottom right corner of the rectangle. Every tile that is overlapped by this rectangle then gets the same randomly generated ID. When all tiles have an ID, we loop from top left to bottom right of the 2D grid and check if the tile to the right or below has a unique ID from the selected tile. If one or both have a unique ID, then the current tile becomes a road tile. Once completed a generation like the ones below are created (depending on size of grid). Tile coloring similar to previous examples was done when the random ID's were created, providing a unique color as well.
If there is interest in creating a tutorial on the procedural generation method I can provide further information on my process and the optimizations I made. While this was done in Unreal blueprints, a C++ or C# implementation would be just as simple to create.
Show Me The Power!
So as I noted at the start of this post, you can use this method to create unique powerful implementation (such as the path finding methods I used for missions). One way is immediately adding road pieces as you set them in the final step above to a separate list. This gives you access to a grid of paths, which can be used for Dijkstra or A* for path-finding. You can also set types when you set unique ID's to provide a way of classifying districts or zone types to the white space generated between roads. With the grid being tile based, there is plenty of other information you can add and adjust as you generate to fit your unique game needs. For Cash Force this was a combination of using path-finding methods and random type assigning onto tiles to create our mission paths for each generation. While this algorithm has a very simple means of generation, the layers of systems that can be added on top of it make it a powerful tool in the right circumstances.
Thanks for reading! If you have any questions about how this method was accomplished or want more information on implementing this yourself, feel free to reach out in the comment section below. Until then, it's time to back to coding!