Multiplexage de sprites

[MsK`]

Plop,
À la suggestion de mon futur chef de projet - hahahaha private joke - DJP que j'ai vu à l'ENJMIN aujourd'hui, je poste par ces contrées ma version DS du multiplexeur de sprites de bulletgba. C'est pas un port, je l'ai réécrit avec très haute inspiration, il est à priori mieux, mais je le considère tout pourri quand même :p
Je compte en faire une nouvelle version beaucoup plus rapide (faut dire que c'est pas spécialement lent la hein, pour afficher 1600 sprites ca bouffe aller, 15% du cpu, 20% ptet') qui sera à peine plus gourmande en mémoire.

Alors le multiplexage de sprites d'abord, quoiquouquestce :
Ça consiste à déplacer les sprites dessinés à l'écran pendant le rendu de l'écran de manière à les faire dessiner plusieurs fois et ainsi afficher plus de 128 sprites.

La difficulté vient du fait que les sprites doivent être ordonnés de haut en bas pour pouvoir modifier l'affichage dans l'ordre du rendu (si vous aviez pas encore tilté, vous pouvez retourner jouer aux legos). Abandonnez immédiatement l'idée de faire un tableau de SpriteEntry et de passer un coup de qsort() dessus, j'ai testé pour le fun, c'est ouf ce que ca rame, j'aurais pas cru à ce point :D

Je suis donc tombé sur une doc' très intéressante, celle du multiplexeur de sprites de bulletgba : http://gba.pqrs.org/tips/sprite-multiplexer.html
C'est tout en japonais...
Heureusement pour vous j'ai passé un mois à le traduire (merci google trad', nihongoresources.com & les autres sites que j'ai utilisé pour m'aider)

Je ne vous filerai pas ma traduction (qui est en anglais), elle ne ressemble à RIEN. J'ai compris après avoir fait ce "truc" que c'était super chaud le boulot de traducteur...

Donc revenons à nos moutons, l'idée du sieur Takayama Fumihiko (auteur de bulletgba, suivez bordel) :
Il s'agit d'un algorithme en 2 passes. L'idée est de diviser l'écran en zones de N lignes (4 il me semble dans bulletgba, je suis monté à 8, heu je crois, je sais plus xD, et ca tournait bien quand même) et de compter le nombre de sprites à afficher dans chacune de ces zones avant de les ajouter, ce qui cré un pseudo-ordre, suffisant pour multiplexer le bousin.

Nous avons donc en structures de données :
- un tableau pour compter les sprites, de 192/N entrées donc
- un tableau de sprites (oui parce que quand même)
- un tableau de pointeurs sur le tableau de sprites au dessus

Et heu, en gros c'est tout.

1) On met tout à zéro (sauf si on veut faire des effets spéciaux complètement foireux, genre j'affiche des restes de l'écran d'avant, ca va surement faire de la merde, m'enfin c'est vous qui voyez hein :p)
2) On donne un par un les sprites à manger au multiplexeur pour qu'il les compte dans le premier tableau
3) On place les pointeurs sur le tableau de sprites en fonctions des sprites comptés : Pointeur 0 = début du tableau, pointeur 1 = début du tableau + le nombre de sprites dans la zone 0, pointeur i = pointeur i-1 + nombre de sprites dans la zone i-1
4) nos pointeurs ainsi calculés, il ne reste plus qu'à ajouter réellement chacun de nos sprites à afficher au tableau de sprites, en passant par les pointeurs, ce qui nous fait notre tableau de sprites pseudo-rangé par rapport à l'affichage
5) on recule tous les pointeurs de manière à afficher un maximum de sprites dans chaque zone (et oui, si on laisse tout ça tel quel, si on a un sprite à y=7, y'aura qu'une seule ligne d'affichée...)

Il ne reste plus maintenant qu'à mettre en place une interruption sur le VCOUNT, déclenchée donc toutes les N lignes (bon juste avant en fait), qui sera chargée de copier un max de sprites de notre gros tableau dans l'OAM, en passant par le pointeur qui va bien par rapport à la zone qu'on veut afficher.

Alors ci dessus je parle par 2 fois de "maximum de sprites", c'est en fait le nombre de sprites réels qui vous allouerez à votre multiplexeur de sprites, sur ma démo il n'y a que 64 sprites alloués au multiplexeur, beaucoup plus dans bulletgba (faut dire il affiche pas beaucoup d'autres sprites donc il pouvait y aller à fond, ca évite les glitchs)

Maintenant le bug : les glitchs donc, c'est en fait quand vous essayez d'afficher plus que le maximum de sprites que vous avez alloué dans une zone. Explication un poil plus claire, si vous avez mettons 32 sprites qui débordent de la zone I sur la zone I+1 (parce qu'ils sont à I*N+4 et qu'ils font 8 pixels de haut par exemple), que vous avez 48 sprites dans la zone I+1 et que vous avez un max de sprites réglé à 64, ben il y aura 16 sprites de la zone I qui ne seront affichés qu'en partie (la partie dans la zone I donc).

J'espère que c'est clair, codons un peu :

spriteMultiplexer.h :
/*
* Copyright (c) 2007, Daniel Borges
* All rights reserved.
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Daniel Borges nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef _SPRITE_MULTIPLEXER
#define _SPRITE_MULTIPLEXER

#include <nds.h>
#include <string.h>

class SpriteMultiplexer {
// Informations
enum {
MAX_SPRITES = 1024, // Sprites handled
MAX_SPRITES_PER_BLOCK = 64, // Sprites used in OAM by the multiplexer
BLOCK_LINES = 8, // Number of lines per block
BLOCKS = SCREEN_HEIGHT / BLOCK_LINES // Number of blocks
} Params;

// Structures
struct SET { // S.E.T. : Sprite Entry Table
SpriteEntry Sprites[MAX_SPRITES];
u16 registeredInBlock[BLOCKS]; // registered sprites with register()
u16 addedInBlock[BLOCKS]; // added sprites with add()
SpriteEntry * Starter[BLOCKS]; // Part of Sprites copied each BLOCKS hbl
SpriteEntry * last; // last copied block
};

static SET zarooSET; // SET with no sprites, used each initFrame

// Data
static SET main[2]; // main screen SET, two tables for double buffer
static SET sub[2]; // sub screen SET, two tables for double buffer
static bool isCompiling;
static SET * displayed[2], * compiling[2]; // 0: main, 1: sub screen
static u16 refused[2]; // refused sprite count per frame // 0: main, 1: sub
static u16 framesSkipped; // how many frame skipped to draw this frame
static u32 spriteCount[2]; // w00t! // 0: main, 1: sub

// Magic
static void on_vblank(void);
static void on_vcount(void);

public:
typedef enum { MAIN = 0, SUB = 1 } screen;

static void init(void);
static void finish(void);

// Call them in this order
static void initFrame(void);
static bool regist(screen s, const SpriteEntry & s);
static void prepare(void);
static void add(screen s, const SpriteEntry & s);
static void optimize(void);
static void finished(void);

// Informations
static inline u16 refusedSprites(void) {
return refused[0] + refused[1];
}

static inline u16 frameSkipCounter(void) {
return framesSkipped;
}

static inline u16 registeredSprites(void) {
return spriteCount[0] + spriteCount[1];
}

static inline u16 availableSprites(void) {
return 128 - MAX_SPRITES_PER_BLOCK;
}

static inline u16 firstFreeSprite(void) {
return MAX_SPRITES_PER_BLOCK;
}
};

#endif /* _SPRITE_MULTIPLEXER */

spriteMultiplexer.cpp
/*
* Copyright (c) 2007, Daniel Borges
* All rights reserved.
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Daniel Borges nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include "spriteMultiplexer.h"

/*
* Static values
*/
SpriteMultiplexer::SET SpriteMultiplexer::main[2];
SpriteMultiplexer::SET SpriteMultiplexer::sub[2];
SpriteMultiplexer::SET * SpriteMultiplexer::displayed[2] = {&main[0], &sub[0]};
SpriteMultiplexer::SET * SpriteMultiplexer::compiling[2] = {&main[1], &sub[1]
};
bool SpriteMultiplexer::isCompiling = false;
u16 SpriteMultiplexer::refused[2] = { 0, 0 };
u16 SpriteMultiplexer::framesSkipped = 0;
u32 SpriteMultiplexer::spriteCount[2] = { 0, 0 };
SpriteMultiplexer::SET SpriteMultiplexer::zarooSET;

void SpriteMultiplexer::on_vcount(void)
{
if ( REG_VCOUNT >= SCREEN_HEIGHT )
return; // Nothing to do if not drawing

u16 block = REG_VCOUNT / BLOCK_LINES;

dmaCopyWordsAsynch(3, displayed[0]->Starter[block], OAM,
MAX_SPRITES_PER_BLOCK * sizeof(SpriteEntry));
dmaCopyWordsAsynch(2, displayed[1]->Starter[block], OAM_SUB,
MAX_SPRITES_PER_BLOCK * sizeof(SpriteEntry));

while ( dmaBusy(3) || dmaBusy(2) )
;

SetYtrigger(REG_VCOUNT + BLOCK_LINES);
}

void SpriteMultiplexer::on_vblank(void)
{
if ( isCompiling ) {
framesSkipped++; // :-(
return;
}

// Swap buffers
SET * tmp = displayed[MAIN];
displayed[MAIN] = compiling[MAIN];
compiling[MAIN] = tmp;
tmp = displayed[SUB];
displayed[SUB] = compiling[SUB];
compiling[SUB] = tmp;

// First copy
dmaCopyWordsAsynch(3, displayed[MAIN]->Sprites, OAM,
MAX_SPRITES_PER_BLOCK * sizeof(SpriteEntry) / 2);
dmaCopyWordsAsynch(2, displayed[SUB]->Sprites, OAM_SUB,
MAX_SPRITES_PER_BLOCK * sizeof(SpriteEntry) / 2);

// Wait end of first copy
while ( dmaBusy(3) || dmaBusy(2) )
;

SetYtrigger(0);
}

void SpriteMultiplexer::init(void)
{
// Init displayed buffer with no sprites
for ( u32 i = 0 ; i < MAX_SPRITES ; ++i ) {
displayed[MAIN]->Sprites[i].attribute[0] = ATTR0_DISABLED;
displayed[SUB]->Sprites[i].attribute[0] = ATTR0_DISABLED;
}
memset(displayed[MAIN]->registeredInBlock, 0, BLOCKS * sizeof(u16));
memset(displayed[MAIN]->addedInBlock, 0, BLOCKS * sizeof(u16));
memset(displayed[SUB]->registeredInBlock, 0, BLOCKS * sizeof(u16));
memset(displayed[SUB]->addedInBlock, 0, BLOCKS * sizeof(u16));
for ( u32 i = 0 ; i < BLOCKS ; ++i ) {
displayed[MAIN]->Starter[i] = displayed[MAIN]->Sprites;
displayed[SUB]->Starter[i] = displayed[SUB]->Sprites;
}
displayed[MAIN]->last = displayed[MAIN]->Sprites;
displayed[SUB]->last = displayed[SUB]->Sprites;

// Init compiling buffer with no sprites
for ( u32 i = 0 ; i < MAX_SPRITES ; ++i ) {
compiling[MAIN]->Sprites[i].attribute[0] = ATTR0_DISABLED;
compiling[SUB]->Sprites[i].attribute[0] = ATTR0_DISABLED;
}
memset(compiling[MAIN]->registeredInBlock, 0, BLOCKS * sizeof(u16));
memset(compiling[MAIN]->addedInBlock, 0, BLOCKS * sizeof(u16));
memset(compiling[SUB]->registeredInBlock, 0, BLOCKS * sizeof(u16));
memset(compiling[SUB]->addedInBlock, 0, BLOCKS * sizeof(u16));
for ( u32 i = 0 ; i < BLOCKS ; ++i ) {
compiling[MAIN]->Starter[i] = compiling[MAIN]->Sprites;
compiling[SUB]->Starter[i] = compiling[SUB]->Sprites;
}
compiling[MAIN]->last = compiling[MAIN]->Sprites;
compiling[SUB]->last = compiling[SUB]->Sprites;

// Init zarooSET
for ( u32 i = 0 ; i < MAX_SPRITES ; ++i ) {
zarooSET.Sprites[i].attribute[0] = 0;
zarooSET.Sprites[i].attribute[1] = SCREEN_WIDTH;
zarooSET.Sprites[i].attribute[2] = 0;
}
memset(zarooSET.registeredInBlock, 0, sizeof(u16) * BLOCKS);
memset(zarooSET.addedInBlock, 0, sizeof(u16) * BLOCKS);
for ( u32 i = 0 ; i < BLOCKS ; ++i )
zarooSET.Starter[i] = zarooSET.Sprites;
zarooSET.last = zarooSET.Starter[0];

// Casting magic spell of sprite Multiplexing : Handling VBL and HBL
irqEnable(IRQ_VBLANK);
irqEnable(IRQ_VCOUNT);
irqSet(IRQ_VBLANK, on_vblank);
irqSet(IRQ_VCOUNT, on_vcount);
SetYtrigger(0);
}

void SpriteMultiplexer::finish(void)
{
irqSet(IRQ_VBLANK, 0);
irqSet(IRQ_VCOUNT, 0);
irqDisable(IRQ_VCOUNT);
}

void SpriteMultiplexer::initFrame(void)
{
isCompiling = true;

dmaCopyWordsAsynch(3, & zarooSET, compiling[MAIN], sizeof(SET));
dmaCopyWordsAsynch(2, & zarooSET, compiling[SUB], sizeof(SET));
while ( dmaBusy(3) || dmaBusy(2) )
;
refused[0] = refused[1] = 0;
}

/*
* Count sprites per block
*/
bool SpriteMultiplexer::regist(screen s, const SpriteEntry & spr)
{
if ( OBJ_X(spr.attribute[0]) >= SCREEN_WIDTH )
return false;

// if y > SCREEN_HEIGHT it's supposed to be a sprite drawed on top of
// the screen, so put it in block 0
u16 block = ( OBJ_Y(spr.attribute[0]) >= SCREEN_HEIGHT ) ?
0 : OBJ_Y(spr.attribute[0]) / BLOCK_LINES;

if ( compiling[s]->registeredInBlock[block] >= MAX_SPRITES_PER_BLOCK
|| spriteCount[s] >= MAX_SPRITES ) {
++refused[s];
return false;
}

++compiling[s]->registeredInBlock[block];
++spriteCount[s];

return true;
}

/*
* Set Starters
*/
void SpriteMultiplexer::prepare(void)
{
SpriteEntry * tmp;

compiling[MAIN]->Starter[0] = compiling[MAIN]->Sprites;
compiling[SUB]->Starter[0] = compiling[SUB]->Sprites;

for ( u16 i = 0 ; i < BLOCKS-1 ; ++i ) {
compiling[MAIN]->Starter[i+1] =
compiling[MAIN]->Starter[i] + compiling[MAIN]->registeredInBlock[i];
compiling[SUB]->Starter[i+1] =
compiling[SUB]->Starter[i] + compiling[SUB]->registeredInBlock[i];
}

compiling[MAIN]->last = compiling[MAIN]->Starter[BLOCKS-1];
if ( compiling[MAIN]->last >=
(tmp = compiling[MAIN]->Sprites + MAX_SPRITES
- MAX_SPRITES_PER_BLOCK) )
compiling[MAIN]->last = tmp;

compiling[SUB]->last = compiling[SUB]->Starter[BLOCKS-1];
if ( compiling[SUB]->last >=
(tmp = compiling[SUB]->Sprites + MAX_SPRITES
- MAX_SPRITES_PER_BLOCK ))
compiling[SUB]->last = tmp;

spriteCount[MAIN] = 0;
spriteCount[SUB] = 0;
}

void SpriteMultiplexer::add(screen scr, const SpriteEntry & spr)
{
if ( OBJ_X(spr.attribute[0]) >= SCREEN_WIDTH )
return;

// if y > SCREEN_HEIGHT it's supposed to be a sprite drawed on top of
// the screen, so put it in block 0
u16 block = ( OBJ_Y(spr.attribute[0]) >= SCREEN_HEIGHT ) ?
0 : OBJ_Y(spr.attribute[0]) / BLOCK_LINES;

if ( compiling[scr]->addedInBlock[block] >= MAX_SPRITES_PER_BLOCK
|| spriteCount[scr] >= MAX_SPRITES )
return;

compiling[scr]->Starter[block][compiling[scr]->addedInBlock[block]] = spr;
++compiling[scr]->addedInBlock[block];
++spriteCount[scr];
}

/*
* draws a maximum of sprites per block by moving back Starters
* ( ~~> fully draw them and not only part of it which is in block )
*/
void SpriteMultiplexer::optimize(void)
{
u16 freeSprites;

for ( u16 i = 1 ; i < BLOCKS ; ++i ) {
// Main screen
freeSprites = MAX_SPRITES_PER_BLOCK - compiling[MAIN]->addedInBlock[i];
compiling[MAIN]->Starter[i] -= freeSprites;
if ( compiling[MAIN]->Starter[i] < compiling[MAIN]->Sprites )
compiling[MAIN]->Starter[i] = compiling[MAIN]->Sprites;
if ( compiling[MAIN]->Starter[i] > compiling[MAIN]->last )
compiling[MAIN]->Starter[i] = compiling[MAIN]->last;

// Sub screen
freeSprites = MAX_SPRITES_PER_BLOCK - compiling[SUB]->addedInBlock[i];
compiling[SUB]->Starter[i] -= freeSprites;
// Keep it in the line
if ( compiling[SUB]->Starter[i] < compiling[SUB]->Sprites )
compiling[SUB]->Starter[i] = compiling[SUB]->Sprites;
// No need to go beyond last block
// -> side effect : last block is always glitch free :)
if ( compiling[SUB]->Starter[i] > compiling[SUB]->last )
compiling[SUB]->Starter[i] = compiling[SUB]->last;
}
}

void SpriteMultiplexer::finished(void)
{
isCompiling = false;
}
Le prochain je le code en C, ça sert trop à rien de faire ce truc en C++...

Bon en gros c'est celui de bulletgba en mieux (sans me vanter, le code d'origine est assez crade, genre il a 2 fonctions qui parcourent le même tableau qu'il appelle d'affilée alors qu'il pourrait sans problème les fusionner mais bon... c'est ma fonction optimize). J'essayais de faire beaucoup mieux mais je suivais pas mal l'idée vu qu'elle marchait bien et le résultat me plait pas, entre autre pour le nombre ahurissant d'appels de fonctions que ca génère. Je viendrais vous mettre ma nouvelle version plus tard, quand je l'aurai enfin codée...

Résultat :
http://dragon/projets/mtpx/mtpx1600.jpg
Oui c'est relativement moche, mais 1600 sprites affichés en en utilisant que 64 (bon ok y'en a qui sont à moitié affichés) mais en même temps 1600 c'est abusé :whst:

http://lywenn.eu.org/projets/mtpx

Edit : ha oui j'oubliais, à priori le code posté déconne xD
Pas grand chose à changer normalement, en fait j'avais dev' mon truc sur émulateur vu que je me suis retrouvé 3 mois sans linker en début d'année, résultat à l'arrivée du linker "HAN PUTAIN CA MERDE COMPLET CA A RIEN À VOIR ABUSÉ", donc y'a juste la 2e démo du site qui marche, pour le code, j'ai pas envie de chercher la version qui a servit à faire la 2e démo, c'est du code d'une vieille version de mon dépot SVN, m'enfin...

[thoduv]

J'ai pas encore tout lu, ca m'a l'air très intéressant, surtout pour moi qui bosse actuellement sur GBA et qui me heurte aux limites techniques. J'ai commencé à écrire un peu le même genre d'algorithme, mais pour gérer la limite de 256 tiles du mode R/S.
Merci donc pour ce long post ! :)

Par contre, je suis tenté de te dire que sur DS, ca ne sert pas à grand chose, étant donné que l'on peut utiliser le GPU 3D, ou un BG bitmap en double-buffering (si on a besoin des deux écrans).

[MsK`]

Le BG bitmap c'est affreusement plus lent et plus lourd et la 3D ca fait tomber à 30 FPS si on le fait sur les deux écrans et puis surtout, ca empêche la 3D, la je peux avoir 1600 sprites sur un décor 3D :)

[thoduv]

Le BG bitmap c'est affreusement plus lent et plus lourd
Ah bon, tu as fait des tests, ça donnait quoi comme résultats en gros ? J'ai pas mal utilisé, et ça tournait pas mal d'après mes souvenirs...

[MsK`]

Bah, j'ai même pas besoin de tester, entre des routines cablées en hard et des routines à faire à la main, outre le code supplémentaire, c'est forcément plus rapide si on utilise le hard. J'ajouterai d'ailleurs que vu que j'utilise les sprites DS, j'ai aussi toujours les effets actifs, je peux appliquer des rotations/zooms & co (bon, c'pas forcément une bonne idée :þ)

[thoduv]

Oui mais là tu n'utilise pas seulement le "cablage" hard, tu est aussi obligé d'utiliser une plus ou moins lourde procédure de tri. Est-ce que ce tri est beaucoup plus rapide que l'écriture sur un bitmap ?

[MsK`]

Sans hésiter, oui. Surtout si t'utilises des effets.
M'enfin en ce moment je bosse sur un jeu qui tourne entièrement au framebuffer et je suis assez épaté par les perfs, mais je demande franchement à comparer un multiplexeur bien fait qui afficher 1600 sprites 8x8 et une version en bitmap.
Je parie que les deux seront aussi fluides, 60 FPS, nickel quoi. Mais je suis persuadé que le multiplexeur
1) consommera beaucoup moins de cpu
-> plus de batterie
-> plus de temps pour faire autre chose
2) consommera collossalement moins de cpu si on utilise les effets.

Faut se rendre compte que la c'est vraiment un tri à la con, il bouffe presque rien le tri, chaque ajout de sprite c'est +1 dans un tableau + copie de SpriteEntry (et ca c'est beaucoup moins lourd que de copier un bitmap !), et au final y'a juste une série de pointeurs à ajuster, c'est vraiment super léger.

[Noda]

moi je suis très intéressé par ton truc, justement pour pouvoir rajouter des effets 3D par dessus les sprites :)

[Nesgba]

1) On met tout à zéro (sauf si on veut faire des effets spéciaux complètement foireux, genre j'affiche des restes de l'écran d'avant, ca va surement faire de la merde, m'enfin c'est vous qui voyez hein :p)
2) On donne un par un les sprites à manger au multiplexeur pour qu'il les compte dans le premier tableau
3) On place les pointeurs sur le tableau de sprites en fonctions des sprites comptés : Pointeur 0 = début du tableau, pointeur 1 = début du tableau + le nombre de sprites dans la zone 0, pointeur i = pointeur i-1 + nombre de sprites dans la zone i-1
4) nos pointeurs ainsi calculés, il ne reste plus qu'à ajouter réellement chacun de nos sprites à afficher au tableau de sprites, en passant par les pointeurs, ce qui nous fait notre tableau de sprites pseudo-rangé par rapport à l'affichage
5) on recule tous les pointeurs de manière à afficher un maximum de sprites dans chaque zone (et oui, si on laisse tout ça tel quel, si on a un sprite à y=7, y'aura qu'une seule ligne d'affichée...)

yop,
je me trompe ou tu vien d'expliquer une utilisation dérivée la methode de tri dite "a casier" aussi appelée "tri postal" ou "tri compteur" ou meme "byte-sort" pour les demomakers ?

Est-ce que ce tri est beaucoup plus rapide que l'écriture sur un bitmap ?
ohh oui enormement !
en fait il ne trie pas a proprement dit, il classe directement sans comparer les valeurs entre elles. et en + sur gba/nds avec le dma tu initialise le tableau temporaire a la vitesse de l'eclair.
en terme de vitesse ca donne des resultat comparable avec aucune autre methode de tri, en fait + il y a de données a trier plus le tri est efficace (il reste lineaire en fait, et le temp de latence du dma ne change pas) tout ce qui peut eventuellement le ralentir c'est le temp d'acces a la ram,
et 4 cycles pour un acces c'est... ridiculement bas :blink:

sur ce genre de plateforme l'indexation est l'un des atouts majeur de l'optimisation (pas comme sur pc ou autre), bref c'est tout benef.

[MsK`]

yop,
je me trompe ou tu vien d'expliquer une utilisation dérivée la methode de tri dite "a casier" aussi appelée "tri postal" ou "tri compteur" ou meme "byte-sort" pour les demomakers ?

Heu, d'accord :rolleyes: :lol:

[MsK`]

Je viens de me rendre compte que ce sujet serait peut-être mieux dans "[DEV] Divers", un modo pour le déplacer ?

[Bobby Sixkilla]

Plutôt dans la section "cours et tutoriel", non? J'y cromprend rien, mais ça a l'air intéressant. :D

[MsK`]

Ben je détaille le truc mais c'est pas à proprement dit un tutoriel, encore moins un cours...

[Nesgba]

a tu envisagé de diversifier un peut ton moteur, genre lui permettre de gerer des sprites de taille differante (enfin c'est surtout la hauteur qui compte), en + avec le systeme que tu utilise puisqu'il s'appuie sur la hbl c'est pas vraiment la taille du sprite hard qui compte, c'est la hauteur en pixel du motif lui meme qui est importante, donc pour faire bien il faudrai une moulinette qui genere un tableau de 2 données pour chaque sprite que l'on as a afficher (position du premier pixel sur les Y, taille vertitable du sprite Y), le but c'est de clipper le motif pour permettre au moteur de liberer le plus rapidement possible les sprites hard utilisés et ainsi pouvoir reattribuer l'emplacement :hmm::ange:

[MsK`]

Ben la y'a aucune limite de taille, c'est juste que plus c'est grand, plus y'a de chances que le sprite ne soit affiché qu'en partie :þ
Je réfléchis un peu à dégager ces glitchs mais faire ça de façon non couteuse, hmm...
L'idée c'est vraiment de faire ça rapidement et le résultat la est très bon, alors j'en reste la. Je code ça pour faire un shoot'em up de type manic/danmaku/barrage/whatever donc la c'est nickel pour afficher les boulettes et j'afficherai ptet des trucs de score ou les powerup, faudra que j'en vois quand j'aurais enfin commencé à le coder...
('tain je voulais le faire cet été, mais avec mon stage, trop pas envie de coder en rentrant le soir :x )

[DJP]

mon futur chef de projet - hahahaha private joke - DJP

Tu crois pas si bien dire :lol:

[MsK`]

Et je confirme ! ENJMIN ownzzz :D

[pmcc]

Pinaise MsK, c'est toi dans le bureau à coté ?

Faut croire vu que tu parles de stage :D

[MsK`]

en + sur gba/nds avec le dma tu initialise le tableau temporaire a la vitesse de l'eclair.
Tu pourrais m'en dire un peu plus ? je suis en phase d'optimisation de la nouvelle version :)

[Matronix]

Putain c'est trop planant ça me rappelle moi qui prog ^^
Personne comprend, on veut optimiser à 300%... ^^

Jdevrais vraiment me lancer ds la prog de DS des fois je me dit c'est le même langage que sur culculettes casio... On peut obtenir des jeux de game boy première du nom pour info, même un poil puis puissant...

Je suppose que c'est pareil, librairies, compilateur et tout ?

La je suis en train de programmer Donjon Master sur graph 85, le jeu de DOS vous vous rappelez ? :p d'ailleurs qqn le porte sur DS (hé mdr je suis plus avancé que lui hihihi ^^). Sur casio le seul problème c'est qu'on a pas la couleur mais bon les sprites sont toujours présents et les niveau de gris ausi.

Mais quand je vois certaines choses qui se programment sur DS jme dit que des fois je devrais vraiment programmer dessus... Parce que c'est pas dur à faire...
Heureusement qu'il y en a certains... Oo ^^

Vive le C vive le C ^^ !

[MsK`]

Heu, la DS c'est quand même colossalement plus balaise qu'une pauv' casio hein... Surtout que ça embarque des moteurs 2D et 3D et tout un tas de trucs hachement bien.

[Matronix]

mdr mais les moteurs on les a créé nous même lol

T'inquiète c'est bien aussi compliqué, d'ailleurs pour avoir programmé sur GBA également je peux te le dire ^^

Je te parle pas de programmer une casio avec la casio, faire un programme en basic. Je te parle bien du C, et qui est bien aussi dur, que l'on programme avec un IDE comme sur DS.

Franchement ça se vaut bien.

[MsK`]

Je crois que t'as pas compris ce que je voulais dire, j'ai jamais dit que c'était pas du C, j'ai dit que la DS, c'est une machine beaucoup plus puissante et qui s'exploite très différemment puisque pour en tirer le meilleur parti, il faut utiliser ses moteurs, le mieux possible.
"Ha mais ma petite dame, une ferrari testarossa et une clio ca se conduit pareil hein, c'est qu'une voiture !"

[Matronix]

Oui j'ai bien compris mais ça ressemble quand même à la GBA qui était bien chiante aussi avec ses modes et compagnie

[DJP]

Oui j'ai bien compris mais ça ressemble quand même à la GBA qui était bien chiante aussi avec ses modes et compagnie

Et bien la NDS c'est encore plus chiant :p

[MsK`]

Ha mais c'est normal que ça y ressemble, la DS c'est une double GBA boostée avec plein de trucs trop bien en plus :)
Et moi je trouve pas ça chiant du tout justement, je trouve ça même super convivial à utiliser, en quelques lignes de code on obtient tout un système top moumoutte avec plein d'effets itou !

Sinon la nouvelle version du multiplexeur a bien avancé ce week end, y'a moins de sprites buggués, c'est plus propre et beaucoup plus léger comme code, me reste encore à optimiser pas mal et à régler quelques problèmes. (je soupçonne 2-3 overflows à droite à gauche et surtout un truc louche qui fait que de temps en temps, quand y'a trop de sprites, genre à partir de 700, une ligne du sprite n'est pas affichée, une ligne en plein milieu du sprite, c'est assez bizarre, mais ca doit être l'OAM qui est mis à jour trop tard. et aussi double écran blanc quand je demande 2000 sprites et ça, ça me fait encore plus peur...)

[Matronix]

Héhé bonne chance à toi

Vous avez la possiblité de tester la couleur d'un pixel sur DS ?
Genre PxlTest ? ça c'est du basic mais un équivlent ?

[MsK`]

En framebuffer oui, pour un bg ou un sprite, en se cassant les couilles inutilement oui. Mais je vois pas trop l'intérêt du truc. (y'a toujours moyen de faire sans)

[MsK`]

http://lywenn.eu.org/mtpx.nds
Version en cours, j'ai juste un problème sur certains sprites dont il manque une ligne en plein milieu, les sprites sont 8x8 en 16 couleurs, quelqu'un a déjà vu ce genre de truc ?
(Appuyer sur Start pour stopper le défilement, et si vous avez de la chance vous verrez que de temps en temps, la ligne manquante du sprite est dessinée ! genre une frame sur 60 donc ca apparait que très peu mais on voit clignoter, un problème de timing je suppose, mais j'ai comme un doute...)

[MsK`]

Je viens de recevoir un mail de sebskater29 qui me fait penser que j'ai toujours pas releasé la bête, je poste donc ici la même version que je lui ai mailé, mais j'ai toujours pas écrit la doc en fait... donc c'est pas la "vraie" version 1.0 :p

http://lywenn.eu.org/projets/mtpx/mtpx-1.0.tar.bz2
(bon, en fait, c'est pas exactement la même version, j'ai encore re-fait l'indentation, j'avais mal configuré mon vim >_<)