Friday, February 27, 2009

World Collisions

Left alone, testpoinst are not really a satisfactory way to handle collisions between objects of a game and the world.
First they don't cover enough and cannot catch all the odd situations. Testpoints are points and they cannot detect the case where you're jumping through a corner unless you have many of them (up to one per tile your character covers).


Je ne suis plus trop emballé par les tests-points tels que je les avait décrit précédemment. En premier, ils ne capturent suffisamment toutes les collisions. A moins de les multiplier, on risque toujours d'avoir une partie du personnage qui rentre dans un coin de mur lors d'un mouvement, et en donnant à chaque état sa propre liste de testpoints, on ne fait qu'augmenter les possibilités de bugs.

Second, they are only boolean. They don't let you express that a fish can only move into water, that a bird can only move in air, and that a frog can move through both, but that only the ghost can also move through walls (and i'm sure we can come up with a negative space creature that can only walk through/over walls). This is a situation much more common that one could think. As soon as you add ladders to your levels, you want to express that climbing the ladder "is only possible over ladders tiles". That was a quite strong restriction of Recreational Game Maker where the only way you could create a ladder for a platformer game was to set gravity=0 on ladder tiles ... As a result, your character zooms through ladders if you press the 'jump' key and miserably 'fail to climb up the air' if you press the 'upwards' when he's not over a ladder.

Le deuxième souci avec les test-points, c'est qu'ils sont simplement binaires. Alumés ou éteints. Point barre. Pas moyen de préciser qu'un poisson ne peut se déplacer que dans l'eau ou qu'un oiseau ne peut aller que dans l'air, mais que la grenouille peut évoluer dans les deux milieux. Si on y réfléchit bien, ce genre de situation apparaît bien plus souvent qu'on ne pourrait le penser. Le simple ajout d'échelles dans nos niveau oblige de définir que "escalader une échelle" ne peut s'envisager que s'il y a une échelle à escalader. Le Recreational Game Maker sur lequel j'ai développé (entre-autres) la série des badman ne permettait pas ce genre de subtilité: une échelle était tout simplement un bloc sans gravité, de sorte que l'on pouvait y monter en sautant -- à une vitesse franchement irréaliste -- et on aurait vu le personnage ridiculement patauger dans l'air en faisant de petits bonds si on avait appuyé sur la touche "monter à l'échelle" alors qu'il n'y avait aucune échelle.

The approach of "the nature of a tile" is thus interesting: it can express (through flags) who can do what over that tile. This is a concept used both in Xargon and (afaik) in the side-scrolling Rayman game, where you have "monster-walls" that monsters can't cross (though Rayman don't feel them). This is imho an elegant solution to many level design problems. Let's take the walking block of "Inside the Machine", who wanders around its initial location, "guarding" a virtual spot even if it could theoretically walk further. Morukutsu relied on a "distance" counter that is increased/decreased through the animation code, which won't let you alter the 'coverage area' of the ennemy through level design, but only through implementation ... not so fun.

L'approche "nature du tile", telle qu'elle est utilisée dans Xargon est intéressante à plus d'un titre, et je soupçonne les concepteurs de Rayman (la version 2D) d'avoir suivi une approche similaire. En particulier, elle permet l'introduction de "grillage à monstres", des blocs invisibles et non-bloquant pour le personnage et les projectiles, mais qui sont assimilés à un mur par certaines plates-formes mobiles et par certains monstres. Comme je l'avais déjà précisé lors de l'analyse des maps de Commander Keen 5, je trouve que c'est une technique élégante pour construire les niveaux. Si je compare à "Inside the Machine" (l'autre jeu dont j'ai étudié les sources pendant mes longues soirées d'hiver en Suisse), l'alternative consiste à programmer les monstres de sorte qu'ils ne s'éloignent jamais de plus de n pixels de leur position initiale, en maintenant une variable supplémentaire "distance" qui les force à faire demi-tour. C'est exactement le genre de "pré-câblage de code" que je cherche à éviter. Décider jusqu'où un monstre va, c'est une question de level design, pas de programmation du comportement des monstres.

The final argument is that some testpoints are typically more important than others, and there is a strong relationship between which testpoint is triggered and which movements you can do. A problem i have with the current implementation of collisions in Bilou is that as soon as one of the testpoint checks fails, the whole move is cancelled. If you fall along a wall, you don't expect your character to "stick" on the wall because you keep pressing the D-pad in the wall's direction. Yet, that's exactly what Bilou does right now.
Instead, we'd like something like

if cando(dx,dy) then (x,y) := (x+dx,y+dy)
elsif cando(0,dy) then (x,y) := (x,y+dy)
else { 
  (x,y) := (x,align_on_tile(y+dy)); 
  trigger_testfail_event 
}
where cando(deltax, deltay) checks the whole area covered by the character at a new temptative location. But still, you don't want such behaviour for all your monsters, and it's certainly something that is specific to jumping. You wouldn't see this ever in a Zelda game : instead you'd have the character "walk around" a block if he's sufficiently near to the edge of that block. So this logic is really controller-related rather than being something that belongs to the game engine itself.

So, do we still need any testpoint ? after all, Xargon's cando() used in controller-specific code seems to be fine. Actually, there's something that cando() cannot catch: mixed situations. The controller will be able to tell the game engine that it's no longer possible to fall, but it can't tell whether we are now landing, diving, or bouncing against a corner. This is where we *really* need test-points, and you'll notice that testpoints are only used for state transitions.

I still have to figure out the best way to convert my codebase to this new approach -- the fact that i'm busy working on the real-world house not really helping -- but i think it might be what i've been looking for since the start of the project.


Enfin, certains testpoints sont clairement plus important que d'autres, et le déplacement indiqué par le contrôleur doit être ajusté en fonction de la situation. J'ai le problème dans le saut de Bilou, actuellement: quelque soit le testpoint qui détecte une collision, le mouvement complet est annulé. Résultat, si Bilou rentre dans un mur lors d'un saut, il va rester "collé" au mur jusqu'à ce que je relâche la touche de direction. Celà n'arriverait pas si je pouvais donner une priorité, ou une description plus complète du rôle des différents testpoints (p.ex. puisque c'est un test-point "mur", il n'annulerait que le déplacement horizontal, etc.)
Mais en fait, ce genre de logique est commune à tous les déplacements guidés par la gravité dans un jeu de plate-forme. Ce n'est pas quelque-chose de spécifique au comportement de Bilou, et celà pourrait sans difficultés être introduit dans le contrôleur du sprite. En tout cas, ce n'est clairement pas à introduire dans la classe GameObject elle-même, puisque si on veut faire un r-type, un boulder-dash ou un zelda, on en aura pas besoin.

Mais alors, à quoi servent encore nos test-points ? eh bien, à décider de quel sera le prochain état lorsque le contrôleur signale qu'il n'est pas possible de continuer. Ca veut dire aussi que le contrôleur devra évidemment ajuster la position du sprite de manière à respecter les "cando()" mais pour que les testpoints puissent détecter quelque-chose quand-même :P
  • [done] extract persistent state (found in map and accessible by other classes)
  • [done] iGobPubstate::cando(x,y,flags)
  • [done] manipulate tile_flags array (that translate tile type into tile flags) from the script
  • [done] controllers report "fail" when no "cando()" can be applied
  • [done] who updates coordinates ?
  • [done] update GameObject::play() and trymove()

2024 #choice reality check: cando is still there. it has allowed slopes, jump-throughs and more. And I finally have proof that it also works with levels featuring water. Pfew!

Wednesday, February 25, 2009

Revamping the green zone

moui ... voilà donc un aperçu de cette fameuse "nouvelle map" que je bricole pour l'instant histoire de tester mes nouveaux graphismes de forêt (encore loin d'être parfaits, hein), avec, marqué en rouge, les endroits où il me manque des blocs de transition pour les coins, etc.

Notez aussi qu'il va falloir que j'aille un peu corriger mon éditeur de niveau qui m'a laissé éditer une cave profonde alors que je sortais en réalité des limites de la map, d'où ces étranges blocs flottants dans l'arbre de droite.

Il me manque des branches, un décor de feuillage "valable" par-dessus lequel je pourrais venir rajouter mes plates-formes feuillues, etc.

A quick sample of the current tileset for the green zone, which is used for testing new collision/behaviours atm. i'm still missing many transition tiles (hunt for red circles) and

TODO:

  • [leds-done] ignore extra sheets in the level editor (rather than just showing empty sheets)
  • [leds-done] a 'swap layer' tool that moves existing tiles to the other (bg/fg) layer
  • [seds-done] RGB shown as 00..FF rather than 00..31
  • [seds-done] S and V shown as 0..100 and not 0..255
  • [seds-done] capture all the colors used on a page and clone them (to allow palette manipulations), updating tiles of that page to the new colors.
  • [leds-wish] copy/paste/clear whole areas
  • [leds-done] don't let me edit out of the valid map area

Monday, February 23, 2009

You can't be successful at every experiment...



Something funny occured while i was working on a new map and testing my new tileset for the green zone, last week ... all of sudden, everything got mixed up in the game engine. I got Bilou's head instead of tree parts, Bilou turned into a funny jumping bush/rock and WoodWorms transmogrified into rolling bilous...

Alors que je testais ma nouvelle map et les nouveaux pixels pour la GreenZone, tout s'est retrouvé mélangé dans le moteur de jeu. Au lieu de feuilles, les arbres avaient des têtes de Bilou au bout de leur branches et Bilou était changé en buisson marcheur... J'ai flashé alors sur le petit dessin où j'expliquais, il y a quelque jours, comment Bouli avait bricolé le transmat de secours de l'AstroCruiser pour qu'il puisse ramener Bilou en lieu sûr grâce au fruits que Bilou récoltait (bio-fuel) pour proposer cette interprétation très "philadelphia experimental / la mouche" du bug.

Since this all occured just a few days after i posted a drawing explaining how Bouli modified the AstroCruiser's emergency teletransmatter to ensure Bilou avoid dying when encountering hazards, i came up with this little "the fly / philadelphia experimental" gag where the bug in the game engine was actually a wrong setting of the transmatter during an early experiment ...

Thursday, February 12, 2009

Script powaa!

Bon. Ouvrez un p'tit terminal (tcsh), on va s'amuser ...

display fairy.jpg
setenv FAIRY `eesh -ewait window_list | grep Magick | cut -f 1 -d :`
randomize `find /pingu/photos/ | grep -v thumb` |\
fe - "display -window $FAIRY '%' & sleep 8"
C'est ma manière à moi de me faire un petit diaporama de mes photos sur mon laptop, mode "discret: je travaille mais j'ai besoin de voir un peu mes proches".

J'vous explique ? Bon, tout d'abord, vous devez penser à tous ces programmes comme des "filtres" qui reçoivent des données par un côté (l'entrée standard) et qui en produisent de l'autre côté (la sortie standard). Un élément de base pour interconnecter les programmes est le tube ("unix pipe") représenté par la barre verticale. program1 | program2 attache les deux programmes de sorte que la sortie de program1 est utilisé comme entrée pour program2... Visualisez une usine avec des robots qui bricolent des pièces qui défilent sur un tapis roulant et vous n'êtes pas loin.

Comme certains programmes ne sont pas prévus pour recevoir leurs données sur l'entrée standard mais plutôt comme des arguments sur la ligne de commande, j'utilise aussi les guillemets arrière qui remplace dans une commande une expression par le résultat de son évaluation. Si add et mul étaient des programmes pour additioner et multiplier leurs arguments, on pourrait faire des expressions un peu plus compliquées à coup de add 5 `mul 2 3` qui serait transformé en add 5 6 avant d'appeler le programme add.

I love how scripting expands the possibilities of programming. Maybe I could have experienced something similar with Visual Basic, but that tool has never happened to be available on my Windows systems afaik. The code you see above is a script I use to periodically change one part of my screen's background as if it was a diaporama.

display FILE will just create the window and show one file. then the line with eesh will capture the identifier of that window into some variable and calling display again with -window $FAIRY will make it paint on the existing window instead of creating a new one.

That's already pretty neat, but I can push it further, like scanning through my pictures repository with find, filtering out the thumbnails with grep and randomize the output with a Perl script of mine that isn't even aware it is processing picture file names.

This is possible thanks to the unix pipe | and shell sub-expressions `sub expr` that gets a program called and its output injected as parameter for another program.

Bref, les programmes utilisés ici:
  • display, le programme d'affichage du projet ImageMagick hyper-standard. Par défaut il ouvre une nouvelle fenêtre pour la nouvelle photo, mais avec -window , il modifie l'image de fond d'une fenêtre existante. En l'occurence, cela me changera l'image affichée.
  • eesh, le kit du bricoleur pour enlightenment, utilisé ici pour récupérer la liste des fenêtres. Si vous n'utilisez pas enlightenment, le package wmctrl pourrait faire l'affaire ...
  • grep, le filtre passe partout, en standard dans toutes les distributions Unix, utilisé aussi bien pour retrouver la fenêtre dont le titre contient "Magick" dans la deuxième commande que pour retirer toutes les miniatures dans la deuxième commande
  • find, également un outil standard, liste tous les fichiers à partir d'un répertoire donné
  • cut : pour extraire un champ d'une ligne du type "fichier CSV".
  • setenv <var> <val>: pour donner un nom au résultat d'une exécution (en l'occurence, enregistrer le n° de la fenêtre d'affichage dans la variable $FAIRY)
  • randomize <args> : un p'tit script perl à moi qui renvoie ses arguments mélangés, ligne par ligne.
  • fe - "commande" : un autre petit programme à moi ("foreach") qui applique une commande à une liste d'arguments. Les puristes auraient utilisé xargs ou find -exec.
  • sleep <secondes> : pour marquer une pause entre 2 images, bien-sûr
Chouettos, non ? Allez, les amateurs de VBA. Vous mettez combien de temps pour faire ça ?

Monday, February 09, 2009

Scripting Sunday

Didn't quite got as far as i hoped in my "coding sunday", so it has rather be a "scripting - and - guru - meditation" sunday instead. Most has been done through state machine scripts or within Sprite/Level editor on the DS ... but some code will have to change. I cannot keep Bilou walking through walls or in the sky, can I ?

C'était un dimanche bien rempli donc, même si je n'ai pas vraiment coder autant que je l'avais prévu. Entre le bricolage de la machine d'état qui gère Bilou, les nouvelles animations et la construction d'un premier "niveau démo" avec les tiles que j'ai dessiné pendant l'année 2008. Pourtant, il faudra que j'y passe. Il y a quelque-chose de fondamentalement foireux dans le couplage "animation/déplacement" qui permet à Bilou de marcher à travers les murs ou dans le ciel ^^"

  • got the GameScript understand multi-set spritesheets (with one set for tiles and one for monsters all in the same file)
  • got Bilou walking animation done
  • bilou walks up/right, jumps and fall
  • sketched a little level for those new tiles i've been working on in 2008 ^_^
  • figured out that i'm still missing *many* tiles and a lot other tiles are unusable ^^"
  • fixed so weird memory things in libntxm, but i still have data corruption happening. Maybe a checksum of some internal arrays will help ... or replacing arrays with std::vectors somewhere ...
  • had fun with sprites on "mid" layer. Bilou can now hide within tree, so can woodworms :P
  • STill to do:
    • [done] testpoints should be checked at every frame, not just when the animation loops
    • [done] moving Bilou through the animation isn't the right way to go. Maybe "delay x" in the animation sequence to have the next frame triggered only when we move to the next pixel would be better.
    • [done] check my own code for things that might corrupt libntxm's internal state. (identified some memory leaks, but no buffer overflows or double-frees)
    • make sure we can see Bilou's feet on grass
    • [doc] let animated blocks work with "extra tilesheets"rather than copying sheets "as needed".
    • [done, leds] ignore extra sheets in the level editor (rather than just showing empty sheets)

    Saturday, February 07, 2009

    Xargon, Jill et Nikita

    Okay, pour ceux qui en nourrirait encore vaguement l'espoir, je n'ai pas l'intention de porter Jill ou Xargon sur DS. C'étaient de bons jeux dans leur temps, mais même le fait que les sources soient disponibles (pour Xargon en tout cas) ne me tente pas.

    Je m'explique. Un des éléments qui m'intéressait dans l'étude du code de Xargon, c'est que tout comme notre Commander Keen, Jill et Malvineous (eh oui: Xargon, c'est le vilain pas beau et Malvineous le héros tout en muscles) savent grimper aux lianes (chaines et autres). Un des aspects qui me coince un peu dans Bilou. Or donc, grace au flag f_notvine, ces héros grimpotent grace aux éléments suivants:

    • le test "y a-t'il une liane" n'est effectué que sur des frontières de tiles (comprenez, quand x est un multiple de 16)
    • une fois accroché à une liane, il n'y a plus de déplacement horizontal

    Maybe my last post made you believe I was about to port Xargon or Jill of the Jungle to the Nintendo DS. I'm not. They were solid games back in the days, but even with sources available, I'm not tempted. What's interesting me while studying Epic source code is that their heroes (much like Commander Keen) can CLIMB. Vines, chains, pole. Name it, you have it. That's one thing I don't know how to deal with in Bilou so far, but thanks to the F_NOTVINE flag. Things seem to work fine. The 'is there a vine' test is performed only at tile edges (x is a multiple of 16) and no horizontal motion is allowed on a vine. Fine.

    But there's one thing missing: where's the code that aligns character to a vine if they aren't yet ? having to pixel-perfectly aligning before climbing is usually not something you leave to your players. And I don't recall it being so hard to hop from vine to vine in Jill of the Jungle. Almost easier than hopping from block to block, actually.

    Apparemment tout ce qu'il faut sauf qu'il n'y avait apparemment rien dans le code qui permette de forcer le perso à s'ajuster à l'emplacement de la liane si jamais il n'était pas pile en-dessous ... louche, ça. Vous vous voyez jouer à un jeu où il faut être positionner au pixel près pour monter à l'échelle, vous ?

    Pourtant je me souviens que ce n'était pas si difficile de sauter de liane en liane dans Jill (j'ai peu joué à Xargon, en fait). Bien plus facile que de sauter de bloc en bloc, d'ailleurs.

    Bin voui. pas étonnant. Figurez-vous que Jill ne se déplace jamais que _de 8 pixels à la fois_ idem pour le scrolling. Oui, vous avez bien lu : 8 pixels. La taille d'un caractère à l'écran. Jill est soit sur le bloc gris, à moitié sur le bloc gris ou à côté du bloc gris. Point barre. Le jeu est un peu plus "souple" pour les déplacements verticaux (2 pixels) mais n'empèche. La version shareware avait beau se gausser de Commander Keen et de Super Mario, le slogan "The Brothers are History", c'est à Giana qu'il revient, certainement pas à Jill. Et toutes ses voix enregistrées et ses cuisses bien rondes n'y changeront rien!

    So here's the catch: Jill and Xargon only move by 8 pixels. Same for the scrolling. Yes, 8. A full-sized letter on CGA screen. Either Jill is perfectly centered on a 16x16 grey block, or she's exactly on the edge of that block. Or she's next to it. That's it. Vertical motion is a bit smoother (2 pixels granularity), but barely. There may be a similar 'minimum walking distance' in commander Keen (4 pixels), but motion happens pixel per pixels, much more smoothly. And while Jill's jerky motion could be excused by the run animation on the ground, nothing justifies it while jumping (and it hurts the gameplay a lot).

    Dans Commander Keen, cette "distance de déplacement minimale" est de 4 pixels (en tout cas, si je donne le plus court déplacement possible, c'est ce qu'il se passe), mais malgré tout Keen est déplacé pixel par pixel. Bien plus fluide. Et si ce genre de "déplacement brusque" peut se justifier pour l'animation de la course, en revanche, il est complètement ridicule (et pénible au niveau du gameplay) lors d'un saut. Tiens, à creuser par contre ... Et si j'utilisais le freinage du perso pour forcer ce genre de déplacement minimum ?

    Bref, le code était instructif, je vais me replonger dans la programmation de mon p'tit Bilou (qui a appris à marcher ce matin ;) et en attendant, si vous êtes en manque d'exploration de mondes curieux à grand renfort de transformations magiques (c'était un des points-forts de Jill, je l'admet), je vous recommande chaudement Nikita, la femme-loup du jeu Inner Worlds. (merci à CJ pour l'URL et sa compil' "nostalgy power" :)

    Voilà. Ma sauce bloubloute alors je vais vous laisser. A+.

    Thursday, February 05, 2009

    Xargon : may the source be with you ...

    Vous ne connaissez pas Xargon ? pensez à Jill of the Jungle avec un chromosome Y et vous ne serez pas loin... Vous ne connaissez pas Jill of the Jungle non plus ? Ah. Bin probablement que votre PC n'avait pas encore de carte SoundBlaster ou d'écran VGA en 1992. C'est vrai que ça coûtait un peu cher, à l'époque.

    Quoi qu'il en soit, si je vous en parle, ce n'est pas parce que les 3 épisodes de Xargon sont disponibles sur classicdosgames.com. Non, c'est parce que le code source de Allen Pilgrim est également disponible. C'est du code C, mode réel pour le DOS, mais suffisamment propre pour que tous les aspects "hardware" soient extrait de la logique du jeu -- et croyez moi, sur PC, c'est un exploit majeur.

    Ce n'est pas la bibliothèque d'abstraction du hardware qui m'intéresse, bien sûr. Même si c'était impressionnant à l'époque, le scrolling des jeux de plate-forme Epic ne pouvait concurrencer celui du moteur de John Carmack (commander Keen & autres), le player de fichiers CMF (adlib/midi) était bien connu, mais je n'ai jamais vu d'éditeur correspondant, et si l'on se laissait impressionner par un "yeeaaah" en ramassant un gros bonus, le mixage des effets sonores était en réalité peu convaincant (voire absent).

    I'm currently studying the game logic of Xargon from Allen Pilgrim's sources. I hope that giving a look on someone else job will help me to overcome that "analysis paralysis" in my own game engine. I know i tend to overcomplicate things ... The management of objects-to-world collision has already shown enlightening... more to come. And, by the way, if anyone of you is interested into porting Xargon to the DS (or whatever other system), you may want to give a look to information gathered on the game modding wiki at shikadi.net in addition to the source code. Personnally, it's not in my to-do list :P

    Non, ce qui m'intéresse c'est la logique du jeu. Et quelque-part, cette logique me crie le maître-mot de Mollusk: "ne vous posez pas de question: codez". C'est vrai quoi. Je me prends la tête avec mes test-points alors qu'en fait, ce n'est qu'une optimisation bancale que je traîne depuis l'age du BASIC, renforcée par l'étude d'un jeu NES. La gestion des collisions perso-monde dans Xargon est bien plus simplement basée sur les possibilités de l'ensemble des tiles recouverts et l'affectation de propriétés sur chacune de ces tiles.

    int cando (int n, int newx, int newy, int ourflags) {
     int x,y,temp;
     int flagor, result;
     int startx, endx, starty, splity, endy;
    
     startx=newx/16;
     starty=newy/16;
     endx=(newx+objs[n].xl+15)/16;
     endy=(newy+objs[n].yl+15)/16;
     splity=(objs[n].y+kindyl[objs[n].objkind]+15)/16;
    
     flagor=f_notstair;
     result=0xffff;
     for (y=starty; y<endy; y++) {
           if (y>=splity) flagor=0;
           for (x=startx; x<endx; x++) {
             temp=(info[board(x,y)].flags|flagor)&ourflags;
             result&=temp;
           };
     };return (result);
    };


    Comme disait Colomb en quittant le Portugal "Il suffisait d'y penser": le tout est de concevoir les propriétés des tiles de manières à ce qu'elles "s'additionnent" bien. Un personnage ne peut se déplacer vers un nouvel endroit que si tous les tiles possèdent les bonnes propriétés ("pas un bloc", ce que Allen appelle f_passthru. Celà demande parfois un peu de jonglage mental. f_water est évident, f_climbable aussi. f_not_stairs un peu moins...


    int trymove (int n, int newx, int newy) {
     int ourflags;
     ourflags=f_playerthru;
    
     if (newy>objs[n].y) ourflags|=f_notstair;
     if (cando (n,newx,newy,ourflags)==ourflags) {
        moveobj (n,newx,newy);
        return (1); // successfully made it to new location.
     } 
     else if (cando (n,objs[n].x,newy,ourflags)==ourflags) {
        moveobj (n,objs[n].x,newy);
        return (2); // could only move vertically
     }
     else if (cando (n,newx,objs[n].y,ourflags)==ourflags) {
        moveobj (n,newx,objs[n].y);
        return (4); // could only move horizontally
     };
     return (0);    // couldn't move at all.
    };


    J'aime bien aussi la manière dont il a réussi à capturer les comportements de déplacement simples Il faudra que je tente d'en faire autant. Bion. Je vous en dirai sans doute plus. Malgré tout, la routine de gestion du personnage principal fait quand-même 7 pages, et je n'ai pas encore tout lu.