Let's talk a bit about map generation in Xenos. I've started development of the game with making a procedural map generation system, and I've talked about it in the very first post. However, then we decided to change everything, and the old system had been summarily ripped out; replaced with a new, kinda-similar-but-not-quite one.
So, how does Xenos create maps now?I still have not solved it in general - current algorithm is heavily geared toward creating town maps. On the other hand, it's simple and it works. As you may remember, maps in new Xenos are made of chunks, that are approximately 10x10 old tiles in size. A single chunk can contain a building or a length of road - i.e. open street. And a single "location" is 20x20 chunks - for now, this is the whole of Xenos, but in the future I'll add more locations that connect seamlessly.
The generation of a location starts with a road grid. I used a very simple algorithm: imagine an empty 20x20 grid. Then, mark some rows of it as "road" - making horizontal and vertical lines 1-3 squares apart. You end up with a grid of streets and city blocks, but it looks much too regular. To break up regularity a bit, let's simply remove some roads. First, going horizontally along every row, we randomly remove some roads between neighbouring blocks, in effect merging them. Then repeat the same, only going vertically along every column. As a result, you get a nice irregular pattern of streets.
There are a couple of gotchas to watch out for: first, we shouldn't merge too many blocks in a row - we want to have enough roads for driving. This is easily accomplished by tweaking the probability of merge (larger block means smaller probability) Second, and more important, is to check for disjoint roads. Sometimes, when we remove a piece of road, the whole grid would be split into two unconnected parts, and we really don't want that. Fortunately, that is pretty straightforward to check.
Once we have the road pattern, next step is to place actual streets. Again, a pretty straightforward algorithm goes over every chunk and select a matching piece of street - a straight road, a corner or an intersection.
Next we have a "special chunks" step. The idea behind it is, what if we want our map to have, e.g. one or two fuel stations, no more, no less? We might have a list of these "special" objects with respective counts. After streets are placed, the next step is going through this list and finding random places to fit objects. Some of these may take up more than one chunk - for example, our fuel station is 2x2, with 2 of those overlapping the street. Every special object has some code attached, that basically answers one question: "given the map generated so far, can this object be placed in point X?" In the above example - fuel station, that piece of code checks for a length of straight road to "attach" the station to.
Finally, when we have placed all special objects, the rest is filled with the most dumb algorithm imaginable - every chunk that is still empty is simply assigned a random object (well, not totally random, but random from the "applicable for town map" list).
And this is basically it - we have a town location that is random, more-or-less irregular (the grid of chunks is still apparent, of course, but it's not bad in practice), and contains the stuff we want it to - but in unpredictable places. I think it's pretty good for a game map.
Very insightful. Are you planning on natural areas?
Yes, of course. We're just starting with town because it has lots of different stuff in it, so that the player would have things to do.
Later we'll add wilderness, village(es), military base and alien base(s) at the very least - and probably some other interesting locations.