Tuesday, April 09, 2013

Circularity

Spongebop monster design was a way to convert the (imho) funny and interesting spider monsters of prehistorik 2 into Bilou's world. As such, they won't simply move up or down, or track Bilou while sliding (as suggested in the 20-year-old proposal), but also rock and roll, hanging by a thread. Another conversion of dangerous-but-useful NPC rather than an evil ennemy.

Une éponge qui se balance au bout de sa corde ... une idée de monstre sympa et qui ouvrait pas mal de perspectives dans la "School Zone", mais techniquement plus délicate à réaliser qu'un "simple" monstre sauteur ou marcheur, en particulier avec les contraintes techniques de la DS. Depuis l'automne dernier je dois bien avoir gribouillé 3 ou 4 techniques succeptibles de rendre la chose possible sans jamais être allé jusqu'au stade de l'expérimentation. Mais maintenant que je peux attacher un objet à un autre au niveau du script, il est temps de monter un prototype.

Now, it's time to turn this "nice idea" into some real code. Physically speaking, spongebop will act as a pendulum bob, oscillating as the result of gravity and counter-force originating from thread tension. We're taught that when 17 at school. There's just two major drawback to a "straight coursebook implementation":
  • it's full of angles, sin(x) and cos(x), which are pretty heavy for our 66MHz processor
  • It assumes a rigid, fixed-length rod between bob and pivot.


Conservation de l'énergie, mouvement circulaire ... ce ne sont pas les approches qui manquent, mais chacune a aussi ses hypothèses de travail (notamment la présence d'un axe fixe que je ne désire pas). J'étais au départ prêt à utiliser une variante des algorithmes à la bresenham pour les cercles, mais la multiplication n'est en fait pas si coûteuse en terme de temps de calcul que je ne l'aurais cru. Je peux donc exploiter assez librement l'équation x²+y²<=r qui décrit tous les points à l'intérieur d'un disque. Dès que les la distance entre SpongeBop et son point d'attache ne valide plus cette contrainte, c'est qu'il tire trop sur la corde.
     Bilou would pretty much love that sort of predictable and massive pendulum platform, but spongebop's thread is instead fairly elastic and landing with excessive velocity triggers a rodeo session, says the comic concept art.
    In other term, I would like something more flexible, that can constraint Spongebop to stay within a certain circular area, but still allow Lissajous-like patterns when drawn away from its equilibrium path, as I explained this lunch-time to Cyril. So fundamentally, Spongebop's behaviour is defined by two controllers:
    • gravity, that takes care of the "free riding" when x²+y²<r²
    • radius detects situations where x²+y²>r². As soon as that occurs, we use a 'unit' vector that points towards the pivot position and iteratively move spongebop back into the allowed area.

    Ce qui est assez amusant, c'est que si je parviens à faire en sorte que SpongeBop ne puisse allonger exagérément sa corde, j'aurai le mouvement de balancier par simple application du même contrôleur gravity que celui qui sert pour les sauts de Bilou. Je rejoins alors le "scénario BD" qui prévoit un comportement plus cahotique lorsqu'on atterit trop violemment sur le dos d'une éponge. J'utilise donc le vecteur "attache-éponge" pour définir une "direction de rappel" et ajouter un déplacement vers le centre tant que Bop est hors de son cercle de repos.

    Ideally, energy preservation should keep the sponge oscillating as long as the level runs, but there's something that looks very much like friction in the digital world: precision loss. Since we're working with fixed-point arithmetic here, we're losing some speed in rounding coordinates and angles, so that after about 3 cycles, there isn't much movement left. It's compensated by a refreshing impulsion generated everytime Spongebop arrives just below the pivot point, as if it had some muscles that helps it control its movement. That part is handled by some gobscript and the controller merely report "you're at (0,ymax)" through an event.

    it's a sponge bob ^_^

    MUL instruction on ARM9 merely takes 2 cycles. As a result, I ended up dropping my initial idea of using (x+1)²=x²+2x+1 and simply re-compute (x+a)*(x+a) whenever needed.
    I have at most one division per frame (per instance), to define the centripedic 'unit' (1/16th of pixel) vector. Yet, division isn't handled by the CPU, but by some extra software (the support library coming along with devkitpro's flavour of GCC). I think I'll live with it unless it turns out that I'm over my cycles-per-frame budget.


    Le résultat est plutôt satisfaisant. Ce n'est pas un arc de cercle parfait et je dois "relancer" le mouvement régulièrement, les erreurs d'arrondi en virgule fixe ayant tendance à l'amortir trop rapidement. Je m'en sors donc avec une division (software) par éponge et par frame au prix d'une progression itérative pour recentrer Bop lors de ses déviations. C'est plus erratique que le pendule du cours de physique, mais ça colle plutôt bien au personnage. Reste à maîtriser la 3D pour tracer l'élastique et le co-processeur mathématique de la DS pour avoir accès aux divisions et aux racines carrées la prochaine fois.

    Agreed, the trajectory followed by SpongeBop on the animation above is not quite a circular arc, but for some dizzy sponge on an elastic string, I think it does the trick. Now it's time I allow Bilou to "land" on SpongeBop, because solely bopping over is pretty tricky.


    Hmm ... tracing a GL_LINE between the spongebop and its pivot (not yet visible) would be a nice use case to introduce 3D support in the mix ...

    PS: all this was the last idea of a long list of dropped approaches. Maybe I'll discuss alternatives later on.
    PPs: of course, although the ARM processor on the DS has no support for division/square roots, the DS itself has extra hardware for such functions.  Since it says "square root takes 13 cycles", it could be worth to use the sqrt(dx²+dy²)/sqrt(R) ratio to properly compute the pullback force rather than relying on iterations here. (that's still an occurence of premature optimisation, imho)

    9 comments:

    Mojo Jojo said...

    Bon, je suppose que tu as décidé de ne pas utiliser des sin() ou des cos(), mais j'ai trouvé http://devmaster.net/forums/topic/4648-fast-and-accurate-sinecosine/ qui donne une approximation de sin() avec 5 multiplications (et quelques additions).

    PypeBros said...

    Bien vu, mojo jojo. Note qu'ici, je dois travailler en virgule fixe, et que la formule de Nick@devmaster ne donnerait pas forcément aussi bien qu'on le souhaiterait. Note aussi qu'employer y=sin(a); x=cos(a); suppose que l'on puisse convertir l'effet de la gravité en une accélération angulaire, ce qui n'est pas forcément évident. Mais ça reste un bon outil.

    Celà dit, les fonctions sin/cos interviennent aussi dans l'approche indirecte pour calculer la projection de l'effet de la gravité le long de l'arc de déplacement, soit g'=g*sin(a) où a est l'angle (inconnu) entre le fil et la verticale: a=arccos(dy/R)

    Mais il y a une astuce: http://en.wikipedia.org/wiki/Inverse_trigonometric_functions#Relationships_between_trigonometric_functions_and_inverse_trigonometric_functions nous rappelle (apprend?) que sin(arccos(x))=sqrt(1-x*x)

    Donc en fait, là non plus, le calcul du sinus ne s'avère pas nécessaire (par contre, il faudra maîtriser le calcul de la racine carrée par le co-processeur de la DS).

    PypeBros said...

    http://imgur.com/ElYrlao for the record ...

    PypeBros said...

    Et http://en.wikipedia.org/wiki/Pendulum_%28mathematics%29#equation_Eq._2 donne la vitesse angulaire en fonction de l'angle actuel. C'est donc ça qu'il faudrait recalculer à chaque itération pour une implémentation basée sur (x,y)=(cos a,sin a) en ayant a=a+c/(sqrt(cos a - cos a0))

    (c étant dépendant de la longueur de la corde).

    Mojo Jojo said...

    Ah oui, en virgule fixe, misère! Bonne chance!

    Indirectement tu m'as un peu inspiré pour créer (enfin, passer le pas) une petite application pour android il y a quelques temps (j'ai un peu sué, vu que je ne connaissais ni java, ni eclipse, ni android, mais au bout de 3 jours (et 3 nuits et beaucoup de googling)) j'ai eu ma première version (c'est pas un truc compliqué - une application qui calcule le temps d'exposition pour un appareil manuel à partir d'une mesure digitale). En passant, j'ai regardé un peu le codage sur appareil photo canon (il y a un truc qui s'appelle "magic lantern" et un autre "CHDK" - iik! J'ai bien fait du codage pour z80 ou 6502 dans mon jeune âge, mais j'ai l'impression que c'était dans une autre vie :-)

    Enfin, tout ça pour dire que j'aime bien tes billets. :-)

    Par exemple en pensant à tes grands ongles et les écrans capacitifs, j'ai vu un bricolage avec une éponge, un bic et un trombone (pas l'instrument) on peut fabriquer un stylet). Bon, l'environnement avec eclipse permet de faire le développement et debug sur le PC et tourner sur le gsm, ce qui est quand même impressionnant quand on songe à tous les niveaux à travers lequel cela doit passer.

    Merci pour les liens - sin(arccos(x))=sqrt(1-x*x) je le savais, c'est une version perverse de Pythagore.

    PypeBros said...

    "Enfin, tout ça pour dire que j'aime bien tes billets. :-)"
    Merci, ça fait plaisir d'avoir des lecteurs ^_^

    "j'ai regardé un peu le codage sur appareil photo canon"
    Il y a un moment, un collègue m'a effectivement montré CHDK. J'adore le concept, j'aurais juste souhaité qu'il soit possible de faire l'équivalent sur ma liseuse, par exemple.

    "j'ai vu un bricolage avec une éponge, un bic et un trombone (pas l'instrument) on peut fabriquer un stylet)".
    J'ai fais le test avec une variante basé sur de l'emballage anti-statique avec mon cybook, mais rien de concluant. D'abord, la zone de contact doit rester équivalente à la surface d'un doigt pour que la capacité suffisante soit détectée. Bref, j'ai fini par:
    - utiliser surtout la main gauche pour taper sur le clavier virtuel de ma liseuse;
    - passer une photo de mon nouveau GSM (2Mpixel à tout casser) à travers les filtres d'inkscape comme moyen de numériser rapidement un dessin, plutôt que d'essayer d'en faire une "saisie numérique" sur un iPad hors de prix
    - continuer à développer et dessiner sur la DSi avec son stylet de 2mm de large à pointe transparente ^_^

    PypeBros said...

    (technique également discutée sur http://forums.tigsource.com/index.php?topic=32735.0 )

    PypeBros said...

    et pour la petite histoire, l'équation exacte est bien galère.

    PypeBros said...

    devmaster.net a rendu l'antenne, donc <a href="https://web.archive.org/web/20120113061102/http://devmaster.net/forums/topic/4648-fast-and-accurate-sinecosine/>voyez l'archive.org</a> pour l'article