May Update

     After a short break I have decided to post a new blog update to let you know what I am up to at the moment. I had a couple weeks off from school but have now started the summer semester.

Mobile Course
     I mentioned in a previous blog post that I was going to be taking a special course on mobile applications over the summer. I am now a couple of weeks into that course and working hard on course projects. The course project I am working on is an attempt to improve location detection around campus based on the router a mobile device has connected to. Our goal is to improve on GPS which is not as accurate indoors and cannot accurately differentiate between different floors in a build. We hope to eventually use this technology to provide context specific information to mobile users in various different applications.

RPG Project
     Another update I have is related to my RPG game project. I have posted another YouTube video showcasing some of the new features. Unfortunately, due to my busy schedule this summer I may not have much time to add more to it any time soon.
     Also, I feel I have hit a roadblock with this project. I have reached a point where my engine has enough features for me to start making a game, but I lack a clear vision for what I want the game to be about, and what the story will be. This is a problem I have come across with many of my previous projects and is why I have never been able to take my project to the point of completion. This is something I hope to think about over the next couple months and try to develop solutions for, while at the same time improving and adding to the existing features of my engine.

End of Semester

     This is the last blog entry I will post for the spring semester. I mentioned back in February that I had created this blog for a technical writing course that I have been taking at university. The goal was to write 26 blog entries by April 11th, and surprising I have achieved the goal. Over the past four months I have posted articles about my projects and topics that interest me related to graphics and games. There were many times during the semester where I was either busy with other courses or simply had trouble thinking up interesting topics to write about. However, I was eventually able to find a good routine and managed to get all of my blog entries written and posted.

     I had several goals that I established when I started writing this blog. The most fundamental goal was obviously to get a mark in a course. However, I tried to think of this assignment more as a way of improving my writing and experiencing what it would be like to write regular blog entries. I have yet to go back and read some of my first entries to see I have improved but I definitely found myself proofreading each blog entry several times before I posted it, keeping in mind the rules of clear writing that I learned in the course.

     Another goal that I had with this blog was to practice documenting some of my interesting programming projects. At the beginning of the semester I wrote blog entries about my game projects and more recently I have been explaining some of the interesting features I have been adding to my most recent game project during the semester. I find this a good thing to practice because while I have a good understanding of the projects that I have worked on it is important that I can clearly describe these projects to other people. I still feel that I have some trouble in this area but practicing through blogging is definitely helping.

     During the semester I also tried to use this blog as a way of putting some of my thoughts into writing, such as when I tried to write about what I did and didn't like in a particular game or algorithm. I find this was helpful because while I have often thought about this it does not become as solid in my mind until I put it into words. My hope is that if I continue to do this I will find it easier to answer these kinds of questions during future job interviews.

     While this blog project may be over, I still have exams before my semester officially ends. After my exams are over I will have a couple weeks vacation and then I am right back to school for the summer. Since this blog will probably be checked for marking over the next couple weeks I wont post any more blog entries for a while. However I have found this blog very useful and I hope to continue this blog over the summer with the commitment to at least 1 blog entry a week and no more than 1 a day.

     I hope you have enjoyed reading my blog as much as I have enjoyed writing it! Have a good Summer!

I created this beach scene back in 2010 using the 3D modeling program Blender

Long Weekend History Project

     I had originally planned on posting a blog entry about my game engine however I have simply been too busy working on my other homework projects this weekend. Instead I think I will talk a bit about that homework project, which I am writing for a non-computer science course.

     This semester at university I have been taking Artificial Intelligence, Software Engineering, Technical Writing and History of England. The first three courses are computer science courses and the third is a History course I am taking to complete my last humanities credit for graduation.

     I decided that taking a history course would be a fun way to get this last credit. I had taken a previous history course, history of modern Europe, a couple of semesters ago which I also really enjoyed. The history course I am currently taking covers the History of England starting from prehistory all the way up to the year 2000. Covering such a long time period over the course of 13 weeks has meant the course covers only a brief overview, but it has given me exposure to a wide range of topics. I am partly interested in English history because I have hopes of one day traveling to England, and by learning more about the past I will appreciate it more when I finally do travel.

A map I created for the project

     This weekend I have spent most of my time working on my end of term project which is an analysis of history books written for children. I had to select two children's history books and compare them with two contemporary scholarly sources. As well as comparing them I also had to use what I learned from the sources to write my own version for children. For my topic I choose King Alfred the Great, who was King of Wessex from 871-899 during the Viking invasion. Specifically I have been comparing how the children's histories and the scholarly sources write about Alfred's early battles with the Vikings.

     Along with History I have also taken a few other courses unrelated to my Major. In my first year I took an English course, that focused on studying fiction, and took both a micro and macro economics course. I have even taken two introductory Japanese courses.

     I have talked with a few other computer science students who I have listened to complain about how they were forced to take courses unrelated to their Major. However, I have really enjoyed taking these courses and I feel they have expanded my knowledge beyond the scope of my Major. The way I see it, I probably wont have the opportunity to take these kinds of courses again so I should take advantage of it while I am still at university, especially considering I will probably be graduating by the end of the year.

     I should probably get back to working on my history project, since it is still far from finished. I am getting really tired though, especially since I have spent the majority of my long weekend in my room working on homework. However, the end is almost in sight, one more week of intensive studying and then I finally get a break.

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].

Non-Player Character AI in RPG Elements

     One of the most important parts of my RPG game engine is non-playable characters, also known as NPCs. Interacting with these characters is one of the most important parts of the game, and the more realistic these characters behave the more believable the virtual world becomes.

     I want to design a system for describing behavior that is at first simplistic but can gracefully extend to include more advanced behaviors. Initially I want to be able to describe a behavior of a couple random or sequential actions. For example, a character that paces around randomly and then occasionally jumps. Designing a system to handle this simple behavior is trivial, but it may not extend well when I want to implement more complicated behaviors. For example, I want to eventually add tasks and goal oriented actions. These actions will not describe a sequence of individual actions but require the character to choose a sequence of actions to achieve a described goal.

     I plan to solve this by using having an action queue. The queue is populated with the current action and the next actions the character plans to preform. Some actions correspond directly to an atomic physical action like preforming an animation or moving. Other actions are made up of many atomic actions generated dynamically. When the first action in a characters queue is one of these more complicated actions it break this action down into its atomic actions. So the solution is a queue of actions where an action can be an atomic action or a more abstract complex action.

     I have so far come up with a four types of complex actions. The first is a simple sequence of actions the character preforms in order. The second is a weighted set of actions preformed in a random order with preferences to a particular action based on the weights. The third is a goal oriented action were all that is described is a goal and the character must generate a set of atomic actions that will allow it to complete the goal, it must also re-evaluate its decision at each step to consider changes in the world that invalidate the plan. The last type of action is a utility oriented action, this type of action is the most abstract since it only specifies some need that they character must satisfy, such as satisfying its hunger, and this action can be composed of many goal-oriented actions.

     Each one of these action types gets progressively more abstract and requires the character, rather than the game designed, to do more of the decision making. Well it is possible for the character to have complete information about the world this would not be the most realistic. A possible extension I have thought about for this system is to have the character build up its own model of the world which includes imperfect and erroneous information about the world. Characters would then benefit by interacting with each other to learn and complete goals. While this would be an interesting experiential I anticipate that this feature is still a long way off.

     In the meantime I have implemented the first parts of this description in my game engine. I have atomic actions, sequences and weighted sets working. Since each level of action gets progressively more abstract it is necessary to describe some lower level actions before the higher level ones can use them.

     In the near future I intend to start writing some goal oriented actions, specifically related to moving a character from one map to another. I talked about how I am able to build a graph of my maps based their connections. My characters will plan a route from a point on one map to a point on another map first by calculating a least cost path through this map graph, then as they arrive at each map they will calculate a path from the entrance door to the exit door, making this a two tiered search technique. There is one issue I still need to resolve, currently the map graph does not show which doors in a map are unreachable from other doors. If a character plans to enter a map through one door and exit through another but there is no way to reach the exit door the search algorithm will fail. This problem is made more complicated by the fact that objects in the world could possibly move and block the path after it has planned its route.

The diagram shows that a character can not simply find a solution by considering what maps are connected, it must also know what connections are reachable from each other

     There is one other component of NPC behavior that I plan to implement, which is how the player interacts with the them. In some of the original RPG games NPCs would respond with a single message every time the player talked to them. This style has persisted in many newer games but a few recent games, like those in the elders scrolls series, have come up with much better ways of handling these interactions. In games like Morrowind, the player is presented with a list of questions that they can ask an NPC, and the NPCs responses vary based on how much they like the player. This may seem like a large amount of dialogue that the designer must write but much of it is shared between characters. Some conversation topics are global, which means every NPC can be asked this topic and gives the same response, the responses can then be customized based on the attributes of the NPC and the topic can be qualified to be only ask-able of specific NPCs. My plan is to implement a conversation system that is similar to this but I also hope to develop ways of generating some simple conversation topics to reduce the amount of work required by the designer. Another problem I realize with this system is that eventually the list of topics will grow to be large, and I will eventually need to develop a way to search it quickly and intuitively.

     I believe that NPC behavior and interaction will be one of the most interesting features going forward with my project. I also believe it will be a very challenging process with the potential for many exciting innovations. Despite the challenge, I am confident that by simulating more realistic NPCs my virtual worlds will seem more alive.

April Fools Day

     Today is one of my favorite holidays, its right up there with international talk like a pirate day. Every year look forward to April Fools Day. I especially enjoy how in recent years the internet has played a large role in the celebrations. Every year you can be sure that the big websites will pull some big prank. Unfortunately, many people forget about April Fools Day and miss out on the fun. So to make sure that you don't miss out I will tell you some of the funniest jokes I saw this year, and remember some of my favorites from the last couple of years.

     The biggest player in April Fools Day on the internet is undoubtedly Google. Every year they advertise new joke products, and usually multiple jokes for each of there popular sites like Gmail and YouTube.

     This year Gmail announced a new feature for those users that have trouble with all of the tiny buttons on a mobile qwerty keyboard, its their new Morse code keyboard with only two buttons.

     YouTube also released an exciting new product that lets you watch videos without the use of the internet, its the YouTube complete DVD collection. I really liked this one and the best part of the YouTube complete collection is how you can sign up an unsuspecting relative for no extra charge.

     Google maps announced that they had ported their map viewing program to one of the most overlooked platforms, the NES. You can now view Google maps in stunning retro 8-bit quality.

     Aside from Google there are some other sites that usually get involved. However, this year it seemed like many of the other jokes weren't as good as they had been in the past.

     XKCD usually as a pretty good joke, this year it was something to do with a different comic based on your web-browser, but I couldn't get it to work that well. Last year their joke was much better, they released all of their comics in 3D. The year before that they converted there entire site into a UNIX console. These features became so popular that they are still available today with a simple URL hack.

     Although April Fools Day is now dominated by the internet, traditional forms of media like newspapers, radio and television often try to have some fun also. One of my favorite TV pranks from a couple years ago was an ad run by the BBC about the discovery of flying penguins. I also liked a joke I saw run in several local newspaper about the city planning to build a bike tunnel under false creek to supplement its recently added bike lanes. Unfortunately I do not use these forms of media as much anymore and as a result don't notice them as much as the internet jokes.

     I have seen many jokes over the years and I have identified certain qualities that I like to see in a good April Fools Joke. The most important quality is that it should look convincing. The Gmail Morse code joke did this especially well this year, the actors in the video sound as though they are talking about a real product and the style of the video is similar to recent tech videos like those announcing real new Google or Apple products.

     I believe the second important quality it that the joke needs to follow a specific progression. When the viewer start seeing the joke they should see nothing that makes them believe it is a joke. This part of the joke establishes the shared context and grounds the joke in the real world. Once this as been done the joke should start to introduce small things that catch the users attention. Then suddenly the main punchline of the joke hits and catches the viewer completely off guard. However, it should not catch them so off guard yet that they immediately know it is a joke. This is the most difficult part, at this point the viewer should be at a perfect balance between believing the lie and being able to commit to the belief that it is false. Once the joke has reach this point the anticipation is gone so any final parts need to be completely ridiculous. A common feature at the end of April Fools Day videos is to satirize the shared context introduced at the beginning, in the case of the Google videos they do this by making the characters, that were established to be typical at the beginning, say something either out of character or fitting with the stereotypical character in an extreme way.

     April fools day is pretty much over now, I hope you didn't miss it and enjoyed the entertaining online humor. Hopefully, next years April Fools Day will be just as great, especially since we will be able to view twice as many at once with this new chrome add-on.

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.

RPG Elements: Console Improvements

     Back in February I wrote a blog entry about an RPG game engine that I was working on called RPG Elements. I have been busy with university, however I have found some time for implementing interesting new features. I am most excited about some of the new features I have added to the map editing tools recently. These tools allow me to create maps much more quickly and even generate hundreds of simple maps in mere seconds.

     I mentioned in my last blog entry that the main editing tool is an in-game console with commands for adding new objects and creating new maps. As my engine has evolved many features had become merged with the console that really should not have been, for example the actual logic of the console commands in many cases needed to be separate functions. With all of the unrelated logic in one place, adding new commands became increasingly difficult. To fix this problem, I refactored the console by moving these features into more appropriate modules, I also separated the console commands into there own classes. Now the console module is complete independent of the commands which it runs.

     When I refactored the console I realized that I needed to redesign the settile hotkey. In my RPG engine, the map is represented by an array of tiles, the user can set the type of the tile their player is standing on by typing "settile <type>" into the console. Because this is such a common operation, it is not practical to make the user type this command in every time, so I had the console remember the last arguments passed to this command and then all the player would need to do was press the "w" key to execute the same command again. However, now I made the commands independent of the console I no longer wanted the console to be storing the arguments of a specific command. Well I was thinking about how to fix this I suddenly thought that it might be nice to have this hotkey feature for other commands or have hotkeys for different arguments. So I came up with a new console command that can assign any console command to any of the number keys. For example, "hotkey 1 settile;sand" sets the tile under the player to sand when the 1 key is pressed. Another advantage of this feature is that I can assign "sand" to the 1 key and "grass" to the 2 key, where before I would have to type in a console command every time I wanted to switch between the two tile types.

     For my next feature I wanted to be able to write a list of console commands in an external file and then have them executed sequentially. When I refactored my console I realized that this would not be very difficult to add and would help easily accomplish what I had originally designed my engine to do, generate a large amount of content with minimal high level user input. One difficult I was confronted with was that loading maps took a couple milliseconds to load and scripts executed in a separate thread. I solved this by adding a command to tell them to wait a certain number of milliseconds to give the map a chance to load. Another problem was that because I am executing hundreds of commands at once I more frequently come across some of the race conditions that I had noticed occasionally in the past. While at the moment these race conditions seem an annoyance, I think of this as an opportunity to find and fix these serious bugs that would not have been possible with manual testing. I am excited about how quickly I was able to add console scripting and I believe it will be very useful going forward.

     With the addition of console scripting I can now generate hundreds of maps and add doorways between them. I thought it would be interesting to visualize all of these maps and their connections, so I wrote a console command that would query the list of doors to identify the directed edges between the maps. The program then outputs a file with a list of these directed edges in a format that I can input into a graph making program called Graphviz. Well this graph is interesting to see now, it will be very useful for some of my planned features. One feature that will require a graph of directed edges is non-player character (NPC) path finding, eventually I want to program NPCs to walk between maps, and by analyzing graphs like this they will be able to identify the best path.

An example map graph generated using test data based on a popular classic RPG game. At this point all of the maps are empty, aside from doors (represented in the graph by directed edges)

     By improving the tools in these ways, along with some other minor improvements, I have greatly reduced the amount of work I need to do to create a map and can now focus on higher level design decisions. Well these tool improvements are very interesting, they are not the only new feature that I have implemented since February. In one of my next blog entries I will talk about some of the other new features. I am also hoping I will have time to upload another video to demonstrate some of these new features. In the meantime I am adding new feature to this project and the next big area I need to improve is NPC behavior and interaction. So stay tuned!

New SimCity Engine

     A couple days ago I wrote a blog entry about a simulation game that I had written to learn SDL and improve my C++ programming skills. I showed this project off at the game developers club and it reminded them about the new SimCity game that was just announced. The game was announced at a recent game developers conference where they also explained a bit about their new simulation engine called GlassBox. The algorithm that the engine uses has a particularly elegant design which I find very interesting.

     The system defines five basic object types: resources, units, maps, globals and agents. Resources are variables such as people, money, electricity. They are organized into bins that can store a limited amount of a resource. Units are physical objects in the world like houses. They are defined as a collection of resource bins. Maps are used to represent the distribution of resources across the environment. They are essentially an array of resource bins with one associated to each map tile. Globals are like units, since they are a set of resource bins, but do not represent physical objects. Lastly, are these things called agents that move around the environment distributing resources between resource bins. Game developers represent these different types of objects using rules which they define in scripts. [1]

    Game developers are able to simulate various natural phenomenon using these simple constructs (as can be seen in this video). For example, a map can be used to represent resources like underground minerals or areas covered by forests. Agents are used to represent the distribution of electricity, pollution or the movement of cars and pedestrians. According to the article the company that makes SimCity believes this engine could be applied to their other simulation games like, one of my favorites, SimTower. [1]

     Although this design seems very elegant I feel that there many some potential problems which have been left out. One aspect that may pose a problem is that there may be tens of thousands of independent agents running in parallel at any given time. Well this seems beneficial in the era of multi-core computing, managing these agents and ensuring mutual exclusion is non-trivial. Another thing to consider is if so few constructs can accurately represent everything needed in a simulation game with over simplifying some aspects.

     I believe that this engine was very elegantly designed. This level of elegance is what I often strive for in my own programs which is why I appreciate how difficult it is to achieve. To create such an elegant engine, software developers often need to iterate and rewrite the program, each time removing unnecessary or redundant features.

     I would very much like to try and implement a similar engine one day and this engine it was interesting to read about. Game development companies are often very secretive so when they reveal this kind of information it is very valuable.

References:
[1] Frank Cifaldi. "GDC 2012: Breaking down SimCity's Glassbox engine" Internet: http://www.gamasutra.com/view/news/164870/gdc_2012_breaking_down_simcitys_.php, March 7, 2012 [March 21, 2012].

Game Developers Club

     Back in January I wrote a blog entry about how I volunteered at clubs week to promote the game developers club. Since then we have held several meetings and had some interesting discussions. Since I have been a member for a while I am also looking for ways to get more involved.

     One of the things that I really enjoy about the game developers club is learning about all kinds of different technology that I might not otherwise have heard about. Usually when I am working independently on my own game projects I am so focused on the way that I am currently doing things that I do not stop to consider new or alternative technologies. By discussing ideas with other people I feel that I can learn more than I can individually.

     For example last week at the game developers club we discussed game engine called Unity. Some of the other members have used Unity to create very interesting games. Unity developers also have the choice of embedding there game in a web browser or deploying it to a mobile device. At one of our upcoming meetings one of the members might give a brief tutorial on how to use Unity because many people seem interested.


     I have really enjoyed being a part of the game developers club and often try to find ways to get more involved. As I already mentioned I volunteered at clubs week but I have also been looking for ways to help organize the meetings and other club activities. Over the past couple semesters some of the prominent founding members of the club graduated and there has been a gap in leadership. Last week one of the former club presidents drop by during the Burnaby meeting and we talked about some of the things we could do to try to improve the club. One of the problems is a lack of focus that we have had at our meetings lately, to fix this I will try to spend some time during the week before the meetings coming up with some more topics for discussion.

     Another thing that needed fixing up was the club website. Many of the pages were out of date, especially the projects page. I started by talking to some of the executives and gathered a list of the projects that they had worked on. I will also need to find out this week if any of the other members have projects they want to post on the website. The project page on the club website is a valuable feature for promotion of the club and its members. The former club president I was talking to was saying game development companies often visit the website and one of the first pages that they want to look at is the projects page.

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.

Summer in Innovation

     I mentioned I have already mentioned that since the courses offered at my university are very sparse I have been looking for alternatives. Initially I thought I should try to find another co-op job, however I have already done 4 semester of co-op and would really like to concentrate on graduating so that I can get a full time position.

     Then I heard about a program that my university is offering called the Summer in Innovation. The program is targeted at upper division computer science, business and interactive arts and technology (IAT) students. Twenty-four students, eight students from each of those three disciplines, will be chosen and the program will have a focus toward working with and learning cross disciplinary concepts to develop software applications.

     The theme for the summer is all about designing mobile applications. From what I understand the course will involve several mobile applications developed as part of smaller groups and a couple developed as a large group. There will also be several industry experts that will come to discuss innovative ideas in mobile applications to share their thoughts and get feedback from the students.

     This program would count toward my graduation as a 15 credit course which would fulfill the 14 credits that I still need to graduate. I would also fulfill the honours research credit and if I decided to I could take 4 more courses in the fall to graduate with honours. So in terms of program requirements this seems to meet my need perfectly.

     Considering that this is a 15 credit course I assume that it will be very intensive. It will be the only course I will be taking and will probably take at least as much time as working on co-op. I do not believe this will be a problem, since I have done co-op and have worked on intensive group projects like my animation project.

     I am also very interested in working with mobile application and feel that this would be valuable experience to have given their growing popularity. It would also give me more opportunities for possible careers after graduation at are not directly related to games.

     Since I found this program interesting I decided to apply. They liked my application and I was accepted into the program. So this is what I will be doing this summer I am very excited.

Creativity in Games

     I have already talked about one of the suggestions that I received from my previous job interview. Today I would like to talk about another thing they suggested.

     During the interview they asked me questions about the kinds of video games that I had played and what I liked about them. I had some trouble coming up with reasons because I had not given it much serious thought. I believe that understanding why one likes something is important to think about, not only with respect to games but also, even more generally, with any kind of software. To help me understand why I like the things that I like, I will try to explain some of the aspects of games I like using specific examples of games that demonstrate this aspect well.

     I have liked playing video games all my life and have many reasons I prefer some games over others. Its very difficult to identify a single common element that I like in games but some themes that I like to see in games are creativity, exploration, simulation, expansion and progression. I wont address all of these in this blog but instead will focus on the first and then continue with the others in a future post.

     Unfortunately, since I began university I have played fewer and fewer games. The biggest reason for this is that I have been spending much more of my time working on university projects. Even still I do occasionally play games but I feel that I do not enjoy them as much as I did when I was younger. Maybe I have different interests now then I used to? I think part of the reason I have not played many games lately is that I enjoy making my own games. Making games is a much more creative activity and it is hard to find games that allow one to be creative.

   A perfect exception to this is Minecraft which gives players complete freedom to be creative. Minecraft has no objective and simply encourages the player to gather resources and use those resources to build things. Other games that I have really enjoyed are simulation games like Rollercoaster Tycoon and The Sims. Both of these games require the player to design a virtual world.

    One aspect I like about of these games that promotes creativity is the lack of a well defined objective. All three of these games have no end condition, the player just keeps creating until they decide to stop. In games with a clearly defined objective, game developers would design the features of a game as tools that the player can use to get them to the goal. In games where there is no goal it is often unclear what kinds of features the player will require. Game developers often find designing these kinds of games particularly difficult because they must create features that have many possible uses.

    A good example of a feature with many uses is the piston blocks in Minecraft. The piston block is a block the player can activate remotely and when activated will extend causing any block in its path to be moved. The piston can also be modified so that when it is deactivated it retracts and pulls the block back to its original position. Using this people have created elevators, automatic doors and even giant moving faces in the sides of mountains.

    While a lack of objective has in someway helped these games I often feel like there needs to be some kind of goal in order to validate the quality of the players design. Business simulation games like Rollercoaster Tycoon allow the player to gauge their skill based on how much money they make and how happy the people are that ride their roller coasters. However, Minecraft and The Sims seem to be lacking a validating goal and occasionally I wish there was some kind of goal that I could optionally try to achieve. For example, in Minecraft I built a castle but then realized that there was nothing worth defending the castle against and no way to prove that my castle was designed well.

     Creativity is not only limited to simulation games. I believe that players want to be creative in whatever game they are playing. There are countless examples on the internet of players finding situations where they can be creative in almost any game. Therefore, my suggestion to game developers is to always keep players creativity in mind.

     Well those are my thoughts on creativity. I find this kind of subject very hard to write about because I have many ideas but it is very hard to boil them down into a single argument. I had to rewrite this post several times because I kept going off on a tangent. I plan to think about these ideas over the next couple weeks and hopefully by writing and thinking about them I will further understand and solidify them in my mind.

Factory Simulator

     Last time I mentioned that I was writing a game in C++ using the graphics library Simple DirectMedia Layer (SDL). The goal in writing this game is to practice C++ and explore some of the popular C++ libraries available.

     I discovered that SDL has many similarities to XNA and was not difficult to learn. I was able to start making my game within about an hour or two of learning SDL basics.

     I decided to make a simulation game, similar to games like SimCity, since this is a style of game that I enjoyed when I was younger but most of my favorite series have since become discontinued. I came up with an interesting idea for a factory simulator where the player owns a factory and must manage the happiness of the workers. Then I broke the problem down in to the simplest parts so that I could plan to implement it in roughly two days.

     In my game the player can build three types of buildings: houses, power plants and factories. The houses produce workers, the power plants produce power and the factories produce money. Also, The factories can only produce money if they have enough workers and power.

     So far I have implemented everything I mentioned but will refrain from showing any pictures just yet since it is still mostly text based with a few placeholder graphics.

     I plan to extend this by giving factories different kinds of input and output resources, for example a paper factory might require wood as an input and produce paper as an output. By doing this I can create chains of resources that the player needs to manage, for example a logging camp is required to produce wood for the paper factory. Also, since the game is about managing the workers happiness I need to keep track of the mood of each worker which will be affected by factors such as wages, safety, housing and environment.

     Overall I have enjoyed learning SDL and I think it is a useful graphics library. It handles most of the same aspects of drawing 2D sprites to the screen as XNA and has extension libraries for drawing text, handling input and playing music. To draw 3D graphics it is common to combine SDL with OpenGL which is something I may try in the future. In contrast to XNA, I have not yet figured out how to use pixel shaders but suspect that I may need to use OpenGL's GLSL shader language which I have heard is more complicated than XNA's HLSL.

     I plan to continue working on this game in, my free time, to practice my C++. If I get it to a more complete state I will post some pictures and videos in a future blog entry.

Interview Feedback

     This semester I have been trying to figure out what I will do during the summer. Unfortunately the course offerings for the summer are very sparse and I have already taken most that are offered. Since I would rather wait till the fall to take more courses I have been trying to find alternatives such as another co-op job.

     Two weeks ago I had an interview downtown at a video company. I have not had an interview in a while and I ended up doing rather poorly. A couple days later I received an email from the co-op coordinator saying the company decided not to hire me. Along with the email they had sent some feedback about what I could do to improve. I spent some time reflecting on this feedback last week, since my midterms were finished and I had a bit of free time.

     The things they told me were not overly surprising since I had already identified them as things I had struggled with during the interview. The first was that I needed to improve my C++ programming knowledge. During the interview they asked me to write a simple C++ program on a white board but I had trouble coming up with an answer.

     I have become very proficient in languages like Java and C# by using them for my hobby programming projects. I have only used C++ for smaller school projects and a couple times during co-op. Since I do not practice C++ very often I often struggle with it.

     For practice I decided to try writing a game in C++. I have never written a game in C++ before and wanted to find out what libraries are available for making games. I though there must be some popular libraries since game development companies use C++ almost exclusively. C++ is the language of choice since modern games are always trying to push the limits of the current hardware's performance.

     One popular graphics library I have heard about is called Simple DirectMedia Layer (SDL). SDL is one of the most fundamental graphics libraries and many higher level libraries, for example a python library called pygame, are written as extensions or wrappers of SDL.

     Another library that I have been interested in trying, not related to games, is QT. It is a user interface library that people have been talking about recently and which is used by applications like Google Earth and Autodesk Maya.

     In my next blog entries I will talk about the game that I made in SDL and a bit more about the interview feedback.

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.

Thoughts on Blogging

     Over the last couple of weeks I have been having some trouble coming up with ideas for blog entries, but I have also spent some time thinking about blogging in general. So today I will talk about the ideas I have contemplated related to blogging. I guess you could say today that I am, blogging about blogging or, meta-blogging.

     In the past I have tried to start a blog but I had trouble getting into the habit of posting regularly. Then I started this blog, at the beginning of this semester, as part of a technical writing course. The instructor requires that I write a 26 blog entries before, April 11th, the end of the semester. The blogging component only makes up a small percentage of the course mark, but the goal is that I practice writing on a regular basis.

     Blogging is an activity that I never used to find interesting. However, since I have gotten in the habit of writing regular posts I have started to enjoy blogging. Based on this experience I could definitely see myself continuing blogging after I have finished this course.

     Starting a blog is simple, but generating ideas and getting people to read the blog are very difficult. In this blog I have talked mostly about some my of the games and graphics projects, but I doubt that I could sustain a blog on those topics alone. Secondly, the audience for this topic is also very small. I have had some success with one of my videos on YouTube which has currently reach close to 7000 hits, however my other videos have not been nearly as successful.

     This then got me to thinking about the kinds of blogs that I am most interested in reading. A common thing that I search for and read are tutorials. In order to write a successful tutorial I would need to write it on a topic that I am very skilled at. The two skills that immediately come to mind are game programming and making computer graphics. I am both very skilled at these and people are constantly asking me to teach them. For example, just this week at the first game developers meeting when were suggesting topics for meetings several of the members were interested in learning more about these two skills. As a result I have volunteered to give a couple tutorials.

     During the rest of the semester I will probably try creating a few video tutorials on YouTube and see how many views that I can generate. If any of these turn out to be particularly successful I will let you know in another blog entry.

XNA Game: RPG Elements

    The projects that I have talked about so far have been ones that I worked on in the past. Today I will talk about a project I am currently working on. It is called "RPG Elements" and is the third major iteration of an RPG game engine that I have worked on for just over a year, although this iteration was rewritten pretty much from scratch in about a month. Through building and rebuilding this engine I have created many interesting features and today I will talk about the most fundamental, and leave some of the more advanced features for another time.

    My goal for this project was to design a tool that could create a game with minimal effort required by the designer. I identified that most of effort is spent in designing the levels so I wanted to make this as simple and intuitive as possible. In previous iterations I had tried making a variety of different editors but I found this to be a lot of extra work. In this iteration I took a different approach, I designed the engine so that all of the data can be edited while playing the game using a console. My biggest surprise was that this console was very easy to implement because of the data structures I had used for storing my data. Then to make editing easier I added shortcuts and hot-keys for common console commands to make editing quick and intuitive.

A Logo Graphic I Designed

    To demonstrate this I will explain step by step the creation of a level. First the user types in the console "newmap" and the dimensions of the tile map. Then they draw background tiles on the map using the player as the cursor. Then, in the console they type "addmapobject" and the name of the object, such as tree or house. The player can then grab onto this object, walk around and drop it where they want.

    In this style of the game, the player walks around a virtual world and interacts with objects. These interactions are known as events. An event is composed of a set of actions that are executed sequentially. There are many different types of event actions, such as teleporting the player to another map, displaying a dialog box, asking the user for some kind of input, etc. Event actions have flow control in the form of "if" statements and loops and multiple events can also execute in parallel. As a result, events are implemented almost like a mini scripting language. Common events, like doorways that teleport the character between maps, have been designed to be especially easy to create since they are so commonly used.

    With these two fundamental features I can design most of what I need for my game, and my more advanced features are typically composed of or supplement these features.

    At this point my engine is in a fairly complete state and I am in the process of using it to create a game. In a future blog entry I may talk specifically about this game, in addition to some advanced features, but it is still in the very early stages.

XNA Game: Tactics Game

     After working on Crazy Party Fight I decided to give another shot at developing a game in XNA. This time I tried to find a couple of my university classmates to help me with a bit of the coding.

     We decided to make a tactical turned based strategy game. For those not familiar with this genre it is basically like chess but with custom pieces and other role playing game elements added. In our game each player would move each character individually during the movement phase and then if they were within range of another character they could attack during the attack phase. The goal was to defeat all of the opponents pieces.

     We decided on a couple of interesting design features for this game, one was the use of an isometric board. Isometric is a type of camera projection that in 2D games basically results in angled diagonal tiles. This makes movement a bit more difficult to deal with because it is on a diagonal but gives the game a bit more of a 3D art style. Another difficulty was implementing the opponents AI. One simplification that we noticed with other commercial games of this genre was that the player always moved each piece during each turn, instead of one piece per turn like in chess. This simplification allowed us to consider a reasonably good move for each piece rather than trying to figure out which piece would be best to move. Although our AI is relatively simple compare to  some chess AI, the strategy of a tactics games is more based on the comparative strengths and weakness of the pieces rather than their positions on the board. There are also elements of randomness thrown in to determine if an attack is successful or results in a critical hit.

     Unfortunately, my attempt at making a project as a group fell apart just as we had finished implementing the core mechanics of the game. The failure was probably a result of the other group members not feeling any real obligation to work on the project. However, convinced that we had created something interesting, I decided to continue working on the project to get it to a stage where it was presentable. I replaced all of our place holder graphics with new ones I made in Inkscape, and created all of the menus for choosing a level and positioning pieces.

Screenshots and Characters from the Game

     After finishing all this work I created the YouTube video you see at the top of this article. Surprisingly this YouTube video has attracted a large number of hits, about 5500 at the time of this writing, which is large compared to the one or two hundred hits my videos usually get. Clearly, this is a genre of game that is particularly popular, especially among indie game developers.

     The final result is still a work in progress. I would really like to continue and finish this project, especially considering the YouTube popularity. However I have always been to afraid to, since I have a vague memory of just how much refactoring is required, especially of the parts I did not write. Another factor that holds me back is the amount of art content that I would need to create. Being a programmer I am not most efficient artist, and yet I am also a bit of a perfectionist when it comes to my personal game projects.

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.