Real World Map Generation; now with Roads, Water, (dummy) Buildings, Zombies and Overmap

Previous post

I would be lying if I said it was already playable (it’s far from it), but hey, you can debug-spawn some weapons and kill zombies in a Real World Map!

Screenshots and downloadable worldmap (Boston)

New features

  • Water tiles.
  • Road width based on road type. Also sidewalks.
  • Dummy buildings with the real shape.
    Diagonal walls are open. I plan to replace them with procgen ones.
  • Random zombies of basic types.
  • Overmap with 4 tile types: fields, water, roads and buildings (house icon).

General comments

I am fairly happy with the advances. I can orient myself on maps of places I know, if I know where I am in the first place. It feels good to navigate the map based on real world knowdlege.

From here, the main question is if I can generate buildings (and their contents) with some reasonable quality. There are a lot of other missing elements (vehicles, trees and plants, bridges and tunnels, thematic zombies based on location…) but those seem easier than the buildings. And the VERY difficult parts (missions, content from mods) are not in the scope of the project.

I think there is enough done (mainly the overmap) to see the limitations. Because the overmap is generated from the details (the opposite of what the game does) the resulting roads are very messy. I see that as a minor issue because it conveys the general layout and still allows you to navigate around, if you now the area.

For a realistic ingame mapgen this bottom-up approach (from detailed map to overmap) is not practical. You need to fully generate the details of all the visible overmap tiles to be able to render them on the overmap. And probably much more because you cannot generate overmap tiles by themselvs (the buildings do not align with any grid) so you would need to generate big detailed areas.

Which bring me to other important topic: execution time. At some point I had an implementation that would have taken more than 12h to generate part of Boston. Fortunately, it was so slow that I was forced to look for the problem. Now it takes:

  • Less than 1 minute and a half to generate the 10,4 km2 Bostom overmap from the screenshots (2,5 x 1,8 miles / 3,6 x 2,9 km at 1,2 meters per pixel).
  • Around 36 minutes for a 191,52 km2 area (9 x 8,25 miles / 14,4 x 13,3 km).
    FYI: this maps expands (but not fully covers) 25 overmap regions (of 180x180 overmap tiles), 5 regions wide x 5 regions high.

The data shows that it’s not linear time (18.4x area => 26.4x time) but it still can manage big areas. I asume (I could be wrong) that the most limiting factor is writting the files. The biggest map has more than 500.000 files (1,96 GB) and it takes a while to write them all.

Those times include all the detailed map, not only the overmap. So no more mapgen is needed, unless you reach the end of course, but incremental generation is not implemented.

Boring technical details

I have delved into the realms of MapGen and GIS data and have become much more humble. Two sentences I’ve said kept coming to my mind:

Yeah, that [the water] is the easiest feature to include. (source)

Oh boy I was wrong. Not only the polygons from OSM data can be defined in a very interesting ways, the coaslines are not even closed polygons, just lines with the water “on their right side” (based on the points order). A couple of links if someone wants to go into the rabbit hole of coastline rendering: 1, 2. I went with a hacky solution that only works with bitmaps because I don’t need the vectors.

The image was a convenient mid-point to split the steps; a more serious implementation would get rid of it (source)

I didn’t think this well enough; I had the impression that I could use some sparse data structure or an array of a smaller-than-RGB-values type. But I really rely on image manipulation with the Skia library (via SkiaSharp) for some key processes. The improvements I could get from an array are not worth it the complexity of reinventing the wheel several times.

I suspect that there are one or two easy performance gains pending regarding the reading and writing of image pixels. But because the times are not so bad, I left that on the TODO list. The 30 minutes map it’s an insanely big one and for the tests I just use smaller ones that take less than a minute

One easy thing is to decrease the color depth. 255 colors would be great, but on the long term that wouldn’t be enough because CDDA (no mods) has > 600 tile types. I don’t know any color format with a number of colors between 256 and 32.768, which would be the one to give it a try.

Also, for saving the data I don’t think I can beat the PNG compression unless I just ZIP it. The image is indeed much smaller than the final generated map, so in case I go for a incremental CDDA-data generation PNG would be the smallest format (that or any ZIPed format) for the intermediate step.

Finally, for some features I have in mind (like spawning rate based on building density) I may need another full map sized image on memory… so I stand corrected. I need that image.

One good news is that I realized that I can skip the detail map of overmap tiles with 100% water or field tiles and let the game generate them. For the fields it will probably be a visible difference in texture but in some specific cases it can really make a difference in generation time and disk space. I still haven’t tested it, but AFAIK it should work fine.

Final random notes

The project has been migrated to C#. It’s not C or C++ but, performance wise, it’s a bit better than python.

I found a more potent tool to get OSM data. The official OSM export tool has a fairly low limit but the Hot Export Tool allows downloading much bigger areas.

I’ve changed the scale to 1,2 meters per pixel because the roads seemed a bit small for CDDA vehicles which, if you take a scale of 1 pixel = 1 meter, a normal CDDA car would be 4 meters / 13 feet wide (more than double of a real one).

A funny detail about the CDDA vehicle moving system is that the roads close to angles multiple of 45º need to be wider than those close to multiples of 90º. To be able to scale them based on the angle I had to use “rounded” road endings. A minor issue, but I would prefer the square endings for the roads.

All opinions, comments and suggestions are welcome.

5 Likes

Wow this is really cool. Cant wait for buildings and other fun stuff to be added. Godspeed to you.

1 Like