Design : Map Generator

This is a design document, regulars already know this, but for the others: the following information is not in the game yet, it's about what's going to be implemented next. The explanations are somewhat technical as I have more or less been asked to do so. It may help as there's basically no useable documentation on proper procedural city map generation on the internet.Comments and ideas from other coders are more than welcome.

I have already posted on the board (which is now working properly btw, feel free to join) a few screenshots about the road network and map generator. Those screenshots are a bit outdated compared to what's I am going to explain, though. My city generator will proceed in 3 steps:

1. Build road connections between sectors

First, the basic rules: Each sector has 4 exit points (N, W, S, E). Every sector must be connected to the city center, or in other words, all sectors must be connected to any other sector. Road/Exit density must be higher at the center than in the outer regions. 

So first, the whole city map is filled with inter-connected sectors, then, exits/roads are randomly removed, the farther from the center, the more roads are removed. Then, unconnected roads are either connected back or removed completely. There's a function that will determine if a region has enough roads or not (fitness function) based on the rules explained before. In detail, this function will check each 1/3 of the map, verify if sectors are connected, and that each tier as the expected road density: the central tier must have 3.5 average exits per sectors, the second tier 3, and the last tier 2.5, more or less. If a region has not enough or too many roads it's generated again until the fitness function returns a positive result. Once we are done, we'll have a nice 2D array with exit points. 

2. Trace the roads based on the exit points

Based on this array, I will trace roads in the sectors. From here I will use a simplified grammar system. For example if one of the sector has a single road going N/E it will pick between several ways of drawing this road like: 

 

3. Define zones and place buildings

Once we are done with all this road tracing nonsense, we will use the space between roads to define where buildings are supposed to appear. That will be the trickiest part, and to be honest I don't exactly have a precise algorithm for that yet. Don't get me wrong, though, I know enough to be sure to get a working method once I am done deciding what parameters must be added to the zone/building editor.

Until then, here are the main ideas. I am going to remove sectors types, instead, buildings will be defined by their size, their density in each tier of the map, and probably a few other parameters I have yet to decide. For example, factories will be big buildings that can only spawn in the outer ring, while office buildings will be smaller ones mostly spawning at the center and second 1/3 of the map.

The main issue will be to find a nice algorithm to put all the buildings according the rules and according to the available space. Based on the free space around the roads, I will define an array of zones (rectangles) where buildings can be put. Larger buildings will spawn first, and then the remaining space will be used or partitioned in smaller zones to put the remaining buildings (L shaped buildings cornering a road, like in the current city center map type, will probably disappear for a while as they are the most difficult to handle without using specific coding).

Then, I will probably use the same concept I used for the road network, a fitness function and randomized regenerations until satisfying results are achieved. A friend told me that a genetic algorithm could be good for this kind of stuff, but I am unfamiliar with those, at least in this setting, and I don't really see how it would beat a purely random generation kept in check by a fitness function as I am not looking for a "perfect" result anyway. So, even if it sounds "edgy", i am probably going to use more conservative methods here.

It's going to cause issues with the current AI implementation, as it relies sometimes on sector types to save time. Nothing major, but it's going to take me some time to adjust it so it doesn't freak out with the new map-gen.

--

Once I am done with all this, I will start adding floors to existing buildings. To do that I will have to differentiate the zone editor from a new building editor. The new building editor will allow to select one or several zones to define each floor of a building. For example, a mansion may have a "living room" zone (with a TV, a couch, a table and some random furniture) and a "bedroom" zone with beds, chests and related stuff. Technically, it's fairly easy to do so, the tricky part will be to make the NPC understand how to navigate between those levels. Before you ask, no it won't be possible to shoot from the 2nd floor of a building toward the streets. As far as the engine is concerned those are two different unlinked zones. It's not possible to alter the code to do it without rewriting basically everything, and even so, it wouldn't allow me to handle thousands of NPC in real time as I do now.

That's all for tonight, folks!