I was drawing tile maps in Flash and found a cheap trick that improved the appearance of the maps, so I thought I'd share. Here's how I had been drawing the tile map:
In a bitmap-based graphics engine, you can smooth the edges of the tiles either by adding transition tiles (see this article or this article or this article) or by using a blending mask between adjacent tiles.
Flash, OpenGL, and DirectX are vector-based engines. The bitmap techniques still work, but there are new possibilities available. I'm drawing each square tile by filling a square polygon with a bitmap texture. The engine doesn't care that it's square; it works on any polygon. I'm taking advantage of this with what I call “vertex displacement”:
I look at the four tiles touching each vertex. If three of them are the same and the fourth is different, I move the vertex to expand the area of the three common tiles and shrink the area of the uncommon one. It's easier to see the effect with the polygon borders:
It turns out there are other fun things you can do with this trick. For example, a little bit of random noise on each vertex makes for a map that looks a little more hand drawn:
I've also used it to animate the boundary between the ocean and the beach. I added vertex displacement to my simple map generator; see the demo (Flash). Try changing the corner setting to adjust how much the corners get moved when three tiles are the same, and the random setting to adjust how much vertices get randomly moved. I have a separate demo (also Flash) to show the animated coastline.
The technique has its limitations. Terrain boundaries that don't fall on a 45° angle look wavy (see example). Some terrain types shouldn't meet in this way. And the biggest limitation is that it only applies when the terrain texture has no major features (such as trees, rocks, etc.). But it's a cheap enough trick that it's worth keeping in my toolbox.
Update: [2012-03-30] Also see Marching squares.
Labels: maps
Looks nice, but when theres a 1x1 area of sand, surrounded by grass, the sand be squezzed to much tinier tile.
Oh btw. finally a new Blog post from you :D
Yes, I agree, 1x1 areas get squeezed into tiny circles. I'm not sure if this is good or bad :-)
I haven't been blogging as much because I've been coding quite a bit on a new game map generator. The project is coming to an end and I'll have a blog post about it.
Nice to hear that, I'm also looking forward to that post ;)
That's a nice trick, it's not perfect but compare it to the original blocky map -- a huge improvement at a small cost! A related technique that is very simple has each tile's graphics bigger than the tile, and with some alpha variations or an irregular polygon it can yield smooth borders with no post-processing (if you don't mind a bit of overdraw). It only works if the borders don't look bad over the same tile type, which will eventually happen; so they can't have different colors, like shading.
About the wavy borders on odd angles, it's very hard to mask that; it's a problem with tile maps. But generating a tile-less map with arbitrary polygons would be a much harder task!
Jotaf, I love large improvements with small costs! :) I haven't tried the trick you described but I may for the next project.
My current map project / next blog post is about generating a tile-less map with polygons. Here's a preview: http://friendfeed.com/amitp/56e6eb85/sunday-afternoon-project-learning-about-blue
Wow awesome! You put the black dots in the center on purpose, so they looked like cells, right? :P
You say the 2nd iteration may not be needed, because most cells don't even change, but it seems to help a lot those rare pathological cases where cells are initially very close together; I think you should keep it :)
What's the next step? The cells' edges would make for some great spots to place roads and rivers. Also, are you planning on sub-dividing the cells once more to get one more level of detail?
Jotaf: the black dots are the seeds for the Voronoi step, but after Lloyd relaxation, they tend to be near the center, so it looks like cells :). I agree, I should keep the 2nd iteration to get rid of some of the leftover weird cases.
I placed rivers along the polygon edges and roads between polygon centers. I tried both edges and centers and found that rivers worked better on edges, both because edges are the topological “folds” (valleys and ridges) and also because the edges support more meandering. Roads worked better center-to-center, both because they should link up important points (which are the centers) and because they looked better crossing rivers than moving alongside them. Click on “Polygons” in this demo to see the placement of roads and rivers.
I'm not currently planning to subdivide the cells. I think it makes sense for some games. Fortune's algorithm should work for building Voronoi cells inside an existing Voronoi cell. However, I've been working on the maps for a few months now and am ready to finish up and move on to something else. If a future game needs the subdivision, I can come back to it, but for now, I want to clean up the code, make it available, and write a blog post about the project.
Hm, are those roads or isolines? ;) The demo looks pretty slick, a lot of game developers I know would be jealous :P (Myself included!)
My plans were for further subdivisions, eventually reaching the player's level of detail. There would be farms, houses around road intersections, and other medieval/fantasy stuff. I ended up integrating the same ideas into my current game project, though it defines arbitrary regions over tiles, instead of polygons (yes I wimped out!). It's a nice distraction from labwork and I spent waaay more time coding the map generator than unimportant stuff like, oh, the most bare-bones of all combat systems.
I really wasn't expecting that 3D view :D The "Blob" was also a nice touch, hehe.
The underlying code for roads in the new map generator is generic (supporting curved sections and intersections in any configuration), but the Realm of the Mad God authors wanted isolines so that's what I put in for now. :) The code is open source (MIT license) and hosted at github/amitp.
I think subdividing regions would be very nice! As wilderness areas get settled with farms, you'd want to subdivide the forests and grasslands. As agricultural areas get settled into towns, you'd want to subdivide to make houses, etc. Are you working on a roguelike?
I wanted to push myself to work with vector data for this project but I do miss tiles. I've tried making some features in the polygon map that turned out to be hard to make without tiles. The rivers are expressed in vector format, as a polyline, but anything I want to do that interacts with that river has been difficult. For example, placing boulders in the river, or making bridges that cross them, hasn't worked very well because I don't have a representation of the “interior” of the polyline.
In my previous big project (Simblob) I spent way too much time (years) working on maps and never got around to combat. :( This time I've put an informal time limit on myself of three months, and I have a little over a week left. I'm trying to do more small projects to avoid getting stuck on one giant never ending project.
Yes it's a roguelike, how did you know? :D
My previous game had also been eaten by the dreaded bloatmonster (and so did several years of my game-dev-life, although I learned a lot) so I decided to scale back too!
I switched to a high productivity environment (python and libtcod), and set on the following plan: I'd first make my game playable in a small setting, a subset of what could be a much larger game world, and only think about bigger things after that. So far so good! :) I still spent a lot of time on the maps but IMO they look very nice :P Of course, this is all talk, since I've been experimenting with combat systems for a few weeks and I'm still not happy with them; so I guess I haven't escaped the monster yet!
About vectors, it's hard because you can't borrow a lot of the concepts from tiles. How do you define neighbors? With tiles it's easy, here... you have to find a custom solution for every situation. It's kinda like using a CAD program; you have a rough layout in your mind but then everything has to be defined in terms of tangents, intersections, you simply can't fake anything!
I'd still love to do it, it would surely be an epic feat, but when I considered these algorithms I really was (and still am) in a state of mind where I just wanna finish something I can be proud of and show off for my many years in game dev :D
(and not let it interfere with the day job/PhD by the way :P )
By the way, I really admire the folks on tig-source and other communities, who output lots of little games every year. Some day I'll give that a shot, but for now the slow hogging of another epic roguelike is just the perfect thing to work on on my spare time ;)
I've had good luck starting small and growing, instead of starting big. I wish you luck :-)
As far as vectors go, take a look at this diagram. You can see that polygons have neighbors, edges, corners, just like the squares/hexagons/triangles in a grid have. It's just that they don't all have the same number of neighbors. Sometimes variable sizes get in the way (for example, artwork), but many algorithms can work with the abstract graph structure without using the actual geometric layout. This is one of the topics I'm writing up for the map blog post.
Looking forward to it; it seems like you solved many problems, which makes vectors an attractive approach again :)
Post a Comment