So last week I’ve been participating in this years global game jam with theme ‘extinction’. The location here in the Netherlands being the HKU in Hilversum, having over 140 participants in total. I was invited by the people of Digital Dreams Games since they needed a second programmer on the team. The game we created is called FYI (see here and here for downloads and more info), and is a platformer puzzler game based around the concept of infographics. Every action you do in the game affects the platform elements in the game (bar graphs, circle graphs etc), so the trick is to do all the correct actions such that all the elements are in their right state (with bar graphs its having them at correct heights for example) to finish a level.

During the 48 hours we made the game, we did some things right and we did some things that we could have done better in retrospect, so I decided on a quick writeup for some obvious tips.

- Throw away your first three designs. This is one tip that the organization proposed as well and i think that really worked out well for us. The idea is that the first three ideas you are going to have, are also the ideas that other people are going to have and are therefore not original enough to be used.

- Make sure you have a good source control system in place. Source control can benefit greatly to the production efficiency, so be sure to use it. We used dropbox as our tool, which was not the best choice to make as it has no version history and no merging capabilities. This arguably cost us a considerable amount of time, since effectively we couldn’t work in the same files at the same time, and face overwrites of files on previously made changes.

- Have a good assets pipeline. If you start on building a game, make sure that when you have finalized assets that they can be placed into the game immediately without intervention of other people. This means first of all that the team has to decide what kind of assets are needed and in what format, size and orientation they will have to be. Take empty space into account when you are using sprites; as an artist think what the asset is supposed to be doing. The programmer needs to have the piece of code to use that asset into place using placeholder graphics such that the only thing that has to be done is replace the assets when they are ready, which the artist should be able to do just by overwriting the placeholder. The next thing to do is have all variables in a separate class such that they can be adjusted easily also by a game designer. Make sure you don’t hard-code levels into your game for the same reason.

- Don’t manically code stuff together with all kinds of pieces from earlier projects because of the time constraints. Honestly, piecing together sections of code from other games is just as fast as coding from scratch, but causes the game code to be chaotic, bloated and incomprehensible quite fast. Try to setup your code base similar to how you would normally do, add structure and try to keep everything as tidy as possible without spending a lot of time on it. If you want to use previously written code, set it up in such a way that it can be easily integrated for example by making it a library.

- Have a clear idea on what needs to be done. It is really an obvious tip, but in the hectic hours of the jam this is easily neglected. Have a board up with post-its, a site to track those things or something similar. It will ease communications and have a positive effect on production efficiency as you can easily prioritize TODO features, see who’s working on what and so on. Also don’t have long arguments on how things should be looking, and don’t spend a lot of time on changing things that had been finalized unless it is absolutely necessary.

- Get sleep and eat healthy. Even if its only 48 hours, even having four or five hours of sleep a night will help you to see things clearer, and makes you work more effectively then when not sleeping at all. It was really a disappointment to see the organization serve french fries and other fried junkfood the first day as if it is inherent to the whole thing. Eating fruit and veggies and drinking fruit juice are a better option always ;)

- Utilize the knowledge available in other teams. It may sound a bit odd, but ask other teams in the event for quick advice when you’re stuck on a problem as it can save you precious time.

I’m sure there are plenty more tips to go around, but these are the most obvious ones in my opinion ;) All-in-all it was a really cool experience to participate in the global game jam, i really encourage people both veterans, starters and students to participate and make cool games together. The organization did well, and breakfast and lunch at least were up to spec ;)

As promised, a first post on path finding solutions for games. The first structure I’m going to treat are so called waypoint graphs, and are still commonly used in games regardless of their downsides, mainly because of their simplicity.

A waypoint graph is actually a very simple concept; positions in the free space (so, the area that a character is supposed to be walking on) are sampled either by hand or by algorithm, and n‑nearest neighbor points are connected to the newly sampled point by an edge if no obstacles are detected between the two points. It is one of the most classical solutions used in games, and is still being used by games today. Short paths are found by applying A* on the graph. Start and goal configurations would be added to the graph as temporal waypoints and characters would move from waypoint to waypoint until the goal is reached.The problem with this is method of course is that it doesn’t give any idea on the boundaries of the free space, so the coverage cannot be optimal by definition and is dependent on how many waypoints are used. In other words, characters are stuck to using waypoint routes, and deviating from the path isn’t really possible unless you perform a collision test on the intermediate path to check if it doesn’t hit any obstacles. On of the games that recently came out still uses this technique; Alien Swarm by Valve. In Alien Swarm there are many waypoints, and they are all connected with a lot of neighboring points. Collision detection is used to check if a path is actually valid and disabled if not (see screenshots). The main reason this is done is because the environment can be dynamic. For the paths in a limited area where the environment is dynamic and changing, new paths are added if they are free from collisions with the changed environment.

Waypoint graphs can also be extended to include a radius. These kind of graphs are sometimes referred to as circle-based waypoint graphs. The idea is that characters may only traverse from waypoint to waypoint if their circles are intersecting. The improvement over a simple waypoint graph is that a circle-based waypoint graph approximates the free space. The problem is that when waypoints are placed in arbitrary locations, the approximation of the free space may still be fairly inaccurate, which means that characters still can’t reach locations that are visibly reachable. Also, the denser the environment is, the more waypoints you will need generally because the circles of the waypoints are smaller. By placing the waypoints along the medial axis of the environment (the axis on which the distance to two different obstacles is equal) you can insure connectivity.

Next time more on waypoint graphs ;-)

By the way, Alien Swarm is freely available on Steam.

So, recently there have been a couple of new videos that illustrate ‘new’ techniques in path planning and especially crowd simulation for games. The first is on so called flow fields in supreme commander. Although it is a really nice new way of doing things, especially in the example where large units move to a group of smaller ones the behavior to my opinion is still unnatural as small units literally get pushed out of the way:

And the second is on path planning in the upcoming Starcraft 2; I don’t really know much about the techniques used here, but it looks as if they combine local force methods with A*. It looks cool but again the behavior of the zerglings sometimes is a bit unnatural still, some odd patterns can be seen when the units are packed together:

In light of my thesis project, I said to try to blog more and focus a bit more on the subject of my research, which is about path planning for characters in virtual worlds, specifically related to constructing paths in complex 3D environments (environments which have tunnels, bridges and such). I still intend to do so ;). I’m not yet sure on where to begin, but I will make it thorough and worth reading for one :) I’ll cover A* of course, one of the most famous of path finding algorithms, but I will also move on to other things, like navigation graphs and navigation meshes, and also some lesser known methods such as the corridor map method which is being developed at Utrecht University (and where I am working on to do path planning in 3D environments). I might also consider several methods to simulate crowds as well, since games tend to get larger and larger and therefore whole cities are being populated with characters which move through the city (for example in the Assassins Creed series and the Grand Theft Auto series). To be continued… ;)

So it’s been quite some time since I last blogged, a lot of stuff happened since, so it’s about time I’d blog again. The experimentation project in the end didn’t turn out to go very well as for the game, but a lot of lessons learnt nevertheless. The only thing left to do is write a document on how best to incorporate Ogre3D within a game (engine), as I changed my topic to reflect my tasks within the project more (didn’t do much special camera stuff as there was no time). The game I was supposed to make for DBP didn’t go through as my experimentation project took all of my time troughout the summer, which is a bit unfortunate.
Fortunately I finished some courses as well; I did a course on Path Planning and Crowd Simulation which was really cool, and I retried for Motion and Manipulation, which is essentially a robotics course mostly related to planning paths for robots that have a certain degree of freedom, forward kinematics for robot arms (and thus also skeletons in games), high level collision detection and the grasping of objects and such. The course has a lot of things in common with other courses like path planning, but also computational geometry and virtual worlds which itself is mostly about physics and network related aspects of virtual environments. Having finished that course which was actually my last one, I am now preparing to begin my Thesis project :)

« Older entries