Project Forge: Town Roads and Plot Zoning - Part 1

Last update I mentioned that the next post would likely be about NPC generation and simulation. Well, I started doing that and finished the generation algorithms; however it turns out simulation will require much more environmental input than I anticipated, requiring a development shift to town generation algorithms. This will give simulated NPCs much more of a "context" to work with, and will save me from much code refactoring when it comes time to tie all these modules together.

Town generation started out with the basics; each town would be defined from the seeded towns discussed in the last update, and would grow outward from a weighted center point of the town plot.

The initial boundaries of each town are defined by the local resources. Each pixel from the global map on the left corresponds with  16 pixels on the local map on the right. Each pixel in the map on the right represents one square meter.

The first step to generating towns is road generation. I made a critical mistake during my initial attempt at solving the problem, and locked myself into a solution that used templates to generate roads. This means that each town would have had a road system that inherited from a pre-defined template with several random variations. By the time I realized how awful of an idea this was, I had already blown most of my spring break programming it.

Example of one of the templated road systems. Purple lines represent roads, and green square represent  potential zones for residential development. 

I have a feeling that my initial idea was something based on L-systems like what this guy does, but the idea never actually came to fruition before I started actually programming. Looking back I have no idea what I was thinking; but on the bright side there were a few useful algorithms that had to be programmed to make templates work that can probably be reused elsewhere.

Okay - with that garbage out the window, I came up with a much more natural approach to the problem that likely emulates how roads are created in real life. The idea is to break the local map down into grids that contain several square meters of land. An entity that we'll call a road builder is spawned at a random location somewhere near the center of the local map. If the grid that the road builder lands on is not connected to a road, then it will construct a road connecting that grid to the main road system. By repeating the process and moving the road builder to another random spot on the grid, a kind of "crack" of roads is formed. 

Shit, it already looks better than that template crap.

In order to resolve the utter lack of interconnectivity on the road grid, an algorithm is executed which connects the endpoints of each path to other endpoints to increase connectivity and to make everything look a bit more natural. 

At least it doesn't look like a spider web anymore. Notice how the earliest built roads form a backbone for the network.

The nice thing about this road builder algorithm is that it works for any size town. It can be used to generate a town of only a few homes or even a metropolis of 500+ buildings. 

Road network from above seeded with building lots(green). There are about 200 buildings lots served by this road network.

Much larger network, unlike the ones above this one's "road builders" were bound by proximity to the road grid, rather than proximity to the origin point of the town. I think there's ~500 building lots on this one.

That's it for this update. Tune in next time for even more images of lines and boxes. 

-zalzane