Cave Story on the DS ...

Huzzaah!

Cave Story ... un mélange étonnant entre le shoot-m-up, le RPG et le jeu de plateforme, réalisé en solo par un japonais sous le pseudo "Pixel". Un phénomène sur le Web, avec les deux versions Mac et Windows, qui est annoncé sur PSP (mais sera-t-il fidèle à l'original?) et boudé par Nintendo (bande d'andouilles). Cave Story, ou "doukutsu", comme préfère l'appeler Cyril, c'est aussi un sujet de conversation récurrent à la pause-café, même si mes collègues de la "Totem Team" ont un peu moins accroché. Bref, j'étais déjà tout fou quand ravenworks avait annoncé une version démo du cimetière "avec les champignons qui se promènent", je crois bien que j'ai eu droit à une belle montée d'adrénaline en voyant le lien "cave story gallery" sur dsfanboy.com

Believe it or not, I discovered Cave Story on the Nintendo DS. Or at least because someone on a homebrew-related blog re-posted the link to Ravenworks' journal where she details her effort to port the game to Nintendo DS. We somehow turned doukutsu-frenzy at the office, it it turned even better when announcement was made that we could get moving monsters in the updated version.

Quite interrestingly, Raven decided to switch to NDS's 3D hardware to get that done. A pretty surprising move. I'd be curious to give that code a look.

En effet, ravenworks nous a sorti une nouvelle démo, qui reprend quelques niveaux dans lesquels vous pouvez vous promener pépère ... oui, parce que s'il a effectivement été très rapide pour intégrer le déplacement de tous les monstres (désolé, mais un gros tas bleu qui vous saute dessus, j'appelle pas ça un NPC, mais un monstre), il manque encore les tirs et l'énergie. Vous vous promenez donc désarmé mais invincible dans un environnement qui aussinon ne manquerait pas de dangers dans tous les coins.

the whole damn thing runs on the 3D hardware now.

Nous confie RavenWorks... wow. Bin je serais super-intéressé de jeter un coup d'oeil au code ... Et celà explique sans doute pourquoi je n'ai vu que le menu de sélection des niveaux et le décor de fond dans desmume :P Je m'étais dit "ce soir, je saute dessus" ... bin j'ai pas attendu jusque là. J'ai ressorti mon lecteur de cartes SD tout pourri, bricolé un peu avec un bout de carton pour que les contacts se fassent bien et transféré le-dit fichier .nds ... Intérêt limité (un shoot'm'up en "god mode", pourquoi pas, mais si on ne peut pas tirer ... bon "dog mode" ?), mais indispensable pour tous les fans. Encore un peu de patience ... je sens que je ne regretterais pas de m'être arrêté à Monster X sur le portable de mon oncle ^_^ 

 (edit: originally hosted on http://cavestory.ravenworks.ca/)

récup skyblog.

Tiens. Ils se sont décidés à ajouter les "pages-par-post" sur mon vieux skyblog. L'occasion de vous donner les pointeurs vers mes premiers posts sur la DS ... Assez amusant de relire des billets un peu "roadmap" après un an et de se rendre compte que les objectifs ont déjà bien évolué.
edit 2009: avec le système de "scheduling des posts" de bloggers, je peux maintenant faire apparaître tous ces articles à leur véritable date dans ce blog.

Sprite Editor on the DS: the SEDS approach.

Let's advertised it a bit: i've started a sourceforge project for the game development tools for the DS.
To many aspects, SEDS philosophy is quite different from the other sprite editors i've shown you in my previous post.

First of all, it is not using bitmap rendering. I oriented most of the rendering techniques towards tiles-oriented rendering that is so specific to console hardware. This is mostly possible thanks to the huge amount of individual tiles available on the DS.

As an example, the grid where you draw your pixels is actually made of tiles, that is, each individual pixel you paint is a 8x8 character that is programmed to be a 8x8 square of a single color. Same goes for the grid lines and the palette on the left. I also integrated various test of DS features in the editor, such as the ability of modifying the grid lines' opacitiy (through up and down arrow), thanks to the fact that widgets are rendered on a separate layer than background and your colored artwork.

Another great feature it enables is fast rendering at any zoom level. So far, the grid is rendered 1:1, but i have already tested a 32x32 grid with smaller pixels (which wasn't working as expected probably due to DMA problems). I could even potentially use 24x24 grid (scaling 8x8 tiles to 6x6 to keep the same area occupied) by just reprogramming two registers. Welcome to 2D hardware acceleration goodness ^_^.

J'ai enfin uploadé mes démos et sources sur mon projet "dsgametools" sur sourceforge. Entre-autres, SEDS, l'éditeur de sprites pas comme les autres, qui s'appuie principalement sur le hardware 2D de la console pour accélérer le rendu de la grille, etc. Le niveau de transparence de la grille, le zoom plus ou moins fort sur la zone de travail, autant de petits tests des possibilités de la bête... Ca demande un peu plus de boulot et de debugging que d'utiliser une bibliothèque de widgets sur un framebuffer, mais le projet gagne en intérêt ^_^

Bon, les sources ne sont pas encore génialement belles (je débute en C++, quoi qu'on puisse en penser), mais c'est assez fun d'utiliser pour ce genre de projet les techniques de développement OO, l'UML et tout ...

/* reprogramming the background layer 3 (colored artwork)
* so that it is 50% zoomed and still appear at (xbase,ybase)
*/
SUB_BG3_CX = (-xbase*2) <<8;
SUB_BG3_CY = (-ybase*2) <<8;
SUB_BG3_XDX = 2 << 8;
SUB_BG3_XDY = 0; /** XDY and YDX useless in that case. **/
SUB_BG3_YDX = 0; /** see TONC tutorial if they puzzle you **/
SUB_BG3_YDY = 2 << 8;

Feel free to download the demo or browse CVS sources.

Well, I'm not very proud of the sources. I'm still learning C++ and certainly haven't a good style atm. Plus, most of the code depends of libraries i've hacked for proper interoperations (such as the libnds that integrates anti-stylush-jumping code from PadrinatoR)
In other words, expect hard time if you try to compile the projects from its sources right now. I'll publish the modified libraries in the project too ... when i'll find time for this :P

And yes, the development of the editor is somehow freezing these last days, because i have met a point where data storage and organisation need to be refactored. And my thesis do not let me allocate sufficiently large time slices to do things like that ... so i'm just writing small perl scripts for converting old .SPR files to the new (anticipated) format -- which gets highly IFF-inspired if you ask :P

Years of Sprite Editor Coding

Oh boy! it's now years i'm busy working on sprite editors. SEDS is certainly not the first one. I probably have half a dozen of sprite editors for DOS. The first ones (the 'regular' sprite editor from JMWS was only controlled through the keyboard)

The first half-usable was "super sprite editor", which --thanks to a book i found in Mr. Beer's library-- could handle the mouse. Only 8 colors were allowed, which wasn't much a problem at that time. Palette editing required the user to encode RGB values. A few built-in features like swap were available, but it was still far from being really usable.

Oh, avec SEDS, je n'en suis pas à mon premier Sprite Editor ... loin de là. Un des premiers à être vraiment utilisable était le "Super Sprite Editor", également mon premier programme à utiliser la souris (grâce à un bouquin trouvé dans la bibliothèque de M. Beer). Seules 8 couleurs étaient disponibles -- ce qui, vu les techniques utilisées par après dans le rendu des sprites -- était loin d'être un problème. La modification de ces couleurs passait par un encodage direct des valeurs RVB.

A côté, la version 1.4 annonçait fièrement (à grand coup d'animation par "palette cycling") "8 blocks in 32 colours, 20x20 pixels". Une petite fonction "copie de bloc" (Shift+C) bien sentie et la possibilité de "retourner" les images (shift+X et shift+Y) étaient ajoutées, mais malgré toutes mes tentatives, je n'ai pas réussi à utiliser plus que les 8 couleurs de base. 'faudra que je replonge dans le code. C'est malgré tout avec cet outil que j'ai fait la plupart des sprites de Bilou's Adventure (version Quickbas, bien sûr).

Super Sprite Editor version 1.4 was proudly announcing "8 blocks in 32 colours 20x20 pixels" in the welcome screeen with funny palette animation. You could basically copy blocks (when prompted "source sprite" and "destination sprite"), but i didn't find out how to use more than 8 colours anyway :P The rest of the interface was basically just the same as Super Sprite Editor. SSEditor2B.bas is its latest incarnation. It has a bit more features and better error handling. I thing that's what's been used to draw Bilou's Adventure sprites.

Its latest incarnation - SSeditor3.bas - is probably the best you can expect from a BASIC program. It features backward compatibilty with the previous versions, edition in 128 colors, easy-click and complete color edition solution. It also has better "compression rate". This is the tool i've been using for the school zone in Bilou's Adventure (basic).

Note that it already uses the convention "left=putpixel, right=getpixel" that i'm still using in SEDS nowadays. I find it more convenient than the typical two-colours setup.

Nettement plus ambitieux, SSeditor3.bas est probablement mon meilleur outil en Basic. Avec une fonction d'import des outils plus anciens, une édition intégrée des palettes de couleurs (avec gestion des dégradés, oui ma bonne dame), et jusqu'à 128 couleurs simultanées, on croyait rêver. Tout ce qu'il lui manquait c'était la possibilité de lire les fichiers disponibles (l'utilisateur est obligé de se souvenir des noms où il n'aura rien du tout).
A noter que c'est mon premier éditeur qui utilise la convention "clic gauche = dessiner, clic droit = lire la couleur", qui est toujours en vigueur dans SEDS, et que je trouve bien plus efficace que le système "FG/BG color" que l'on retrouve p.ex dans The Gimp et dans le sprite editor du Game-Maker.

Another heavily used tool: "Decor Editor Special Bilou" was pain for the fingertips. You navigate on the grid with the arrow keys and fill one pixel xith "enter". Changing to another color required you to hit "C", navigate to the new color and then press "enter" again.

Barely more intuitive than encoding your colors as DATA statements in a dedicated "rendering program".

Enfin, terminons par un des tout premiers "sprite.bas", encore sous le label "JMWS", qui était entièrement contrôlé au clavier. Tout le dessin devait se faire en déplaçant le curseur à l'aide des flèches, et il fallait entrer "C" pour pouvoir avancer dans la palette jusqu'à la couleur suivante. Les dernières versions permettaient aussi de descendre ou remonter d'une ligne dans la palette et se souvenait de la couleur en cours.
Croyez-le ou non, mais toute la forêt de Bilou sous Dos avait été encodée avec cet programme. Les opérations du genre "copier/coller" ou "symétrie verticale" étaient obtenue par des programmes BASIC indépendants :P

J'ai aussi fini par retrouver "blobedit.asm", une tentative de sprite editor complètement en assembleur, mais pour lequel je n'ai apparament plus aucun des fichiers "maya.blb" qui en sortait.

Oh, there also was "blobedit", pure a86 assembler ... 16x16x256 editor which had been used for "nono in maya zone" ... but it looks like i don't have any .blb file anymore on my hdd...

And of course, now, this 'family' is completed by SEDS, the Sprite Editor on DS, that result of a completely new approach, trying to get the best user experience from this unusual hardware : one hand on the D-PAD, the other holding the stylus. No menu or distracting boxes. A handy development tool that you can take along anywhere...
Et bien sûr, la famille compte maintenant aussi SEDS, mon éditeur sur la console DS, d'une conception entièrement nouvelle pour améliorer l'ergonomie du pixel art... une main sur la croix directionelle, un doigt sur le bouton L, le stylet dans l'autre main ... et vous êtes parti! Dans le bus, le métro, au boulot ou au dodo, rien ni personne ne vous empèchera plus jamais de spriter ... sauf peut-être le prof de Latin ^_^

Smoove DS ... Another Sprite Editor in Development

A new blog has just pop'd up in the Drunken Coder community. A blog of special interest for me as Smoove is doing his own pixel editor too ... I hope he won't mind my intensive comment on his posts, and i sincerely hope each other's shared experience will benefit to both our projects ^_^
Un nouveau blog vient de faire son apparition dans la communauté Drunker Coder. Un blog particulièrement intéressant pour moi, puisque Smoove s'attaque lui aussi à un Sprite Editor. Comme on dit, "y'a plus dans 2 têtes que dans une". J'espère qu'on pourra s'aider l'un-l'autre.

Par exemple, il nous a mis une image de "palette façon oldschool". Si vous avez jamais utilisé un éditeur de pixel (p.ex. le grandissime Deluxe Paint), vous savez à quel point travailler avec une palette mal organisée peut devenir un calvaire. L'ennui, c'est que c'est extrèmement fréquent dès que l'image est passé par n'importe quel convertisseur.

Just an example, he posted an example of "oldschool color sorting". If you've ever been involved in pixel edition, you know that dull task of creating a "workable" palette out of the mess some .gif or any other kind of "automatic conversion from RGB to indexed colors" could create.
If not, just look on the side here. Blues are scattered with other colors, etc. A regular "sort" function will have hard time identifying rasters in the 3-D color space.
L'ennui, c'est que pour un PC, ça va être particulièrement délicat de retrouver les dégradés dans l'espace 3D "RVB". Et si nos yeux font très facilement la différence entre de l'orange et du bleu, par contre pour ce qui est de "trier" des nuances de bleu, c'est souvent plus délicat.

Alors pourquoi ne pas laisser chacun faire ce qu'il fait le mieux? donnons à l'utilisateur la possibilité d'indiquer au programme quelles sont les couleurs à ajouter dans un raster donné, et la DS se chargera de les trier au fur et à mesure. Et éventuellement, on pourrait indiquer les couleurs les plus proches de la couleur choisie.

Your eyes are good at discriminating blues from oranges, but not at sorting blues... so i thought we could have something like a "color to raster" picking tool that would allow the user to collect colors he want to have included in a specific raster, and then let the DS do the sorting. You could then remove/split if some colors seems not to belong to the produced raster. We could also have the DS give hints to the user at which colors it "think" to be "close" to the one you picked.

edit: the smooveDS project is now defunct. It never went much further than basic attempts, partly due to the difficulty to save files on a FAT filesystem in these early days. 'MW', his author has now moved to iPhone programming where Smoove is now known as "hiscore pixeleditor"

Indexing my Thesis

Okay. For those who have missed it so far, i'm writing down my PhD thesis ... and it's built with Latex.

Updating and completing a 1 year-old Latex document with new parts coming from conference paper, autonomic thoughts, etc. is some challenge i haven't met so far, so i'm upgrading my toolset as well.

Au cas où vous auriez loupé un épisode, je suis en train de rédiger ma thèse. Et je fais ça en Latex. Un document commencé il y a plus d'un an que je dois compléter avec des articles de conférence, etc. Bref, un des plus gros challenges auxquels j'ai eu à faire face jusqu'ici.

Le défi d'aujoud'hui ? Garder le fil de ce dont j'ai parlé, et où j'en ai parlé tandis que je fusionne et réorganise tous les bazars. En gros, construire et utiliser un index pour mon document.

Today's challenge: how to keep track of what i'm talking about in the different part and see whether merging/reorganizing things would help. In a word, building and working with an index of terms in my manuscript.

http://www.dtr.isy.liu.se/latexindex.html is a first good reference. Just adding \usepackage{makeidx}, and \makeindex \printindex to the document structure, and voilà. (oh, well, almost. I also have to make sure i properly call the makeindex command between latex calls :P)

Un petit peu de googling, et j'ai trouvé comment me servir de \usepackage{makeidx} de \makeindex et \printindex (oh, ne pas oublier d'appeler makeindex sur la ligne de commande, au passage). Reste à remplacer ici et là les \emph{protected tags} par quelque-chose comme \index{tags!protected}\emph{protected tags} ... dans près de 70,000 mots répartis sur 37 fichiers source ... de quoi devenir dingue si on ne fait pas un peu attention.

Now, i'm starting to do mass-replacement of "\emph{protected tags}" with "\index{tags!protected}\emph{protected tags}" ... in those +70000 words split in 37 source files ... Time for something to automate grep/open-file/query-replace, no?

Well, another google search pointed me at Sam teachs yourself Xemacs in 24 hours where they had a very nice explanation on regexp-query-replace and how to use the etags tool to operate on many file at a time. Roughly, all i have to do is invoking "wasp/phd> etags *.tex" to produce a condensed TAGS file for the current directory and then invoke M-x tags-query-replace to replace all the instances of the text with index-augmented text (well, i'm prompted whether i want the replacement or not ;)


Heureusement, il y a Sam, pour m'aider à comprendre le fonctionnement de etags de manière à invoquer M-x regexp-query-replace et remplacer tous ces mots l'un après l'autre en un clin d'oeil.
Allez, les windoziens. Qui dit mieux ?

edit: plein d'autres trucs latex en FAQ sur cette page

Beware of DmaCopy()

Hop. Entre deux transparents pour ACNM'07 et la navette pour IM'07, j'ai profité du portable emprunté à mon oncle pour faire un peu de HomeBrew. Il faut dire qu'avec son lecteur de carte SD et ubuntu "feisty", c'est méchamment plus pratique.

J'avais un problème avec le "scrolling" de la zone de travail, que j'utilise abondamment pour faire des tiles qui peuvent s'emboiter, et plus étonnant, celà n'arrivait que sur une 'vraie DS' ... aucun problème dans desmume (pour une fois). A force de chercher des failles hardware sur mon Network Processor pour ma thèse, j'en suis venu à suspecter les fameuses "commandes de copie DMA"...

Between two slides for the ACNM'07 workshop and the shuttle to IEEE IM'07, i'm enjoying my uncle's laptop for homebrew coding. With embedded SD card reader and the "feisty" Ubuntu, it's *way* better than playing with my regular hardware ...
So i took the opportunity to debug something odd occuring when "scrolling" the working grid -- some feature i'm heavily using to make tiles that ... tile. While it worked flawlessly in desmume emulator, it seemed to miss the first click on scroll button on real DS hardware ... As i'm looking for hardware issues on a Network Processor for my PhD thesis, i suddenly suspected something wrong with DMA copies.

Et j'avais raison. Le code du "scroll" proprement dit, c'est quelque-chose comme

for (i=0;i<16;i++) {
char extra=data[i*16]; // save first pixel
for (j=0;j<15;;j++) data[i*16+j]=data[i*16+j+1]; // shift row
data[15+i*16]=extra; // get back first pixel
}

après quoi, j'appelais à nouveau ma méthode "render" du widget "grid", laquelle faisait gentillement:
I first used to shift the working space (data[] array) in place, (see above), and then called the gridWidget::render() method which issued row-per-row DMA copies as below:

for (i=0;i<16;i++)
 dmaCopy(/*from, char*/data+16*i,
         /*to, uint16 */VRAM+ROWSIZE*i,
         /*bytesize*/16);

Ouais. Bin si vous avez du code pareil qui se comporte bizarrement, courrez bien vite remplacer les "dmaCopy" par des "memcpy" bien gentils. Je n'ai pas le fin mot de l'histoire, mais n'oublions pas que tout ce que le processeur ARM lit/modifie passe par un cache, alors que les déplacement DMA, pas. En clair, pour peut que la commande DMA se mette à lire notre ligne de données avant que le cache n'ait été réécrit en mémoire centrale, c'est foutu.

Well, if you have something like that in your code and that the code behaves weirdly, do a rush query-replace of dmaCopy with standard memcpy. I haven't investigated this down to the nitty-gritty details, but we should keep in mind that the ARM processor read/writes goes through a cache while DMA memory transfers typically operate directly on physical DRAM rows... So to make it clearly, a DMA command could very well start moving the bits _before_ the content of the cache has been committed to main memory. And bang, we're doomed.

That's what computer scientists call a race condition. wuuzaa.
En informatique, ça s'appelle "une condition de course". Géant, non?

Edit: stellar date 2009.05.29, Cornarac (the author of TONC, a major reference in GBA programming) has published an impressive and detailed tutorial on caching and dma : http://www.coranac.com/2009/05/28/dma-vs-arm9-fight/