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.
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.
In my last entry I mentioned a YouTube video of a game I had made. I thought today I would explain a little bit about that game.
The game is called Crazy Party Fight and was written in C# using Microsoft's XNA Framework. XNA is a development kit for the Xbox360 and other Microsoft devices like the windows phone. During development of this game I actually ran and tested it on my Xbox 360.
Crazy Party Fight is a party battling game for 2 to 4 players. You get points by jumping on the other players heads. Also, occasionally items fall from the sky and if a character collects one it has an effect such as shrinking the player, making them run quickly, or jump really high. Something I put much of my time into was the in game character and level editors. The idea is that players can create their own characters and levels using a collection of pre-made parts.
This game was the first major game project I made using XNA. I worked on it in my free time for 4 months one summer during second year university. The goal was to submit it to a contest by the end of the summer, not that I had a hope of winning, just so that I something to work toward, hence why in the video you see a team name.
Characters created using the character editor
This was the first game I developed using the programming skills I learned from university. All the games I had made before this I made using a graphical tool or at the most involved writing a couple of simple scripts. Everything in this game was made by me, except for audio which I obtained from online game resource sites. All of the graphics I made using the open source program Inkscape which has since become my favorite drawing program for game projects.
I have often been asked why I never finished this game. The fact is that this was my first game project and by the time I got to this point in the project the code had become completely unmanageable. The amount of time to add each new feature was growing rapidly and it was no longer worth continuing. I felt I could learn so much more by starting other projects and trying new things, instead of spending months trying to refactor all of my code and fix all the bugs.
Through making this game I did learn from my mistakes. One of my biggest mistakes was that I did not realize that you had to release the memory for images and as a result had massive memory leaks by the end. Another thing was that I spent so much time making the level and character editors that the actual game turned out not to be very fun to play.
Crazy Party Fight was in many ways the beginning of my game development projects. I will talk about some of my other game projects in future posts.
For the last two days I have been helping promote the Game Developers Club at my university's clubs week. I have been a member of the Game Developers Club for about a year and a half, but this is the first time I have helped at clubs week.
Clubs week happens at the beginning of each semester where all of the clubs setup tables and promote their club. I took a quick walk around, as I do every year, to see what kinds of clubs there are, and as usual most of the clubs are faculty/student association clubs, ethnic/religious clubs or political/protest clubs, not that there is anything wrong with most of these clubs but they are not particularly interesting to me. I am always looking for more of an activity based club, something fun and social to do while at university. There were a couple more this year than I have seen in previous years, like two or three board game clubs, the outdoor club, the photography club, one or two dance clubs, and three or four athletic clubs, but these kinds of clubs are still few and far between. This is one of the reasons I decided to join the Game Developers Club, the other being that I enjoy Game Development as a hobby and like discussing my ideas with other people.
When I got to our table I noticed the other guys did not have very much setup, a medium sized sign, a couple of game related decorations and some hand outs. And after a few minutes it seemed like not very many people were coming by. So I suggested that we put on a youtube video of one of my games I made a couple of years ago. As soon as we put this on I started to notice most of the people walking by looking at the video and some of them starting to walk over to the table to ask about it and the club. I thought this was awesome, and we got lots of people to sign up, hopefully some of them come to the meetings.
What the Game Developers Club does is support those interested in developing games either as a hobby or as a potential career. We have members from all different backgrounds with a range of technical and non-technical skills. Some are programmers but many have very little technical skill and are interested in art or design. We have meetings twice a week, one technical and the other design related. In the technical discussion we usually discuss techniques used for developing games, such as handling collisions and physics or analyzing an interesting technique in a game we recently played. In the design discussions we usually try to design a game, starting with an idea or an experience we want to give the player and expanding on it until we have a complete game idea. Many of the members of the club are also working on hobby game projects and are often looking for people to help them out. We have also had some club projects we have started such as a collectible card game. Lastly, we have a mailing list that we send out announcements about local events, like game development competitions or conferences like SIGGRAPH, or sometimes even about game companies that are hiring.
In conclusion, the game developers club is a something I really enjoy and I also really enjoyed promoting it at clubs day.
During my time at university I have had the chance to do a couple of Co-op work terms. Last year, for my second and third work terms, I worked at SAP for eight months. I worked as a software test automation developer. SAP is the worlds largest developer of enterprise software, and one of their more well known products is Crystal Reports.
My job started with me running manual tests of the companies installers on a daily basis. Testing that each product installed correctly on each supported operating system. Gradually I started the process of automating these manual tests. It became more interesting when I became responsible for talking with developers and trying to develop more comprehensive test cases. I was basically working on my own small team project, with one other co-op student, and as a result I was able to experience a complete development cycle. The cycle started with me gathering requirements from the other developers. Next I designed test cases to meet these requirements. Then I implemented the test automation for each test case. Lastly, I was responsible for maintaining the test cases and fixing them when the broke.
I found this to be an interesting experience. The most challenging part was the amount of multi-tasking that was required, and more importantly, discovering that I am not very good at multitasking. Everyday I would have about 50-80 tasks that I had to run, each one ran for about an hour, then I had to check the results and start another task running on that machine, and finally check the result when it finished. At the same time I had a long list of improvements that I was making to the system. So I would constantly be switching from one task to another, and occasionally when I found a bug I had to report it. Then about an hour or two later someone would come by and ask about the bug, and I would have to sit there for a minute and try to remember which task they were talking about. That was a stressful experience.
Despite the difficulty I did enjoy some things about my co-op term. The office was right downtown, which was an interesting experience for me since I do not often go downtown. Also, some of the people I was working with were really fun. Occasionally we would play a game of Pool or Foosball when working was getting particularly stressful. I remember often going out for lunch with one or two of the other co-ops I was working with. There are a lot of great places to go for lunch downtown, that is something I really miss, especially the butter chicken place across the street. But maybe I am getting a bit off topic.
The work I was doing might have been a bit boring, and not really what I had expected, but I think I learned a lot from the experience, like improving some of my non-technical skills. I had a chance to practice my public speaking when I gave tutorials for other testers on how to create automated test cases using the new software. It also gave me a perspective of what it is like to work at a big company, and particularly a company that does something that I do not know a lot about. I also was able to get a glimpse of other peoples jobs to give me some idea of what I can work towards after I finish university.
This past summer I took an animation course at university. The main component of this course was a group project to make an animated short film. The only requirement was that it had to be roughly 5 minutes long. This project took up the majority of my summer and was a lot of difficult and time consuming work but was extremely fun and I really enjoyed it.
Our group created the animation using an open source 3D modeling program called Blender. I had experimented with this software a number of times before the course but had never created anything nearly as complicated. Since I had used this software previously, and using it was not covered as part of the course, I took on the role of expert and taught the other members of my group. And this was no easy task, Blender is a very complicated and powerful piece of software. What made this assignment more difficult was that even though the course was a computer science course, creating an animation is more about art than anything else. Luckily, we had a couple of artistic computer science students in our group.
Planning sketches and the finished character
There are many steps required to make such an animation. We started with several planning meetings where we developed a rough storyboard, characters and setting. We then took the sketches of the characters and scenery objects and created polygonal models of them using Blender. Then we created textures to overlay onto the characters to add detail. We created some of these texture ourselves, such as the hieroglyphics and the details of the characters. For other textures, like the sand and rocks, we used stock photos from the internet.
The model and skeleton of our cat character
Now that we had finished the models for our characters and scenes we next had to animate these models. To animate the characters we added a virtual skeleton which was connected to the model. By adjusting the skeleton we could pose the character. And so to create the complete animation we just had to pose the characters, camera and objects in each key frame. Key frames are a the important frames, and a frame is just the name for a single image. By defining the positions and orientations of objects in the key frames, Blender is able to interpolate to get the positions and orientations of the in between frames.
A rendered scene with lights and fire
The most time consuming part of this project was when we started to render our final animation. Rendering is the process of drawing a frame. The time consuming part is calculating all of the lighting, shadows and other special effects like motion blur or depth of field. Some of our more complicated scenes took a couple minutes for each frame to be rendered. And when you consider that our animation is 24 frames per second and roughly 5 minutes, we probably rendered roughly 7000 frames. Rendering was still in progress on the last two days before the due date. It was after most students had finished exams so we found a relatively empty computer lab and rendered segments of our animation on up to twenty computers at once. Even this took a long time, but remarkably we managed to finish and then add sound effects before the deadline.
What I just explained is only a brief summary of how we spent the majority of our summer creating this animation. It is probably hard for anyone who has never worked on such a project to understand the amount of work we had to do just to make 5 minutes of animation. However, I have stayed away from some of the more technical details to keep this article from getting too long. I may talk about some of the details in a future blog entry. In closing, watch the video if you have a chance, its at the top of the article.
For the first post of my blog I think it is necessary that I introduce a bit about myself and what I will be blogging about.
I am a fourth year computer science major who has had a lifelong interest in computers. When I was in grade 4 I learned HTML and created my first webpage. My early interest in computers probably has a lot to do with that fact that my father works with computers as an IT manager at a technology company and so I naturally picked up a lot about computers growing up. When I was young I was always trying to learn and make new things using the computer, be it drawing, making webpages or even trying to program my own games.
The thing that sets me apart from many computer science students is that I have always been a bit more interested in the creative uses of computers rather than solely how they work. Many of my friends growing up had a similar interest and a few of them decided to pursue it by going to an art school. Since I have always done reasonably well at the academics I took the university route. Looking back I feel that I made the right decision by pursuing a computer science major. I have done well with my courses and my grades reflect it, ironically, being considerably better than in high school.
During my time at university, I have managed to work some of my interests into my studies through the courses that I have taken and some of the projects I have worked on in my free time. One example was a computer animation course that I took last semester where me and a team of 4 other students were tasked with creating a short animated film for our final project. However, the most interesting experience over the past 4 years was during my last co-op term where I worked at Capcom improving some of their internal tools they use for making their video games. But I will save the details of those for a future blog entry.
For the sake of wrapping things up I will say that I intend on making this a blog about interesting projects I have finished or am currently working on related to computer graphics and game development. And I will be posting a new entry at least twice a week with a couple days in between to think up more interesting things to write about.
