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
IslandShapeclass, 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.]
19 comments:
Subscribe to:
Post Comments
(
Atom
)
two other possible approaches to generating terrain on the fly while still maintaining large scale structures:
1. You can keep a purely local approach if you are willing to generate the large scale structures based on a continuous mathematical function. If you have a function, say f(x), for placing mountains then it is easy to query this to find out where nearby mountains are, and build the rest of the terrain around them. This is the approach I'm taking with http://runway.countlessprojects.com/prototype/index.html?proceduralLevel
2. For a game like minecraft you don't need a purely local implementation because you're always filling out the edges of an existing map, so you can just build off them. (If you could teleport somewhere far away and then walk back this wouldn't work, of course)
I tried your mapgen, but when I save any bitmap its a .data file I cannot open with Paint. Call me a newb, just hoped to use ya gen for my conworld, but cant figure out how to save a map generated. Thanks.
Hi Duinnin,
Sorry — it's not a viewable bitmap. It's a 2048x2048 array of bytes (0-255 elevation or moisture) that you can use as tile data to generate your own bitmap. I'll edit the blog post to clarify. Sorry about that.
I do want to export PNG at some point; that's something I have on my to-do list.
I used your previous more simple map generator to generate big worlds to walk around in via a top down view, this was easy given that the map info was a multi dimensional array so I could simply scale my players position and get relative coordinates to draw, the only way I can see to do this with the new generator is to use the exported bitmap mytearray?
Am I being stupid? :D
Just to clarify, i'm quite happy with the as3 graphics rendering and would simply use this for the large scale scene. I tend to add my detail by tree placement and other objects.
This is AMAZING by the way :D
Hi Tom,
Yes, the exported byte array was meant to be all the map information you need, but it turns out to not be sufficient. In particular it doesn't contain the biome data. The overrides array is rather awkward.
This is something I hope to address in the next version. In theory you can create a large BitmapData and then use BitmapData.draw(this) to draw the sprite into it. I haven't tried this yet.
well, I have to say that this is a really interesting approach to making maps, but how can you get more detail from it?
To specify a little more, I'm really interesting in something like zooming in, to the level where you can see where each tree is places, like when you zoom in in google earth. I was thinking in something like nested voronoi graphs when you zoom in each individual cell will get its own array of mini voronoi inside it, so each point can become a tree position on a forest biome, or something like that, but I really don't know how to nest voronoi maps dynamically.
Hi Wins, yes, there are some ways to get more detail. In Realm of the Mad God, the authors used a noise function on top of the elevation/moisture from the polygon maps. With this noise function they added vegetation, smoothed the boundary between biomes, and created monster habitats. I've also experimented with warping the sampling function to create more interesting details. Nested voronoi as you suggest also has potential, as it creates a more even distribution of vegetation than a random noise function does. I've done some experiments but am not yet happy with any of my algorithms so I haven't published them yet. In practice, I suspect that the detail you need depends on the game, and I'm not working on a game that uses these maps…
Hi Amit, I was thinking in nested voronoi since, I'm doing a 3d map, where trees have more volume, so in a noise function is hard to define where a tree trunk goes, and the area that the tree covers, but with the voronoi, the trunk is the centroid and the leaves can be a radial area inside the voronoi poligon, which is easier to track, as perlin noise (or others), don't really work for placing volume trees, as the values not always go all the way to the top and back. I'll try to apply some of your techniques in my game and lets you know.
Wins: sounds interesting! Yes, I'd love to hear how it works out for you.
here is a little 3d test of the generation, had to tweak the elevation code since your ocean is always 0 and I need it to be lower than 0 to generate coast and the like, and my height gradient code still is not as good as yours, that't why I have ugly coast so far.
Here is a test with 15000 polys
http://tinypic.com/r/dvgcya/6
Winsp: looks cool!
ok old elevation code... is gone, had a lot of things that didn't worked well on 3d, also lakes are both flat water and deep in bottom, so, that broke the rivers also, due to not always having a downslope way to the ocean, moisture had to be tweeked also, and made the coast just on the edges as having an entire poly of coast was way to much, also added lake coast, and my plan is to add waterfalls, lava and roads next, but so far so good.
http://tinypic.com/r/14aevyd/6
well, all was going great until I started to make each pixel become 32 pixels, like a zoom in view to make more room, and well there is no way to add more detail without having to run the algo with lots more points on a bigger resolution image. On fBm you would normally just increase the octave count, and get a smaller rage of data, and thats like auto zoom in, in here, I haven't found a way to do something similar, any ideas?
Wins: what I had in mind was that the detail is not scale-independent, as you see in fractal based approaches, but instead that you'd use a different algorithm at a different scale. For Realm of the Mad God we used a vegetation algorithm that was quite different from the algorithms used for the main map. However we never zoomed in as far as you need to, so we didn't develop algorithms for that scale. I do want to experiment with this at some point but I also have so many other projects I want to work on :)
I enjoyed your map generation articles. Do you have any suggestions on how to ensure/force a balanced map?
For example, a 2 player world with both continents and islands. You probably wouldn't want one player to have all islands and the other player to have all continents as it could affect the balance between players (e.g. expansion of territory using islands theoretically would cost more than expansion of territories on a continent)
Thanks!
Hi Mike C,
For the maps I described here, started with the gameplay the map needed to support. In the game, new players start on the edges, fighting alone, and then as they work their way up, they converge onto a few central locations, where they fight in groups. From the gameplay requirements, I put constraints on the map generator: (1) the edges of the map have to be unreachable, (2) the center of the map should be where the hard monsters live, (3) there should be some straightforward ways to get from the easy to the hard areas, (4) the paths different players take should be roughly balanced. The resulting map had (1) water at the edges, (2) mountains in the center, (3) rivers and roads helping you find the way up the mountain, (4) constant slope from the beach to the mountaintop.
These gameplay requirements explain why the map is the way it is. You don't have local hills. You don't have variable slopes. You don't have multiple mountain ranges. You don't have cliffs or canyons. But a different game will end up with a different type of map.
I don't have specific advice for you but I'd suggest writing down a list of the gameplay requirements the map needs to support, then come up with the constraints on the map structure. It sounds like you might want to generate things in pairs (not only islands and continents, but any other resources like forests or water), so that both players end up with a similar resource. There might also be constraints around how far some things are from each other. Then experiment with the remaining freedom to arrange things differently for the two players while keeping the constraints that ensure fairness.
This is immensely fascinating. Great and elegant work.
My game engine of choice imports heightmaps for terrain, and it seems only a slight modification is required to achieve this.
Have you been able to implement this? If not I may take a stab at it.
Hi Anonymous,
Yes, the code supports exporting a 2048x2048 height map. You also may want the 2048x2048 moisture map. I have a version compiled here that has three additional export buttons. In the code, see the makeExport() function.
Post a Comment