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.