Articulated Body Algorithm – first video

January 7, 2011

Update: my code a.k.a. Rigid Body Dynamics Library is now available at http://bitbucket.org/rbdl/rbdl

During the last month I was working on an implementation of Roy Featherstones “Articulated Body Algorithm” which is one of the most efficient algorithms for simulating the dynamics of articulated figures. It has an asymptotic complexity of O(n) with n being the numbers of degrees of freedom. Here is a first video of a simple OpenGL visualization I hacked together yesterday:

I used Featherstones book “Rigid Body Dynamics Algorithms” which I highly recommend to anyone undertaking this task(*). Additionally I used Featherstones Matlab Code of his algorithm that is available from his site at http://users.cecs.anu.edu.au/~roy/spatial/index.html to verify my results. I also used The HuMAnS Toolbox to double check my implementation. Furthermore I used exhaustive unit testing (algorithm + library: ~2600 lines of code, automated tests: ~1500 lines of code) to make sure I don’t brake things too much or at least have some feedback what I am currently breaking. Thanks to UnitTest++ this was nice and easy.

Now what is remarkable about this video is that it is the first time I see my implementation in live action. Before that I only knew from my tests and the comparisons that it is correct. It is comparable to flying blindly through fog only by using your instruments and trying to land. Luckily this bird has landed! … actually using “luckily” here is rather odd… let’s go with: WICKED!

(Even though the instruments said it is all right it is very nice when the sun comes out suddenly and you have landed very well and are already at the correct parking position.)

*Some things to note about the book:

The book is also very useful for other well-known algorithms used in robotics and mechanics, such as the Composite Rigid Body Algorithm or the Newton Euler Algorithm, as this book is very clear and complete. It also discusses other topics such as system with closed (kinematic) loops, impacts and other stuff. Additionally there is a detailed section about efficiency and how to implement the algorithms. For every major algorithm there is always the mathematical expressions next to the actual pseudo code for clarity – nice!

Spatial Algebra

But The Best Thing Ever™ in his book is the spatial algebra he uses to formulate rigid multi body problems. It is a very sleek way to overcome the hassle of using two types of equations: one for linear motions and forces (translations, etc.) and another one for rotational motions and forces. Instead of the two 3D equations he uses one 6D equation that is further grained with Screw Theory. It takes some time to get the point of it all, but it absolutely pays off once one understands the elegance of it.

There is also a very good 2 part tutorial written by Featherstone concerning spatial algebra, which is published at the Robotics and Automation Magazine in the two recent issues which you might get through here:

Update: link to the September issue of RAM pointed to the December issue, now fixed.

Asteroids Beta 1 (update)

December 1, 2010

Wahoo!!! It looks like I am getting somewhere with my Asteroids clone. It took me much longer than expected that far, but I do think I learned a lot on the way. Initially I started it because I realized my game programming demons that prevented me from actually writing a game. Instead I was only talking to myself that I would program game X at some point and programmed smaller things with which I could delve in the illusion of programming games.

However you don’t make a game unless you make a game. And that’s what I did – although I have to confess something: the game is not yet finished. There are two remaining tasks that I want to work on before I would dare to call it a completed game. These tasks are testing and additional levels.

Things still todo…

I guess the experienced game designer/programmer might smile at this point, especially at the latter part, as levels are probably one of the trickiest things to do. They have to make the player at first curious, then be challenging, but not too hard, and not too easy, oh and not boring. However I do not plan to make this game perfect and therefore I am not going to make more than, say 20 levels. So far there are 5 levels with more or less increasing difficulty except the 5th which is a bit of a steeper step. The game mechanics will stay the same for future levels and there won’t be crazy new game elements, because I do not want to finish a game and not go on an endless journey of ideas.

Right now I need to do some testing (done by YOU* !) to find problems that I haven’t found yet. I am starting to not see issues because I am already too much in the technical viewpoint and got used to a play style that probably circumvents all issues that other people might have. Therefore I need some non-biased feedback from people without knowledge about the details. I already showed the game to a few people and had the chance to watch them play and I am fairly satisfied so far.

Now cut to the chase!

You can download the windows version from here:

I tested it under Windows 7 (64bit), Windows Vista (32bit), and Windows XP (32bit). I do my development under linux, but creating packages for that is a bit annoying. If someone wants to run it under linux, I will gladly send you the code and help you make it run.

Update: there is now also a Debian/Ubuntu (64bit) package available here:

Here are some screenshots, to get an impression how the game looks:

A few words to the style…

I tried to keep the style more simple and not do fancy OpenGL stuff. This has two reasons: first I am so far not much of an OpenGL guru and shader ninja, and second for a game like this a more ‘classical’ style fits very well. I tried to use filtered sprites, but that made the game look like strangely cheap. I hope the following picture conveys this somehow:

Also together with the font I am using it all looks a little more retro style. I do believe that it is more important to find a fitting style than to have graphical excesses (however I totally do not mind them, rather the opposite). But for a lone-wolf production like this I have to take what I can make myself and so far I am very satisfied.

Some Credits

Here is a non-exhaustive list of libraries that I am using for the game (in no particular order):

The music I am using is from DJAD and is called Space Exploration. Other than that I am using various sounds from http://freesound.org that I have customized (I still have to make a proper list for the credits).

All right. So much for now.

Have a nice day!

(* all right, there are not too many people passing around here that might be inclined to test it, but I still thought I’d make it clear that you are cordially invited to test and give some comments.)

Blinking Cursors

July 16, 2010

When having some sort of keyboard input it is always helpful to have a blinking cursor, so that the user knows where he/she/it is typing. This is usually shown by a blinking pipe ‘|’ or underscore ‘_’ symbol. In my current asteroids I didn’t bother with the blinking and simply appended a static underscore to the current input. However I was just reading a nice post about immediate GUIs at http://sol.gfxile.net/imgui/ch01.html (very interesting way of programming a game user interface!), which also had a very nice trick to have a blinking mouse cursor with pretty much no effort. You find it in chapter 7 of that tutorial.

The trick is:

std::string name_output (mPlayerNameInput);
if ((SDL_GetTicks() >> 8) & 1)
	name_output += "_";
DrawGLString(xpos, ypos, name_output.c_str());

SDL_GetTicks() is the time function of the SDL library and simply returns the number of milliseconds passed since the initialization of the SDL library. By shifting the value of the function to the right by 8, the resulting expression in line 2 alternates now between true and false each 256 milliseconds. If you want the blinking every half seconds, shift it by 9 bits.

Awesome!

Tags

Asteroids: first flying rocks

March 24, 2010

As I mentioned in my previous post, I decided to get a rather simple game done instead of dreaming of bigger ones. So far I think I was quite successful. I tried to reuse most of the code I already had and it was very helpful to modify my existing code towards a very clear playable game.

The game itself is already playable and I have a basic menu and basic gamelogic (you have 3 lives and once you die you’ll see the game over screen) and I can load and save levels. At first I thought of using 3d models by using the cal3d library which I already use in my research project, however I reminded myself of keeping things simple and created some nice sprites. I added PNG support by using libpng to be able to load sprites with transparency and also added simple animation of sprites. In the background the stars are moving sideways to give a slight 3d effect (looks very nice!).

What is still missing is sound and I need a few more animations (ship exploding, asteroid exploding). Additionally I do not yet count any points and some non-asteroid (maybe some powerups) would be nice to add more fun to the game.

Enough prose – here are some screenshots:

the menu

asteroids in action

game over screen

My game development demons

March 8, 2010

It’s been now a long time, since I decided to write a certain game and talked a lot about it with friends. However I must confess, now after a few years, I still haven’t managed to finish a game. I wrote a lot of code and both bugs and documentation is so far not the problem. Instead there are a couple of demons that  slow down the process that I would like to introduce to you (you probably know them already):

Efficiency Demon: This one is always in the back of my head. It tries to convince me not to use virtual functions as they are somewhat slower than normal function calls. However this approach makes things a lot more complicated and I spent time to circumvent the usage of “the single most important feature of C++” by using probably less efficient detours. Additionally following strictly the rule: first make it run, then optimize would encourage me to take a deeper look in profilers, which would be definitely a knowledge I wish to possess. There are a couple of nice quotes to this one on the Wikipedia page on program optimization – I guess I am not the only one having this demon.

Engine Demon: Instead of tackling simply completing the game logic/event managing/input handling part, I try to generalize what I just coded and put it into a part that I call “engine”. This “engine” is some kind of container of reusable code that I will most certainly need in the future. The catch is just: I do not yet know what exactly I will be needing in the future. Actually neither whether I need the generalized case nor the specialized I wrote in the first place. There is a very well written article (write-games-not-engines) from Josh Petrie which talks about this one. This demon is sometimes called Premature Generalization.

Beauty Demon: The Beauty Demon is related to the Engine Demon. It makes you want to clean up your mess (a.k.a. code). You just hacked in some features and now you want to polish it a little. So you polish. Then you realize you should add documentation. So you add it (and look at the beautiful caller graphs that Doxygen creates automatically for you). Then you realize that you could create of this feature set a library against which you can link dynamically – oh yeah, this is great, because then you can do this for all the other games you will write and reuse it. Oh, and the build system it got a little messy. How about … Yeah, you get it. You do a lot of things which are actually very useful. However they do not complete your game.

Just-that-feature-and-then-I’m-done Demon: I coded hard. The prototype works. And I am very happy. So I relax and think: Awesome, I’ll be done soon with the whole game and I can finish the rest tomorrow. There is a huge difference between a prototype and putting it into your game. I had a few nice parts, such as an event system and entity management system and so on which worked very well on them selves. But when I actually tried to make a simple game with it, I had to rewrite a lot of it and it was a lot harder than I expected. So unless the code is not in your game don’t think anything is done! (Please note that this is not an argument against writing prototypes – they are very important because you realize what the actual problem is and what kind of difficulties you run into!)

A long time ago, I read this very inspiring article ‘How do I make games?’ A Path to Game Development.When I look back, I must admit, I skipped quite a few steps suggested there. So last week I started to abuse my “engine” to create an Asteroids clone. So far controlling the ship, destroying asteroids and getting killed works, but there are still some areas untouched (menu, game-over screen, etc.). It took me a lot longer than I expected and I currently have a lot of quirks on making things work.

So far it is not efficient, not an engine, not beautiful and there is still a lot of work to be done. But I’ll stay on that rocky road and bring it home.

Thought game development is fun? It is – but getting it done is actually quite hard!

Tags

About the View in a Model-View-Controller

February 25, 2010

I recently bought the third edition of the book “Game Coding Complete” from Mike McShaffry (a.k.a. MrMike) et al. which has been very delightful to read so far. I have been reading a few chapters which gave me a new way of looking at game architecture and other things that I was convinced that I already understood them quite well.

One of them is the famously known Design Pattern: the Model-View-Controller. To me, the Model always was the data that is being modified, the Controller takes care of the input (mouse, keyboard, maybe network, …) sent to the application and the View simply displays the data. If you want to improve graphics – you work on the View. You want to update keybindings in your input system – you’ll modify the Controller. Also the Controller keeps track of the player id that tells us which entity is being controlled by the player. Need a new type of vehicle / weapon? – Go to your Model (and of course, add code to the Controller and View to reflect them).

So far so good.

However in this book Mike gives an overview of a game architecture consisting of three basic parts: the Application Layer, the Game Logic and multiple Game Views. The Application layer hides the platform specific from the game and the Game Logic resembles what is going on in the game. The Game Views represent the game from different perspectives e.g. for a human player or a AI agent.

Game Architecture after Mike McShaffry

At first my head tried to map them onto a Model-View-Controller which failed as they resemble completely different things. Especially the description of the Game View gave me a different way of looking at the View in a Model-View-Controller. The Game View does not only display what is going on in the game, instead it also takes care of the input handling. More specific: the Game Views receive all the input events (key presses, etc.) and communicate with the Game Logic over events.

At first this seems a bit awkward concerning to what I wrote further up concerning the View, but giving the view the ability to receive input and send events has some nice properties. For example it might be “easier” to add a split-screen mechanic as each player has its own Game View (remember: we have multiple Game Views!) and also its own keybindings. Also one could imagine having a GameEditView which has completely different abilities than e.g. a HumanGameView. This gives the View more power as it also contains not only the way how you look at things but also how you interact.

Maybe I got it all mixed up, however I think it one shouldn’t be too strict on saying input is clearly handled in the Controller or that the job of a View is drawing only.

Tags