Polygon map generation FAQ

Some of you have sent me feedback on my polygon map generation blog post series (part 1, part 2, part 3) and questions about how it could be used in your own projects. Here are some thoughts on how to extend the map generator:

• I want to generate a tile map, but this project only generates polygons. The map generator uses polygons to create structure, but that structure can be converted back into tiles or bitmaps. The developers of Realm of the Mad God wanted a 2048 X 2048 tile map. They wanted the elevation and moisture data in a 2-dimensional array so that they could generate their own biomes, monster zones, and vegetation. The solution is to render the polygons into a bitmap, and then extract the color data into an array. The source code includes a function makeExport() to export the polygons in array format, but I omitted this from the demo, for simplicity. Here’s a demo with the export feature enabled.


• I want to generate the map on the fly, like Minecraft. The main reason I used the polygon approach was to create large scale structures: mountains, rivers, roads. A purely local map generator has no knowledge of other areas, and thus does not generate good large scale structures. A possible solution is to use both. Use something like the polygonal map generator to generate the large scale structure with low resolution, exporting thresholds and other parameters. Then use a local Perlin map generator that uses those parameters to generate the small scale structure at high resolution. For example, you might use the polygon map structure to generate a 1000 X 1000 biome map, and then each of those 1,000,000 zones could itself be a 1000 X 1000 locally generated map. That’d give you a 1,000,000,000,000 tile map that you can generate on the fly, with only 1 MB of additional storage for the large scale structure. I’ve done a few experiments along these lines but don’t have anything to show yet.


• I want to have objectives, quests, goals, etc. on the map. This is one reason polygons are so appealing: they produce a notion of “area” or “zone” that you can use for creating high level game structures like towns, quests, or territory to conquer. The demo used the structure to create roads. Realm of the Mad God uses the structure to place quests. The ways you can use the polygons are game specific so it was hard to make a good demo for it.


• I want to implement pathfinding. If you’re rendering the polygon map into a tile map, you can use these two levels for hierarchical pathfinding. Use Floyd-Warshall to precalculate all paths between all polygons, then use A* or another algorithm to compute the local paths on the tile map.


• I want to have unpassable terrain. In Realm of the Mad God, all biomes except lakes were walkable, so I didn’t implement interesting obstacles in the map generator. I think the types of unpassable terrain will vary by game, but both polygons and edges should be useful high level structures to make unpassable areas like cliffs, mountains, caves, lakes, fences, walls, and chasms.


• I want my designer to draw the island shape. The map generator can handle any boolean assignment of polygons as land or water. I included four algorithms (Radial, Perlin, Square, Blob) to demonstrate that it’s not tied to a single algorithm. You can write your own code in the IslandShape class, including something that uses a custom hand-drawn shape.


• I don’t want the mountains centered. I experimented with non-centered mountains, but for Realm of the Mad God they wanted the mountains in the center, for gameplay reasons. I think non-centered mountain ranges would be more interesting, and I believe they would work well in this map generator. The main constraint is that that river algorithm requires a monotonically decreasing elevation from the mountains to the ocean (e.g. no local minima). In practice that means you could move the mountain range to one side or the other, but the river algorithm would get confused by valleys with no outlets. A more complex river algorithm could handle local minima.


• The borders between polygons are too noisy. This is controllable by a parameter, NoisyEdges.NOISY_LINE_TRADEOFF. I should have made this controllable in the demo. It should vary by biome, elevation, and moisture level.

In my git stash I have several other experiments I’d like to play with one of these days. I don’t plan to experiment more until I am helping another project that needs maps. It’s easy to dream up things people might need. It’s much more rewarding to work on the map generation when I know it’s being used in a game.

[Updated 2012-04-11 to clarify that “render to bitmap” then converts the elevation and moisture data into arrays, which are exported.]