In the previous blog posts (part 1 and part 2), I described generating random polygonal maps with elevation, moisture, biomes, and rivers. For some games, those maps are sufficient. However, in other games I want to hide the polygon structure. In this blog post I'll describe how to render the polygons into a game map that doesn't look polygonal, and conclude with the demo and source code.
The full article is here. There's also a demo and source code.
Noisy Edges
Recall from earlier that there are two graphs: one for Voronoi
corners (1, 2 in the diagram below) and edges (blue lines), and
one for polycon centers (A, B) and Delaunay edges (red
lines) between them:
I wanted to add some “noise” to the the straight lines. I tried making them move randomly, but sometimes lines would cross, and I realized I needed to constrain them so that they would never cross each other. The second thing I wanted was to make sure that the lines had as much space to wander as possible.
I realized that points A, 1, B, and 2 form a quadrilateral, and
I could constrain the wanderings of the line segment to that quadrilateral:
I further divided the quadrilateral into four quadrilaterals. Two were usable for the red (Delaunay) edge and two for the blue (Voronoi) edge. As long as the lines stayed within their allocated space and met in the center, they'd never cross each other. That takes care of constraining them.
The entire map can be divided up into these quadrilateral regions, with no space left over:
That ensures that the noisy lines aren't constrained any more than necessary. (I wonder if these quadrilaterals would be useful for game mechanics.)
I can use any noisy line algorithm that fits within these constraints. I decided to subdivide the quadrilaterals recursively and stitch line segments together within the small quadrilaterals into a complete edge. The result is here:
The noisiness is tunable, and I have examples at segment size 7, segment size 4, and segment size 1. In the map demo I use segment size 1 for rivers and coastlines, 3 where biomes meet, and 10 elsewhere.
More noise
I'm generally a fan of noise in game art, and wanted to add a little bit of noise to these maps as well. In a real game map the noise might reflect vegetation or small variations in terrain. In the demo I just filled the screen with a random noise texture, and smoothed the colors between adjacent polygons:
However, with a bit more random noise, we can generate this (described in the full article):
Here's a rendering with 16,000 polygons, noisy edges, a noise texture overlay, and simple lighting:
Demo
I wrote a Flash demo to explore the generated maps:
The simplest way to explore the maps is to click Random and the various View options.
In a shape number like 85882-3, 85882 chooses the overall island
shape and 3 is the random number seed for the details (random points,
noisy edges, rivers, lava). You can type in a shape number and press
Return to generate that map. The demo also shows some unfinished
features that may be useful for some games: lava, roads, and
watersheds.
Source
I've placed the Actionscript source under the MIT license; it's available on github. There's an overview page describing what's in these blog posts, along with notes about the code. I don't expect that the code will be immediately useful to anyone, but it might be a useful starting point if you'd like to use these techniques for making your own game maps. The diagrams are built with 300 polygons, the demo uses 2000, and the code can go much higher, although I've not tried above 16,000.
If you find the ideas or code useful, I'd love to hear about it!
Update: [2010-09-22] I added a noisier rendering, which is described in the full article.
Very interesting and great fun.
Even by your high standards, this is a particularly good blog series.
Thanks Ben!
Very nice demo! Love it
Blew my mind, thanks for sharing Amit and thanks for sharing the code, too.
Looks great!
Awesome article series!
/Pär
Wow incredible work and love that you have the code on github. Can't wait to trace the code some and see the magic behind this. awesome awesome awesome!
This is really cool.
One question though, did you play a lot of super mario? Why I ask? Well, check the map I got when playing around with it: http://yfrog.com/mhislandkj
:)
Tetsu, no, it's not from Super Mario. It's my personal “blob” logo. I've used it for 23 years, and I sometimes embed it into the projects I work on. :) For example, see this unfinished project for generating facial expressions.
Facinating read, couldn't beleive how great the results were both visually and in terms of the random realistic island shapes and features. Two things i'd like to see in the future is dynamic loading of the island, or blitting of the polygons this way the island could be used for example in a top down game really zooming to make gigantic worlds to explore. More complicated road networks and towns.
The river/ moistore system is really impressive kudos.
I checked out the source but was unable to run it from the flash cs5 ide, no compile errors but the demo seems to get stop at "shaping map" the program responds and buttons can be clicked but the mp doesn't generate, I have all the extra classes, and files.
Thanks and good work!
Thanks Thorgaming!
As far as dynamic generation, one big difference between this approach and the usual “infinite dynamic world” approaches is that the infinite dynamic worlds have features that depend entirely on local properties, whereas a lot of what makes these maps interestins it that features depend on global properties like mountain ranges, rivers, and moisture. (I might be misunderstanding your question)
To generate these maps dynamically I think a hierarchical approach would work better. At the high level, generate all the polygons, but don't render them to a bitmap yet. In the demo there are only 2000 polygons. That takes almost no space to store. The noisy edge algorithm is deterministic, so you can generate it again with only the random seed. The noise texture can also be deterministic. In the full article there's a mention of a more interesting random noise approach using perlin noise, but that's also deterministic. So I think it'd be possible to generate the polygon map alone, and then render a portion of it to a bitmap later, without having to store the entire detailed bitmap. I didn't pursue this because I think it's often game specific and I wanted to wait until I had a game that needed it before working on it.
Voronoi polygons can also be generated within an existing Voronoi polygon. I haven't explored this but I think it'd be a way to add to the hierarchy in a way that allows dynamically expanding the areas that players are actually visiting.
I'd like to work on road networks and towns sometime. I tried a few ideas but wasn't happy with the results. I decided not to pursue it in this project because I suspect it'll depend on the kind of game I'm working on, and I don't have a game in mind yet. For example, the way the town develops might depend on the game economy, or the resources (ore, wood, gems, etc.) that the game simulates. See a screenshot here of one of my failed experiments to make towns.
I'm not sure what might be failing for you in cs5. I compiled it with mxmlc (command line compiler). If you get a stack trace with information, let me know and I'll investigate. Thanks!
Haha i wouldn't call that a failed attempt! looks pretty cool to me! perhaps it would look better if the houses etc were more sparse.
I got the source working for some reason
commandExecute("Shaping map...",
function():void {
newIsland(type);
});
none of the commands like this ran (should have traced it before I asked)
However interesting your response was! reading my question back i wasn't clear. I designed this as more of an experiment a while back http://www.thorgaming.com/games/7615/thor-city.html you can drive around an endless city, basically the physics objects and background are simply mirrored as you pass from bitmap to bitmap more due to lazyness of not wanting to design a full city!
As soon as i saw you islands i couldn't help but think how cool it would be to drive/ fly /sail around it. Now to use the maps in this method it would need to be MASSIVE, and thus i assume would need to be loaded in chunks (forgive me if this is already a feature) which made me think that any (zoomed in) use of the map would benefit from a built in feature like this.
transport tycoon is pretty much my all time favourite game and this type of simulation is suited amazingly to your maps but i really like the idea of using them in a more action based genre.
Thanks again for the excellent articles and your considered reply, keep up this fine work!
Tom
Hi Tom,
Thanks — the commandExecute commands should have worked, although I admit that it's a complete last minute hack that's there only to keep the Flash player responsive while the map is being generated. :(
Thor City is fun! I eventually got cornered by the police while I was in a race. :)
I agree that large maps could benefit from producing chunks at a time. In the case of Realm of the Mad God, the entire map is rendered to 2048 x 2048 tiles on the server, and then the server sends chunks to the client, which renders into roughly a huge 100,000 x 100,000 pixel map. Of course it only renders small chunks at a time. The chunking algorithm varies by game though. In their case they send square sections to the client, but in other games you might want to send polygonal areas, or areas that reflect the game levels. Since this, and so many other things, are game specific, I decided to release this map generator more as a starting point, not as a complete project that someone can drop into their game. If I work on a game someday I'll have to come back to this and add the parts I need for that game.
Thank you for writing this article! It's a really useful overview and insight into terrain creation. I noticed that all your terrains are essentially mountainous - have you thought of ways in smoothing it out, e.g. into plains or rolling hills?
Hi Jevon — thanks! Yes, the simplest mapping from distance_from_cost to elevation was linear. My intent for this project was to divide the world into biomes, but not worry too much about the actual elevation. However, if you want to have more flat areas, you can use (distance_from_coast)^2 or other mappings. That will flatten the medium elevations into low elevations, and stretch the higher elevations out into steep mountain sides.
Wow, great article - I'm really impressed. Thank you for sharing this!
Hey, Really cool stuff, I was wondering if there is a python version of this??
I'd love to port this to C++ or Python. I just haven't found a nice Voronoi library like as3delaunay (I admit I haven't looked very hard). I need a freely distributable Voronoi library that will output the underlying structure, not only the locations of points.
Note that your noisy line rendering analysis assumes that the dual edges always cross each other (so that the quadrilateral is convex).
But this doesn't seem to be guaranteed by the algorithm, in fact you can see one case where it's not satisified in this example: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/voronoi-and-delaunay.png
(Towards the bottom, in the middle.)
nothings: that's a good catch! Yes, the quadrilateral isn't always convex. The code anticipates this problem and handles it correctly, but the article doesn't make it clear. I say that I divide the quadrilateral but I don't say how. The center point is the midpoint of the Voronoi edge (1-2), *not* the Delaunay edge (A-B).
You can see an example of this near x=270 y=280 in this diagram: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/quad-markings.png . Note how odd that area looks. It almost looks like 2 blue triangles instead of 2 blue quadrilaterals. It's the midpoint between the two blue dots but not the midpoint between the two red dots.
Thanks for pointing this out! I should clarify the algorithm in the article.
nothings: Also note that the problem already exists without noisy edges. You can't draw roads or other features along the red Delaunay edges directly. Anything going from one polygon to another must pass through the Voronoi edge. I use the midpoint of that edge for several map features, including the roads shown in http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/roads-zoomed.png .
Amazing series of articles. These and the ones about using height maps.
How would you handle carving caves on the sides of mountains in either type of map generator?
Thanks Daniel! I start with the needs of each game and try to design a map generator specific to those needs. In this particular game we had some caves but they weren't in the sides of mountains, but instead they were open holes in the ground, so we placed those in a separate step after the terrain step was complete. Also, the polygon centers turned out to be useful places to add features (quests, buildings, etc.) that were spaced out evenly across the map.
Post a Comment