Map Generator Algorithms: Polygon Map and Caves

     A couple of months ago I posted a blog entry about my procedural map and maze generators. I find procedurally generated content interesting because the results are can often be unique and unexpected. these results are usually based on a few very simple rules, usually inspired by mathematically geometry or natural phenomenon. In the pursuit of creating better generators I am always trying to learn new techniques. Recently I came across a couple of algorithms on the internet that I feel like talking about. They are similar in intention to my map and maze generators but use different techniques and achieve a much more natural result.

Map Generator Using Voronoi Polygons

     The first algorithm is a map generator based on Voronoi polygons rather than on square tiles. A Voronoi diagram is created by randomly placing points and creating polygons that have edges are no more than halfway to any other point. The most common way of generating a Voronoi diagram is using Fortune's Algorithm. The advantage of using polygons over tiles is that they produce a much more random and natural looking shape.

A Voronoi Diagram after 2 applications of Lloyd Relaxation

     After the Voronoi diagram is created the algorithm fills in the map by defining some tiles as land and the rest as water. It then calculates elevation based on the distance from the coast. It places rivers randomly starting in the higher elevations and traveling along edges downward to the ocean. Then it calculates the temperature and moisture level, using the height map and proximity to a river, which it uses to assign each polygon a biome. [1]

     The writer of this algorithm posted a flash demo, and there are source code examples in various languages listed near the bottom of the article.

The final result using 16,000 polygons [1]

     There are a couple aspects of this algorithm that I find interesting. Firstly, I like the idea of using Voronoi diagrams. Before I read about this I had never heard of Voronoi diagrams and now that I now about them I can think of several application that they they might be suitable for, such as the generating streets in a city. Secondly, I like the way that this algorithm was able to generate rivers, and this seems to be made possible by the use of Voronoi diagrams. Had I tried a similar technique in my generator I would probably have ended up with ugly square shaped rivers. I believe this strategy has some clear advantages over the technique that I tried and I would like to try to implement this in the future.

     Well I find this technique works generally well I have also noticed a few problems. One problem is that the algorithm places all of the mountains in the center of the land mass and then has an even slope from the mountains to the coast. While this looks good for some small islands, in general mountains are not placed like this, for example the island of Oahu has mountains on the two sides of the island with a flat area in the middle. Another issue that I find common in most map generators is that they look good from a distance but lack details like sharp cliff faces and jagged peaks. Well this algorithm is a good start, these issues make me want to consider improvements.

A terrain map of Oahu from Google Maps

     I have thought of a couple of map making strategies, based on natural phenomenon, that I believe could be used to improve this algorithm. The first is faulting or the simulation of plate tectonics. A possible faulting algorithm would define fault lines and plates, these areas would then be moved slightly to make the edges discontinuous. I believe faulting could be used to produce features like cliffs.

     Another technique is based on erosion and volcanic eruptions. The map would start with a randomly generated landmass and then randomly drop water on points and have these water drops move down hill toward water. This is similar to how rivers already work in this simulation, with the extension that overtime the rivers cause the steep edges to lower and the shallower edges to rise. This simulates how fast moving water erodes ground which slow moving water deposits. I believe this strategy would lead to steep valleys, canyons and smooth plains. I also believe that volcanic eruptions could be simulated in a similar way.

Cave Generator

     I also read about another algorithm for creating caves. I find this algorithm interesting because it is similar to my algorithm for generating mazes but using a completely different technique.

     The algorithm is very simple and is based on several agents that act as miners, digging out a tunnel. The algorithm starts with a single miner. The miner moves randomly to an uncleared tile and clears that tile. As it moves it randomly spawns additional miners. A miner dies when it is completely surrounded by empty tiles, unless there is only a single miner left in which case it continues to move randomly. The article does not mention an obvious stopping point but say that they stopped the algorithm after 400 miners had died. Once the algorithm has stopped it removes small unmined fragments and then adds water to the empty bottom tiles purely for aesthetic effect. [2]

     The writer of this article also posted a flash demo.
 

The final result of the Algorithm [2]

     There are several things that I like about this algorithm. Firstly it produces very natural looking cave maps. On a side node, the water reminds me of the movie Sanctum which I saw recently. I also like that this algorithm is guaranteed to produce connected tunnels and thus would be useful for using in a game.

     There are a couple of things that could be improved with this algorithm. The first is that it would be nice if the algorithm could be modified to produce longer more dispersed tunnels. Also, the algorithm is described as being on the vertical plane but the minors ignore gravity and the result is a mine that looks somewhat natural but if you were trying to generate a mine that looked like it was built by miners one would probably want to take gravity into account.

     There are a couple of improvements that I would like to try with this algorithm. First, I think this would be interesting to try in 3 dimensions since adding an extra dimension would be trivial. Secondly, in nature many mines are carved out by water, so using technique based on erosion might also produce natural looking caves. Lastly, adding the concept of minerals could be used to direct the miners in a certain direction giving the designer some loose control over the random cave.

     So those are two procedural generator that show that complex scenes can be constructed using some simple rules. I am very much interesting in trying to implemented a version of these algorithms. At the moment I am very busy with term projects and exams, but will hopefully have some free time after. Also, In the future as I find more interesting algorithms I will write a similar analysis of them and tag all of my procedural generation articles so they are easily to distinguish from my other articles.

Refereces

[1] Amit Patel. "Polygonal Map Generation for Games" Internet: http://www-cs-students.stanford.edu/%7Eamitp/game-programming/polygon-map-generation/, Sept 4, 2010 [April 7, 2012].

[2] Noel Berry. "Procedural Generation – The Caves" Internet: http://www.noelberry.ca/2011/04/procedural-generation-the-caves/, April 19, 2011 [April 7, 2012].

Character State Management

   When making a game how should the program decide when the player should be walking? Well, maybe if they press the arrow keys. But, then what if the character is crouching and you would like the arrow keys to make them crawl. Also, what if you want the character to jump when the up button is pressed but only if the character is standing and not walking. One way is to have a variable for jump and another for walk and one for crouch, and by using a large combinations of if-statements you can determine the animation that should be played.

   Anyone that has followed this way of thinking before will know that eventually this if-statement will get large and the number of state related variables grows quickly. Once the number of variables becomes too large, handling the various exceptional cases becomes nearly impossible.

   When I started I too faced this problem, however I have since found a much more elegant solution. I have found that all of these states can be described as a finite state machine. Game developers can benefit from this approach by clearly defining which states can transition to others and by abstracting the transition logic away from keyboard inputs.

   To start a programmer needs to describe a simple generic finite state machine. A finite state machine consists of a graph of nodes representing states and directed edges representing actions. The state machine keeps track of its current state and when it receives an action it move to a new state only if it has an out going edge with the same action. Then, Once we have a generic finite state machine we simply draw whatever animation we want to associate with a particular state.

   One thing to note in the design of my state machines is that I never make the action refer to user inputs. This is because not all of the characters in my game are controlled by the player, so for non-player characters it does not sense to think of actions as user inputs. This also gives me the flexibility to change the inputs later if I want to run it on another platform, like the Xbox360 which has buttons and joysticks rather than a mouse and keyboard.

A partial character state diagram from my RPG game engine

   I have used this technique in my RPG game engine and have found it extremely elegant. I no longer need massive if statements for determining what character animation should be drawn. I have also found it has enabled me to have more complicated character actions, like action combos, that I used to find very difficult to program.

Book Review: The Animators Survival Kit

     Back when I was working on my animation project, one of my group members recommended a book to me. Unfortunately, he recommended it to me near the end of the project when the deadline was fast approaching and I did not have time to read it. I remembered that book the other day while I was at the university library researching for a history project. I searched on the library's website and found that they had a copy of the book so I decided to read some of it.

    The book is called The Animators Survival Kit and was written by Richard Williams, the animator behind the film "Who Framed Roger Rabit?"[1]

    I found this book interesting because it explained some of the techniques used by traditional animators. Many of these techniques, such as tweening, are now done automatically by computer animation software. Even though these processes are now automated, I feel that understanding the workflow and techniques of traditional animators can be useful to improve digital animations and make them more expressive.

    One process digital animators often take for granted is called tweening. In traditional animation, tweening was the process of creating the frames in between the major actions. In digital animation software the in-between frames are inferred using mathematical interpolation. Often beginner animators will rely too heavily on the animation software to generate the correct in-between frames and as a result there animations look artificial.

    One thing that I never realized about tweening is that traditional animators would draw the in-between frames halfway between two frames they had already drawn. This is because it is easier for animators to imagine what the frame should look like if it is exactly half way rather than a third of the way to the next frame. Then they would draw further in-between frames to make the animation slower or smoother.[1]

    The book also explains about how to make characters more expressive and have display their personality through there actions. The most fundamental action that many animators overlook is how the character walks. The book probably has around one hundred pages just dealing with developing the walk cycle.

    Another technique the book explains to make the characters more expressive is to design their actions to have three phases. In the first phase, called the anticipation, we want the character to make a motion that sets the scene for the major action. In the second phase the character preforms the major action. The final phase is the result where we see the outcome of the major action.[1] For example consider a cartoon character hitting another character with an over sized hammer. The anticipation would be the character lifting the hammer over their head, the action would be them quickly slamming it down and the result would be the character lifting the hammer to reveal the other character has been flattened like a pancake.

    I have enjoyed reading this book and hope to try some of these techniques when I get some free time. I definitely recommend it to anyone interested in learning more about animation and the workflow of traditional animators.

References
[1] Richard Williams, Animators Survival Kit, Expanded ed. London, Faber And Faber Ltd, 2009.

Graphics Software: Inkscape

     Over the next couple weeks I am going to write a couple blog entries about the computer graphics applications that I have used. I have been using these applications for a number of years and have become quite skilled with them. I will explain what they do, why I like them so much and how I have used them. All of these programs are open source and free to download.

     The first program I am going to talk about is Inkscape, an open source vector graphics application. It is used to produce a type of art known as Scaleable Vector Graphics (SVG). SVG differs from pixel-based graphics because it represents objects using shapes. Well pixel-based graphics usually store the value of each pixel in a large array, SVG stores primitive shapes in an XML format. SVG's biggest advantage is that there is no loss of quality when scaling an image. SVG has grown in popularity over the past few years because it has been supported by modern internet browsers and improves consistency across devices with different display resolutions such as mobile phones.

     I have tried many vector graphics applications but I have found Inkscape to be the best. These days it is my first choice for creating quick graphics. I use it to create most of the graphics for my games and I even like to use it to create diagrams for reports. I have also found it to be useful for planning website layouts and picking color schemes.

Notice the repeated elements and primitive shapes I used to create this complex scene

      What makes it so useful is that creating an object out of several primitive shapes is very intuitive. Inkscape provides all of the standard Constructive Solid Geometry (CSG) functions that allow you do such operations as taking the union or intersection of shapes. It is also easy to duplicate and reuse pieces of objects to help create more complex objects. For example, when creating a house you might start by designing one of the windows using primitive shapes, once you have a single window you can group the primitive shapes and then copy and paste the window as many times as you need. I often save objects that I have created so that I can reuse them in future projects.

Three diagrams using difference shading techniques to add depth.
Plain (Left), shadow (Center), Gradient and Shine (Right)

     I have also found that the gradient and blur tools are very useful for adding depth to any image and make it eye-catching. I have created a quick example diagram in the image above. I have added a shadow, gradient and a bit of a shine to give the graph some depth. These effects are so easy to do in Inkscape and make the image much more eye-catching.

     In many ways Inkscape reminds me of when I used to use Flash to create animations. Although I find Inkscape has more features and is more intuitive than flash, it does not have the animation tools that Flash had. Unfortunately, I have not been able to find another vector animation software that even comes close to Flash. Maybe one day I have will make one myself.

     Inkscape is definitely one of my favourite open source software applications and I am constantly recommending it. For me it is probably tied with blender in my list of favourite open source graphics applications, since I find Inkscape more useful on a daily basis, whereas blender is amazing because it is so powerful. Later this week I will probably talk more about why I like Blender. In the meantime, if you are interested you can checkout a tutorial video I created explaining my process for creating graphics using Inkscape.

Last Summer at SIGGRAPH

    Last summer I heard from my computer animation instructor that SIGGRAPH was coming to Vancouver. SIGGRAPH is the largest computer graphics conference in north America and this is the first time that it was being held outside of the US.

    Since I am really interested in computer graphics I thought it would be interesting to go. However, tickets to the conference are very expensive. Luckily, through my connections with the Game Developers Club I was able to get a ticket to the exhibition part of the conference.

    So that morning I took the train downtown to the convention center, not knowing what to expect since I had never been to anything like this before. At the exhibition all of the well known companies that had anything to do with computer graphics were there. There were large booths with people giving demos of their products and computer monitors everywhere playing videos. Its hard to put into words just how exciting it was for me. Basically, everything that I am interested in under one roof.

There were a few technologies that seemed to be a focal point. 3D printing was a big one, and there were several different companies showing off things they had printed in their 3D printers. Motion capture was also big, there were several booths with break dancers and ballet dancers controlling characters on a screen simply by dancing.

The biggest booths were those of the big name 3D modeling programs and pretty much all day they had guys giving demos where they would making some really cool 3D model using their program. They made it look so easy, and I spent hours mezmerized by their skills,  its a shame the software is more then I will ever be able to afford. Speaking of which, Blender also had a booth there, it was more modest though and there was not much to see.

    My favourite thing I got to try at SIGGRAPH though was a virtual reality demo. I got to put on this head set that had screens for each eye, so the image that you were looking at was in stereoscopic 3D. It also had four cameras mounted on poles in a square that you stood inside and when you moved the cameras tracked your movement and you would appear to move in the simulation you were viewing. The scene I got to try looked like the interior of an apartment. It was the most realistic simulation I have ever experienced, because of the 3D effect everything looked so real, and when I moved or turned my head the same thing happened in the simulation, and there was no noticeable delay.

    SIGGRAPH was really interesting and I am glad I was able to go. Part of the reason I am writing this blog entry now is that I recently heard SIGGRAPH will be coming back to Vancouver in 2014.

Procedural Maze Generator

Part of a Generated Maze

In my last blog entry I talked about my map generator. Shortly after making that generator I created a second one for generating mazes.

Mazes are a very fundamental part of video games. Most maps that the player actually plays through, be it a building, forest or cave, is really just a maze in disguise.

Part of a Maze with Multiple Solutions

The maze generation algorithm I choose is called the recursive subdivision algorithm. There are several different algorithms to choose from but this one seem the best for my needs since it could create a maze with hallways and rooms of varying sizes.

The algorithm is simple: Start with a rectangle, divide the rectangle in half with a wall and leave a gap or doorway somewhere along that wall. Then take each of the half rectangles created by this division and recursively divide them. Continue until the rectangle is the desired size.

A Maze with Wider Doors and Walls

This algorithm has many ways that it can be controlled to create different types of mazes. One way is to control the number of doors in each wall. If every wall has one door then the maze will have only one correct solution. If the walls can have more than one door the maze will have multiple solutions.

The most important part for me was the ability to control the size of the hallways and rooms. To create rectangular rooms I set it so that it would stop dividing rooms when they were between a certain size. To create long hallways, I set the width of the walls to be greater than one.

This algorithm is just a proof of concept for the moment, but I hope one day to use it along with my map generator to generate levels for a game.

Procedural Map Generator

 

    You might have wondered what inspired the title of my blog. It actually comes from a procedural map generator that I wrote two summers ago. It only took me one afternoon to write it and yet it can generate millions of unique maps in a very short time. It is based on two well know algorithms, Perlin Noise and A*.

    Procedurally generated content is a topic that I was particularly interested in at the time. I was fascinated by how you could write a quick program that produced nearly infinite meaningful combinations based on a few simple rules. One of my earlier projects was a procedural riddle generator which used template sentences and then inserted words of the right category to form a sentence that sounded like the question part of a riddle. Most of the time the riddles were nonsensical but often they were funny.

    The goal of the procedural map generator project was to create a map that could be used as a high level representation of a role playing style video game. The world would contain towns and the player would need to travel along pathways to get between the towns. The towns would be ordered so that the player visits the towns in order. The pathways would need to have ordering also, so that obstacles could be placed between towns to prevent the player from traveling to them out of order.

Example of Perlin Noise

    To create most of the natural qualities of the world I have used perlin noise. Perlin noise creates a set of random numbers that have several local maximum and minimum values with a smooth gradient in between. If we create a 2D set of perlin noise and render these values as a black and white image we get something that looks very similar to a topographical map. Using such a map I can set a threshold value where any point less than the threshold is water and the rest is land. Using another two thresholds we can produce a map with deep water and mountains. Forests and deserts are placed using two newly generated sets of noise since they are not depended on terrain height.
 


     After I had generated the natural landscape I needed to add in the towns and road. The towns I simply added randomly, making sure that they were not placed on water and that they were at least a minimum distance apart. Then to connect the towns I used the A* path finding algorithm to calculate a least cost path between two cities, which I repeated until all of the cities were connected. It is important to note that the least cost path is not the shortest path since the shortest path might make the road cut through a large body of water or a large mountain range. Instead I assigned costs to different types of tiles with grass having a low cost and mountains and water having a high cost. As a result, roads generally travel around water and mountains unless they have no other choice or the alternative route is much longer.

A map generated using the algorithm

    Obviously this is a very simple algorithm and can easily be improved on. One feature I would be interested in adding is rivers, rivers generally travel from high land to low land so a hill climbing algorithm might be a possible solution. I have also though of adding the concept of resources, such as water sources, minerals, lumber, etc. I could then change the locations of towns to be in areas close to resources. Climate and weather are properties I could also try to simulate to have more naturally placed deserts and wetlands.

    In conclusion, this map generator was very simple to write yet produces something that seems very creative in a very short amount of time. Hopefully this gives a better idea of why I choose the blog title, "worlds per minute", especially considering that this was only the first in a series of projects that I am still currently working on that have the goal of creating a large and dynamic virtual world in a very short amount of time.

Computer Animation Project

This past summer I took an animation course at university. The main component of this course was a group project to make an animated short film. The only requirement was that it had to be roughly 5 minutes long. This project took up the majority of my summer and was a lot of difficult and time consuming work but was extremely fun and I really enjoyed it.

Our group created the animation using an open source 3D modeling program called Blender. I had experimented with this software a number of times before the course but had never created anything nearly as complicated. Since I had used this software previously, and using it was not covered as part of the course, I took on the role of expert and taught the other members of my group. And this was no easy task, Blender is a very complicated and powerful piece of software. What made this assignment more difficult was that even though the course was a computer science course, creating an animation is more about art than anything else. Luckily, we had a couple of artistic computer science students in our group.

Planning sketches and the finished character

There are many steps required to make such an animation. We started with several planning meetings where we developed a rough storyboard, characters and setting. We then took the sketches of the characters and scenery objects and created polygonal models of them using Blender. Then we created textures to overlay onto the characters to add detail. We created some of these texture ourselves, such as the hieroglyphics and the details of the characters. For other textures, like the sand and rocks, we used stock photos from the internet.

The model and skeleton of our cat character

Now that we had finished the models for our characters and scenes we next had to animate these models. To animate the characters we added a virtual skeleton which was connected to the model. By adjusting the skeleton we could pose the character. And so to create the complete animation we just had to pose the characters, camera and objects in each key frame. Key frames are a the important frames, and a frame is just the name for a single image. By defining the positions and orientations of objects in the key frames, Blender is able to interpolate to get the positions and orientations of the in between frames.

A rendered scene with lights and fire

The most time consuming part of this project was when we started to render our final animation. Rendering is the process of drawing a frame. The time consuming part is calculating all of the lighting, shadows and other special effects like motion blur or depth of field. Some of our more complicated scenes took a couple minutes for each frame to be rendered. And when you consider that our animation is 24 frames per second and roughly 5 minutes, we probably rendered roughly 7000 frames. Rendering was still in progress on the last two days before the due date. It was after most students had finished exams so we found a relatively empty computer lab and rendered segments of our animation on up to twenty computers at once. Even this took a long time, but remarkably we managed to finish and then add sound effects before the deadline.

What I just explained is only a brief summary of how we spent the majority of our summer creating this animation. It is probably hard for anyone who has never worked on such a project to understand the amount of work we had to do just to make 5 minutes of animation. However, I have stayed away from some of the more technical details to keep this article from getting too long. I may talk about some of the details in a future blog entry. In closing, watch the video if you have a chance, its at the top of the article.