Thoughts on the Global Game Jam

So this weekend I participated in the Global Game Jam, and it was quite the experience. It started Friday evening, when they announced the theme, Deception, and the secondary themes, Maids, Raids, and Trades. We brainstormed, made game pitches, then broke into groups. I ended up in a group with some great people, and I think our game turned out pretty good. Our game’s page on the GGJ website is here. Rather than trying to write a cohesive essay that addresses all my thoughts, I thought I would just share my thoughts in any particular order.

We did the game in C# using the XNA framework. I have only used C# once before, on a project for a class my senior year of college, and I didn’t do any XNA programming at the time. I was a bit nervous, making a game in a day is difficult enough, without having to deal with an unfamiliar language/framework. But it came pretty easy, switching between computer languages typically isn’t too difficult, especially if they have similar syntax like C# and Java. XNA was also pretty easy to get into; there were lots of examples, and some pretty good documentation.

As I was working, I found myself wondering why I didn’t us XNA instead of Torque. It’s pretty easy, very powerful, and it’s free. But then I started running into things I had to do for myself in XNA that Torque always takes care of for me. Like animation and movement, I think I did a pretty good job making my own animated sprites, but I’m glad we didn’t have to do any sort of collision detection, because I hate collision detection. Working with XNA gave me a good appreciation for XNA, and gave me a renewed appreciation for Torque.

We developed the game to run on the Xbox 360, which was a bit intimidating at first. I expected it to be a horrendous process, but it was really simple. We didn’t have to do any weird code tricks to accommodate the 360, it just worked. It was really easy to develop for both windows, and the 360. Although I was surprised by how little room there is on the 360 screen. Developing for a PC gives you a lot more real estate to play with; it felt a little bit restricting at times. Overall, I thought it was really fun to make a game for the 360, and I’m glad that’s the route we took.

Developing the game felt like a whole months-long development cycle compressed into a 24 hour period. It included everything from the initial object oriented design idealism, to the horrible refactoring because your design didn’t account for something, to the bug fixes, to the code base growing large enough that you can’t keep it all in your head, to frantic debugging while trying to add new functionality without breaking anything. There were moments when I would look at a section of code, and even though I had written it only five or six hours previously, it felt the same as it feels at work when I look at code that I haven’t seen in weeks.

You would think by now I would know this, but making a game is a lot of work. I was programming almost non-stop for 24 hours with another guy, working on a rather simple design and we still had to leave a couple of features out. A lot of it was just taking care of small details that you have to take care of if you plan on releasing your program to the public.

Programming at 5:30 am after you haven’t been to bed is a bad idea. There were several times I would run the game to see what needed fixing, see something, go into the code to fix it, and have no idea what it was I was intending to fix. I started having to write down what I saw the game doing so that I could remember what I was looking for sixty seconds later. It was an amusing experience though.

I might post a couple more thoughts as they occur to me, I’m still pretty tired from the event, so I might be thinking better in a couple of days. Overall, I thought it was a great experience, and would recommend anyone who is interested in game development participate in something like this.

Nutritionally Dense Entertainment

I find that some entertainment choices are better than others. This may seem self evident, but bear with me here as I explain. Some entertainment seems more satisfying, for example, I could spend an hour playing Planescape: Torment, or I could spend an hour looking at lolcats. After the hour is finished I’m going to feel more satisfied if I spent the time with Planescape. It’s almost like Planescape is more nutritionally dense than the lolcats. Like the lolcats are a Twinkie and Planescape is an apple. The lolcats might be tasty, but too many will just make you sick.

I don’t think that you can say for sure that one form of entertainment is definitely superior to another. I think it’s primarily a matter of figuring out what forms of entertainment are best for you, and then having the restraint to seek those out. For example, I do really enjoy action RPGs, like Diablo, Titan Quest, or Torchlight. They are fun, and they’ll suck up lots of time if I let them. But I find that they aren’t as satisfying to me as other more story driven games. So I have to exercise restraint, and enjoy the action RPGs in small doses, while spending most of my entertainment time on other things. That was especially difficult the day after Christmas when Torchlight was on sale for $5.00. It was really tempting, but I knew that I wouldn’t enjoy it as much as some other games, and I’ve already got Titan Quest to give me my action RPG fix.

It’s kind of an interesting journey, figuring out what kind of entertainment really does it for you. Kind of difficult too, but I’ve found it’s helped me to enjoy my free time more. Just thought that was kind of interesting.

Game design lesson: Humility

So I’ve been thinking a lot about what I’ve learned over the last year, especially from working on my current project. When I started work on the game, I really thought I finally had things figured out. I had worked on several game projects prior to this one, and none of them made it very far. Maybe twenty or thirty percent complete, I would learn new things each time about what made a good project.

For example, I really wanted to make a game that played like Elite, or Privateer, except you drove around a car through a post apocalyptic wasteland. I still think that sounds like a fun game both to make and play. But writing my own graphics and physics engine was something I really didn’t want to attempt. Something that would have taken way too long. So I learned to build on someone else’s technology, and otherwise save yourself time.

I also worked for a time on an online graphic adventure type game. I had the engine mostly written in flash, and it was kind of neat. It was going to be an episodic online adventure, with new episodes every couple of weeks or so. The primary problem with that is that I don’t have much artistic ability. Graphic adventures are incredibly demanding graphically, if you can imagine. So it was a bad idea to try creating something where 90% of the content was outside my ability to produce. I learned to focus on my strengths.

I then worked on a hacker type game. I wanted to create a game that made you feel like an elite hacker flying through the networks at incredible speeds. I wanted to focus on speed, and cleverness, and so I started working on a game design document, and trying to write it in Torque. Unfortunately my design strayed from the original idea, and became a bloated mess of contradicting game mechanics. I learned to keep the design tight and simple, to focus on a single gameplay type.

Then, almost exactly a year ago, I started on my current project. I picked a simple game type, that I really enjoyed, and thought I could bring some new ideas to. I really liked the idea of setting up your defenses, and repulsing wave after wave of enemy. It seemed simple enough to create, and I figured I would have it done by last July. I’ve learned more from this project than any other, but I think the primary lesson I’ve learned is humility.

A year ago, as I was working on the prototype for this game, I thought I had it all figured out. I was going to quickly get the game done, release it and move on to the next game in my brilliant career. I wanted to share what I had learned with others, so I volunteered to speak at a gathering of local independent game developers.

I talked like I knew it all. It kind of got away from me a little bit. I did my best to present the lessons I had learned, but what I didn’t realize is just how little I knew. I had learned lots of lessons on taking a game to the thirty or forty percent complete mark, and I thought with this newest game I had figured out how to smoothly take a game clear to completion.

I’ve learned over the past year how difficult it is to make something that works well outside the controlled environment of your development machine. I’ve learned how difficult it is to make a system of interlocking pieces that interact with each other in a way that is interesting. I’ve learned that all I’ve really produced before were prototypes, and that the real thing requires much more polish. I’ve learned that anyone who produces any sort of game, and releases it to the public deserves a lot of respect. I’ve learned that it is very understandable that a game studio could spend hundreds of thousands of dollars, and years of development, only to push out a product that isn’t any fun. And I’ve learned that I am in no position to tell anyone anything about game development.

I’m going to keep working, learning, and occasionally posting the things I’ve learned from my efforts. I do intend to finish and release this current game, even if it doesn’t end up being any fun.

Primarily I wanted to express how impressed I am with anyone that manages to finish and release a game. I intend to never say anything negative about someone who has worked hard and put their efforts out for the world to see. I might still criticize the work, but the artist deserves accolades for getting it done.

I also wanted to express to anyone who may have been put off by my hubris that I’ve learned quite a bit about how little I know. Hopefully 2010 will bring lots more learning experiences.

Twitter

I never thought that I would find a use for twitter. But it occured to me that twitter might be a good way of posting project status updates. The hope is that knowing that I have a public log of my productivity will encourage me to do something every day so that I will always have something to post on it. If anyone is interested, here's a link to my twitter profile. I imagine that it will be pretty boring, at least at first, perhaps over time I'll loosen up and post more interesting personal stuff.

Zombie Path Finding: Part 3

Last time I talked about some of the methods I tried that didn’t quite work out. This time I’m going to talk about what I did that finally worked.

Often a problem that is very difficult to solve, can become much easier to solve it you limit the scope of the problem. The more limited the scope, the easier it is to solve. For example, a self aware AI is a very hard problem, an AI that plays games well is an easier problem, an AI that plays a single game well is even easier. The trick is to limit the scope, without making the realm in which the solution operates uninteresting.


So, I decided that it would greatly simplify things, but still keep them interesting, if I changed the rules of how a map is put together. If you look at screen shots I’ve posted in the past, most of them feature a mix of open areas, and tighter areas, but the two mix together freely. So I set it up so that maps can only have two types of areas, open areas, and passageways connecting those open areas. The passageways are only one tile wide. Here’s a good image of a new map.


This breaks the tiles into two types of groups. One group I call edges, the other is called nodes. The edges are bright green in this other image. Barriers are only allowed on tiles in the edge group, which means that if a barricade is put up, the only way around it is through another edge, which means that I don’t have to look at each individual tile and calculate the best path, I can look at the larger groups of tiles instead.

Each node knows how to get a zombie from any tile in the group to any other tile in the group, and knows how to get a zombie to any adjacent tile groups. So there are two levels of path finding going on, the micro level, getting the zombies between individual tiles, can be done once when the level is loaded, or even when the level is built, because it will never change. The macro level, getting the zombies between the nodes and to the goal, needs to be calculated in real time, but because there is a relatively small number of nodes it goes pretty quickly. I only have to process around 22 nodes, rather than around 300 tiles.

Tuesday night I got the zombies to capture buildings again, and the zombies win pretty quickly. So I'll have to tweak them to make them weaker, or the humans tougher, or a little of both. But I'm glad that they are presenting a good challenge now.

Looking at it now the solution seems pretty obvious, but it was kind of a rough journey to get here. It reminds me of something one of my math professors once said. He had shown us how to do a proof, and a student said “Well I can understand it when I see you do it, but I can’t come up with it myself.” The professor replied “Yeah, it’s really easy to watch a strong guy lift weights in the gym, but it’s much harder when you’re the one lifting the weights.” Hopefully next time my mind will be a bit stronger, and I’ll be able to more quickly find these types of solutions. In any case it was a fun problem to solve.

Zombie Path Finding: Part 2

Last time I talked about the requirements I had for my path finding algorithm. Today I’m going to talk about some of the false starts I had, and some of the considerations that makes path finding difficult.

Initially I tried a straight implementation of Dijkstra’s algorithm. Basically how Dijkstra’s works, is that you pick a target point on the map, then move out from that point recording the distance to every point along the way. After you’re done you know how long the shortest path from any point to the target point is. You can use this information to get to the target from any point on the map. From any point, you pick the neighbor that has the smallest distance, and move there, then repeat the process until you reach the target.

It did everything really well, except for the quick recalculations. With a map that is only ten by ten (pretty small) there are a hundred squares, and each time I wanted to recalculate the paths I would have to visit each square and check its distance. This was pretty time consuming. Every time I placed a barricade, or the zombies tore one down, the game would pause for a half second while it recalculated. This was completely unacceptable, especially since I wanted to have maps that were at least twenty by twenty or larger. So I started investigating other path finding methods.

One algorithm that is very popular for path finding is A*, it’s a great algorithm, but not well suited to this situation. Mostly because A* works best to find a path between two points. If I wanted hundreds of zombies running around on the screen I couldn’t afford to run A* for each one, and it’s actually quicker to use Dijkstra’s rather than A* to find the quickest path from every point on the map. So I didn’t bother giving A* a try.

The first alternative I did try was the Ant Colony algorithm. Using this method the zombies would wander the map randomly until they found the target, then they would mark the path they followed, and when other zombies stumbled across the path they would use it. As more zombies followed the path, it got stronger, and even more zombies would follow it. There were two big problems with this though. First, it would take forever on a big map for the zombies to find the target point, once they did you would have every zombie on the map running at you as fast as they could come. But until then they wandered around aimlessly, and it was pretty boring. The other problem was that if they did manage to find a path, and you cut it off with a barricade, they would have a hard time routing around the barricade. It all became very noticeable on larger maps.

I tried another idea where I had the zombies do a breadth first search. Basically I marked the tiles that hadn’t been explored yet as the most interesting. The zombies would move in the direction that was most interesting to them. Tiles that were farther away from explored tiles would be less interesting, so the zombies would naturally spread out and explore. The most interesting tile was the target tile, so when the zombies found that one they would tend to move towards it above all the others. This did a good job of getting the zombies to spread out and search, but similar to the ant colony method, they took a long time to find the target tile.

I decided to give Dijkstra’s another try, but decided to see if I could find ways to reduce the number of calculations that had to be done. I figured it might be a good idea to break the map up into groups of tiles, then navigate between the groups of tiles rather than between the tiles themselves. That’s where I got into trying to calculate choke points, because a choke point would make a logical place to end one group of tiles, and start a new one.

So I started looking at ways to find chokepoints. I wrote some routines to go over the map and mark the tiles different colors based on how good it thought they were as candidates for chokepoints. The brighter the green, the more likely that the tile would make a good chokepoint.


None of them really gave very good results, although they were kind of interesting. This image shows the rankings based on which tiles have neighbors that are farther away from the target point. The idea was that if a tile has a lot of neighbors that are farther away, then more zombies will go through that tile on their way to the target.

This image shows the tiles that have a small number of neighbors. I thought that if a tile had a lot of neighbors, then it wasn’t as important because zombies would have more options when moving through the area, and could use one of the tile’s neighbors.


This image shows the tiles that have more options of where to go than their neighbors. This one seemed to have promise, since most of the tiles I would pick as chokepoints were also highlighted by this method. But it also highlighted a lot of extra tiles that weren’t important.


The last method I tried was to see how removing a given tile affected the distance of all of the other tiles. For each tile on the map I would remove the tile, then recalculate all of the distances, and check the new average distance against the old average distance. The greater the difference, the brighter the green. I figured that if a tile increased the average distance by a lot, then a lot of paths must pass through it, which would make it a good chokepoint. Unfortunately, while almost all of the tiles it picked out could be considered important, there were a lot of others that were important that didn’t get picked out.

I tried several other methods besides these to figure out which tiles were the important ones, but I finally decided that I needed a better approach, I needed to narrow the scope of the problem. So I found a way to greatly simplify the problem that I was trying to solve, but still keep things interesting. I’ll talk about that next time.

Zombie Path Finding: Part 1

If you’ve been following my blog at all, you’ve probably noticed that it’s been over a month since I posted anything, but there’s been a good reason for that. Remember how I said that I’ve discovered that in game development gameplay balancing is the hard part, and implementation is the easy part? Well, I was wrong; they are both the hard part, probably along with some other hard parts I haven’t discovered yet.

I’ve been working on the path finding for my game, and it’s been a real beast, but I’m happy to say that I believe I’ve come up with a really good solution. I’d like to take you through how it works, and the process I went through to get there.

I realized I needed to do something very different with the path finding when I tried creating a big map. It took so long for the zombies to find the target building that I didn’t even have to do anything to win, just wait, it was pretty boring. So I sat down and came up with several requirements that I needed my path finding algorithms to satisfy:

• The zombies had to be able to find the target building from any spot on the map
• The route had to be able to be recalculated very quickly to route around barricades
• I wanted the route to be non-deterministic, so that all hundred or so zombies wouldn’t follow the exact same route through the maze
• Route calculations for each zombie had to be very quick, since I was going to be routing possibly hundreds of zombies around the map at once

Individually these requirements wouldn’t be too bad, but together they presented a real challenge for me. I spent a lot of time looking at graphs, and trying to figure out clever ways of handling things. Eventually I realized that in most of the maps there were a lot of wide open spaces that narrowed down to choke points, and that if I were to route the zombies between the choke points, then I could save myself a lot of calculations. So I started coming up with different ideas on how to mark those choke points.

As a human, it’s pretty easy to quickly pick out potential choke points, but that’s because we tend to look at the whole map at once, and do parallel processing to figure out which points are important. A computer can only look at one point at a time, so I had to come up with some heuristics, or rules of thumb, that would allow the computer to quickly determine which points would serve as good waypoints on the map.

Next time I’ll talk about some of the methods that I tried that didn’t quite work out, and some of the difficulties of the problem.