La Venaria Reale

On Easter Monday, for the traditional “Gita fuori porta” (out of town excursion) we went neat Turin to see the Venaria Reale an old royal palace repaired and rebuilt to its ancient splendor.

Finding the Right Path

After yesterday’s post, PaoloMan reminded me about how he and Piggi changed the CEngine pathfinding system simplifying the level design by at least an order of magnitude. In fact I had the intention of writing about their bread crumb pathfinding algorithm, but the good will got lost in some interruption of my editing. Anyway the matter is interesting and would be a pity to settle this matter with few lines embedded in another topic, so I am happy that my subattentive mind left out this yesterday.

In the beginning it was [|Rainbow Six: Rogue Spear]. This was the first game of the studio on the then new GameBoy Advance platform with the quite ambitious goal of recreating the playing experience of the PC version of the game.
Pathfinding was needed for a number of actions of non-playing characters. Terrorists had to be able to find their way toward noises they heard, or to the last known position of their pals. Counter-terrorists had to manage to stay together following the player controller team leader.
A full A* algorithm would have been likely to be daunting on the poor ARM 7, so I devised a lighter system for all these pathfinding needs (well the idea was mine, but later I discovered it was already employed by other game engines). The idea was to define a routing network of nodes connected by straightly “walkable” rails. When a character needed to go from its actual position P to a remote position Q it queried the pathfinding system for the routing node closest to its position P. Then it asked the node for the next node in the network in order to get close to Q. In overly-simplified pseudo code it would turn out like this:

currentNode = findNodeClosestTo( P );
targetNode = findNodeClosestTo( Q );
walkTo( getNodePosition( currentNode ));
while( currentNode != targetNode )
    nextNode = getNextNode( currentNode, targetNode );
    walkTo( getNodePosition( nextNode ));
    currentNode = nextNode;
walkTo( Q );

Although the gameboy side of the algorithm was simple (even with extra code for a more realistic behaviour of characters) and fast (provided a way to quickly find the nearest node you can walk to) two non trivial problems had to be solved on the editor side.
First – networks had to be hand drawn on each map and – second – routing tables had to be computed for each node.
The reason for requiring manual work to draw networks was simply because we didn’t have enough programmer time to put the right amount of AI in the editors. One of the constraints of the project was the maximum reuse of GameBoy Color editors and tools we developed for [|Rayman GBC] and minimally improved over the next two GBC platform games. This meant that editors didn’t understand the 3rd dimension.
So level designers had to hand draw the network taking care of connecting nodes with walkable line, trying to be very careful when more than one terrain level was involved. Also it wasn’t easy to test and debug the network. First you had to flash the game on a GBA and play it. A quick play throughout the level could not show any flaw even with a flawed network.
A properly designed routing network affected how realistic would be the movement of the characters, so networks were subject to several fine tunings.
Routing tables creation was not that hard, but the “easy way” my fellow programmers took first involved several hours of number crunching on the editor PCs. Level designers were quite mad at us for this daunting weight.
Lear produced a new and much more efficient construction algorithm, trimming down the network computation to a bunch of seconds.
But we were talking about Lara and the prophecy. Well it was clear that laying out routing networks was a big problem, luckily the AI needs for this game were quite modest. The pathfinding would have been employed for enemies to chase the playing character only after a walkable contact have been established.
PaoloMan and Piggi came out with a clever mechanism that allowed us to get rid of pathfinding networks and the related burden. The idea was to have the main character to drop virtual (and invisible on screen) breadcrumbs. When the chasing enemy loses direct sight of Lara (maybe she just turned around a corner), he can search the most recently dropped crumb for walkable way. If the most recent is not accessible, then he should go backward in time until he find a suitable one. It is like the main character defines a subset of a routing network just for the area where she is.
Talking about pseudocode, this approach would be something like:

// breadcrumb 0 is the current character position,
// 1 is the most recent and so on
breadcrumb = getBreadCrumb( Lara, 0 );
// find the most recent breadcrumb you can walk to
while( !canWalkTo( breadcrumb ) && i < MAX_BREADCRUMB)
    breadcrumb = getBreadCrumb( Lara, i );
    // give up
// now just follows the trail
while( i >= 0 && ! canWalkTo( Lara ))
    walkTo( getBreadCrumb( Lara, i ));
if( i > 0 )
    walkTo( Lara );

What I find notable is that, when working with games, standard solution to known problems (e.g. the A* for pathfinding) could be overwhelming or too daunting both to implement, to run and to manage. Having a clear vision of the needs of the game can point you to a proper, more efficient and simpler solution for the problem.

Tomb Raider – the prophecy

PaoloMan sent me a link of a video review of Tomb Raider – the prophecy the game we developed some years ago when I worked at UbiStudios. The development was quite a challenge – we have to reuse as much as possible from the previous game – [CV-projectDesc-RS.html|Rogue Spear] and write, test and debug the whole game in three-four months.
With [CV-projectDesc-RS.html|Rogue Spear] we had developed a pretty robust engine for isometric view able to handle a couple of terrain levels – the CEngine. On the constrained hardware of the GameBoy Advance, the CEngine happily performed line of sight and line of fire tests, room occlusion, automatic generation of level maps, pathfinding, managed an impressive number of enemies on the whole level and provided reliable support for multiplayer game.
When I was informed that the studio was going to develop this game and that I would have been the lead programmer most of the decisions about the kind of game we were going to make were already taken, but, they assured me, it is as close as possible to the previous [CV-projectDesc-RS.html|Rogue Spear] game.
Good I thought. Unfortunately the old saying about a non-programmer pretending that two systems are the same meaning that they do not differ more than 50% held in that occasion too.
In fact the game had to preserve the Tomb Raider key game plays: jumps, vertical vertigo effects, puzzles and extinction of animals. Jumps was something unheard in a military simulation game such as [CV-projectDesc-RS.html|Rogue Spear] and the vertigo effect was hard if not plainly impossible to achieve with just two levels of terrain. Editors and tools were the same of the GameBoy Color games we did, i.e. 2D platformers without any notion of elevation. They already posed a number of headaches with the quite-flat world of [CV-projectDesc-RS.html|Rogue Spear], I wasn’t willing to think what could happen with tens of levels.
Puzzles was another head-scraping aspect of the game. I knew that every factor of the gameplay was going to be refined, modified and touched an uncountable number of times before the Gold Master, and I didn’t want a programmer to be dedicated to change and modify code to this purpouse.
Cut scenes were also required and the camera needed to move around, far from the main character, to show the effect of various switches and devices or the goal of the level.
Another problem was posed by the animation system. The CEngine animation system suffered from the [|Rayman] modular animation. In Rayman many animations were performed just by moving fixed shapes around. This approach was intended to save space and Rayman character itself was designed around this idea, but it is ineffective at most when you have to animate life-like characters. Lara had an impressive number of actions that really stretched the limits of the poor handheld system.
How we made it was a successful combination of hammering, ingenuity, compromise.
The CEngine proved to be well designed and well coded with good insulation between layers of game related abstraction levels. My fellow programmers were top notch and brightly solved a number of problems. Artists and Game Designers were great to understand technical problems and helped us in finding suitable compromises. And we managed to get the game throughout the whole process in three months and half.
How we did it?
About the number of levels we changed the physical property encoding of the terrain. CEngine provides a single byte to encode the physical property of each 8×8 pixels square. Such properties defines whether the place is dangerous to the main character or a solid wall or a plain, walkable terrain.
In [CV-projectDesc-RS.html|Rogue Spear] three bits were allocated to sound properties leaving just 5 bits for the rest. 8 elevation levels allowed to define two floors and the connecting stairs/slopes. Also the slopes needed to be both vertical and horizontal to accommodate for climbing and descending both ways. This allocation leaves pretty no space for more levels.
Well but if Lara Croft can jump why do we need slopes? So here we get back our slopes code allowing for 10 different heights, enough for the vertigo effect.
Nonetheless it was impossible to design such maps with the old 2D editors. Luckily [|another GBA game we were working on] at the same time needed a better editor so the management decided we had enough “needs” for a new editor. Alberto worked on the editor for about one month and something accomplishing a remarkable result before game designers actually started designing maps and levels.
Another bright programmer, Valentino, worked on the puzzle system. Rather than hand coding each puzzle as a specific C code, he defined a set of devices that could be connected in many different ways to provide enough flexibility to implement any kind of puzzle. At the end the mechanism proved to be still too complex for non-programmers, but he managed to implement and maintain the whole system alone with minimum effort.
Cut scenes were a major problem – we didn’t have the resources for developing a cut scene authoring editor, nor we could afford movies in the game for cartridge space constraints. We came out with a simple idea that turned out to be a nightmare to use. The simple idea was to have a dummy character able to play any animation, then for each character in the cut scene a path had to be drawn where each node contained both timing and animation code.
Although the idea was simple, creating cut scenes this way was a burden. Synchronization among characters was impossible, modifying an existing sequence was a painful operation. At the end the producer Nicola went through all the cut scenes fixing and sometimes recreating from scratch all these meaningless number tables.
The number of Lara action posed another problem. Design document asked for some 40 basic actions to be performed in all the 4 available facings (left, right, up, down). Moreover some of these actions could be performed both with guns drawn or not. Moreover guns automatically aims to the nearest target in discrete steps of 8 directions. Even relying on the hardware horizontal flip for some animations, the resulting number was huge. We managed to handle them all by splitting the character in half: legs and arm with chest plus head. Thanks to this trick and some twiddling in the actor code we avoided the need of writing compression/decompression code for animations.
Given all that, the fact that the lead game designer resigned in the middle of the project, the fact that a change in the Eidos management near the Gold Master forced us to rework a number of license issues and the other GBA game developed at the same time by the same people, I don’t hesitate to call Tomb Raider – the Prophecy a great success. Back then it won’t earn much credits to the studio since it sold much below the expectations and got several mild reviews that’s why I am happy to hear that people love it (the video reviewer score it at 10/10).

Thank you for welcoming

It was quite a time I wished to add this old document to the my website. A new section (not yet visible from the blog, but visible from the rest of my site) is intended to host my memories of those bright days the Universe was young, full of High Ideals and Good Ideas and I worked in the Videogaming Industry. The story of “Grazie di Benvenirli”. I started that document somewhere in 2001-2002. From a chronological point of view I would say around the Silver Age. Soon after I started typing some HTML code I realized that the right choice was to use some software to manage dictionary entries. The then-new wiki seemed to be a good idea, but it lacked a dictionary-oriented style and the “printable” layout. So I wrote Webdict a rather rough web application, my first PHP program, and installed on a company internal web server. My coworkers accepted enthusiastically to add their contributions and the dictionary grew for a while. Unfortunately the server was put off-line and recycled and the webdict content went lost.
The surviving part you can read is mostly my contribution, what I wrote in HTML. I gladly welcome terms and definitions to add from all my friends and coworkers of those glorious days.

Here you are…

… the much awaited [|pictures from the last summer vacation]. Most of them have been shot by my nephew Matteo, kudos to him. USA parks in Utah are the among the best place we have ever been, look at the photos a judge yourselves. This new kind of photoalbum is a little different, a bit more tricky to handle behind the scene. Let me know if you find any quirk.

Alsace on-line

The more ESP talented of you have already noted that I made our [images/photoalbum/Alsace/200704/index.html|last vacation photos] on-line. For those who can read Italian I just uploaded the [downloads/Diario_Alsazia_2007.pdf|travel log] as well.I hope you enjoy both. As usual comments and critics are welcome.

RSS broadcasting

This feature is still beta, but I am so proud, I’m going to tell you without waiting for a complete bug-free version.If you point your favourite feed reader to [] you will receive my blog post without having to visit daily (or so) my website.
If your favourite feed reader is Firefox Live Bookmarks, then maybe you HAVE to wait for a more bug-free version 🙂