[WIP] MD Mugen

[Tryphon]

Pour ne pas polluer le topic "MD vs SNES" avec des trucs plus ou moins sérieux, j'ouvre ici un topic sur un projet qui m'intriguait depuis un moment, et qu'une discussion sur le topic susdit a remis sur le tapis.

Je souhaiterais porter le moteur de versus fighting MUGEN vers la MD. Ça c'est la version courte hyper prétentieuse. Plus réalistement, je souhaiterais développer un moteur de jeu de baston qui permette d'utiliser les ressources développées pour Mugen (on en compte des centaines sur le web), avec bien sûr des contraintes inhérentes à la Megadrive. Même si, au bout du compte, les contraintes s'avéraient tellement fortes qu'aucune ressource ne soit totalement compatible, ça me plairait bien qu'on puisse au moins utiliser les outils de création pour MUGEN pour développer des ressources adaptées. En effet, il y a pas mal de ces outils, ils sont faciles d'utilisation, et on peut développer des jeux vraiment sympas avec très peu de connaissances en programmation.

Soyons encore plus réaliste : n'attendez pas un produit fini, ou en tout cas pas à court ni moyen terme. J'arrive à trouver peu de temps à consacrer à la programmation, et je switche souvent de projet, même si j'essaie d'en restreindre le nombre et que je reviens toujours aux mêmes (il m'est même arrivé d'en finir).

Donc, pour expliquer un peu mieux, un jeu MUGEN c'est fait de plusieurs ressources, pour les personnages, les décors, les GUI.

Commençons par les personnages. Il y a, pour chaque personnage :

• un fichier sff, contenant les gfx du personnage, + quelques infos (hotspot, effets...)
  
• un ou plusieurs fichiers act, contenant les palettes
  
• un fichier air, contenant les animations (timings, déplacements)
  
• un fichier cmd, décrivant les commandes à entrer au pad pour exécuter un coup (spécial ou normal)
  
• un ou plusieurs fichiers cns, qui sont des scripts indiquant comment s'enchaînent les coups (par exemple, l'AI du perso quand contrôlé par la machine est dans un cns)
  

Je précise que je ne suis pas un spécialiste de Mugen et que je découvre au fur et à mesure.

Pour l'instant, je cherche d'une part à développer un moteur offrant des performances correctes, d'autre part à tester ce moteur à l'aide des fichiers sff et air.

Par la suite, je coderai les routines de gestion du pad, et je m'intéresserai au cmd, puis un petit compilateur pour convertir les scripts cns en C ou en asm (ce sera un grand moment, mais c'est pas pour tout de suite).

J'utilise le SGDK de Stef pour le moteur proprement dit, mais uniquement ses commandes bas niveau ; je n'utilise pas le Sprite Engine. Non pas qu'il soit mauvais, bien au contraire, mais surtout parce que je veux développer mon propre moteur pour le réutiliser, en l'adaptant, dans mes autres projets, comme Shinobi arcade.

J'utilise Python pour les programmes de génération de ressources.

Pour l'instant, voilà ce que j'ai fait :

1) j'ai codé et adapté le moteur de sprites, version basique : chaque nouvelle frame est envoyée au VDP par DMA durant le VInt, tous les sprites peuvent être mis à jour dans la même VInt. Stef a proposé d'alterner le perso 1 et le perso 2 une frame sur deux, et Touko a proposé du double buffering, pour l'instant je ne les ai pas implémentés

2) j'ai codé un extracteur de SFF, qui récupère les frames avec leurs paramètres intéressants, et un générateur de ressources MD qui est capable de virer les coublons, d'appliquer un filtre de resize aux frames (selon un algo qui a été discuté dans le topic de la mort, je le redécrirai ici plus tard, mais il n'est pas certain que je le conserve), de convertir en 4BPP, de découper les frames en sprites MD de façon relativement intelligente (en essayant de minimiser la taille en VRAM), et de générer un source .c contenant les infos dans mes structures

3) J'ai codé un extracteur de AIR, qui récupère tout ou partie des animations (pour l'instant, je n'en récupère qu'une seule pour tester, mais ça marche avec autant qu'on veut) et qui génère encore un c correct.

C'est pas grand chose, mais ça me permet de tester la vélocité du moteur.

Alors, avec deux personnages, ça fonctionne bien (animation fluide et pas de frames perdues d'après Gens-tracer). J'ai voulu mettre le moteur à genoux avec 3 persos, mais ça tourne nickel. Je suis donc passé à 4 persos, mais là ça y est, ça ne marche plus (l'écran se fige, je suppose que le DMA est trop long dans la VInt). Néanmoins, ça doit se jouer à peu de choses parce que si je passe la ROM en 50 Hz, ça donne ça :



Je trouve ça assez encourageant. 4 Ryus ça doit représenter à peu près autant que 2 Zangiefs, donc le moteur tient presque la route sans alternance des MAJ ni double-buffering, il doit donc franchement tenir la route en implémentant l'un des deux. Je vais commencer par l'alternance des MAJ parce que le problème du double buffer, c'est que ça coûte cher en VRAM et je risque d'en avoir besoin (faudra bien placer les décors). Si cette alternance a des effets sensibles, j'implémenterai le double buffer.

De plus, vu qu'un Ryu est sensiblement plus gros qu'un Musashi, j'ai bon espoir d'arriver à animer 4 ennemis dynamiques dans mon port de Shinobi avec ce moteur.

Après, encore une fois, je suis pas Vétéa, ça va être lent

[Stef]

Interessant cette idée mais effectivement MUGEN c'est costaud, je me demande comment tu peux adapter ça et que ça reste utilisable... mais en tout cas le projet est vraiment interessant :)
Je trouve aussi le fait que tu utilises les fonctions de bas niveau de SGDK interessant aussi car si le Sprite Engine te facilite la vie, il est évident qu'il ne te permettra pas d'obtenir les meilleurs performances :-/ Je dois encore travailler pour l'améliorer (le code est encore 100% en C).
D'ailleurs les résultats que tu as obtenu sont vraiment très prometteurs ! Je suis étonné que tu puisses animer 3 Ryu en 1 seul VBlank, tu as du bien optimiser le découpage des sprites Ca laisse présager le meilleur pour la suite :)

Aussi tu parles d'un algo pour découper les sprites de manière "intelligente" pour la MD, ce genre d'algo m'interesse car ça manque fortement à rescomp (le compilateur de ressource de SGDK). Actuellement il n'y a aucune optimisation dans le découpage que je fais et c'est très dommage... Mais l'air de rien la question de l'optimisation n'est pas simple, soit tu optimises pour l'utilisation VRAM, soit pour minimiser le nombre de sprite hard, soit pour minimiser le cout sprite par scanline, soit un mix des 2... Je verrais bien une approche brute force où je prends le cout le plus faible en arrangeant les poids selon ce que je veux privilégier

[troudki]

Waouu .. trés belle initiative..
je suis curieux de l'implémentation des hitbox et autres effets dans l'animation des sprites.

[Invité]

4 Ryus ça doit représenter à peu près autant que 2 Zangiefs,

Je dirai facilement, ils font quelle taille tes ryu ??

[Tryphon]

Interessant cette idée mais effectivement MUGEN c'est costaud, je me demande comment tu peux adapter ça et que ça reste utilisable... mais en tout cas le projet est vraiment interessant :)

Je sais pas non plus où ça ira. Après, si c'est pas possible d'automatiser le tout, j'aurai quand même un moteur de Versus Fighting !

Je trouve aussi le fait que tu utilises les fonctions de bas niveau de SGDK interessant aussi car si le Sprite Engine te facilite la vie, il est évident qu'il ne te permettra pas d'obtenir les meilleurs performances :-/ Je dois encore travailler pour l'améliorer (le code est encore 100% en C).
D'ailleurs les résultats que tu as obtenu sont vraiment très prometteurs ! Je suis étonné que tu puisses animer 3 Ryu en 1 seul VBlank, tu as du bien optimiser le découpage des sprites Ca laisse présager le meilleur pour la suite :)

Lorsque j'avais regardé ton Sprite Engine (il doit y avoir plus d'un an), je pensais qu'il n'était pas assez performant, mais j'ai vraiment l'impression qu'il a beaucoup progressé et j'avoue que j'ai hésité. Mais c'est de toutes façons plus formateur pour moi de bosser de zéro. J'ai juste peur que, ta fonction de VInt étant prévue pour fonctionner avec tes libs, je fasse quelque chose de sous-optimal avec mon VInt_callback perso (genre interférer avec ta gestion du DMA).

Je ne suis tout de même pas certain d'être plus efficace que toi   Mais moi aussi c'est encore du 100% C  

Aussi tu parles d'un algo pour découper les sprites de manière "intelligente" pour la MD, ce genre d'algo m'interesse car ça manque fortement à rescomp (le compilateur de ressource de SGDK). Actuellement il n'y a aucune optimisation dans le découpage que je fais et c'est très dommage... Mais l'air de rien la question de l'optimisation n'est pas simple, soit tu optimises pour l'utilisation VRAM, soit pour minimiser le nombre de sprite hard, soit pour minimiser le cout sprite par scanline, soit un mix des 2... Je verrais bien une approche brute force où je prends le cout le plus faible en arrangeant les poids selon ce que je veux privilégier

C'est plus ou moins ce que je fais. Sachant quand même que la force brute est impraticable ici (il y a trop de façons de découper un metasprite), je ne considère que deux ou trois heuristiques et je garde celle qui minimise le coût :

1) je considère tous les découpages possibles en bandes de 8, 16, 24 ou 32 pixels, puis tous les découpages de chaque bande en rectangles de 8, 16, 24 ou 32 pixels, en favorisant et virant les rectangles vides (je crois que c'est l'algo utilisé par Mortal Kombat)

2) même chose mais en commençant par des colonnes

3) je considère toutes les façons de poser une grille de cellules carrées 8x8 (en virant les carrés vides) sur le metasprite, puis toutes les façons de recoller les cellules adjacentes en rectangles

La fonction coût peut être précisée, là j'ai gardée celle qui minimise la taille totale (data + sprite table) en VRAM.

Ici, l'heuristique 3 est trop lente (ou y'a un bug dans mon code) sur certains metasprites, donc je me suis contenté de la 1) (j'ai pas testé la 2). En général, d'après mes tests sur Shinobi, la 3 est meilleure (pas toujours) mais les résultats sont du même ordre de grandeur.

Je suis quand même à la recherche d'un algo plus efficace (temps et résultat).

@troudki : merci
Les hitbox ne m'angoissent pas trop : il n'y en a pas tant que ça (au pire 2 contre 3, de ce que j'ai vu, x2 ; et il n'y a pas de collision avec le décor). Par contre, les conversions des stages (couleurs) et animations de stage, c'est une autre histoire.

@ TOUKO : autour de 56x96

[Invité]

@ TOUKO : autour de 56x96

Ok dans les 1,8 ko alors, x 3 on est à 5.4ko de DMA ..
Pour 4 ryu en double buffer tu dois réserver environ 13ko de VRAM .

[flyz57]

Bien évidemment un mugen jouable sur md, je vote pour toi aux présidentielles

[Tryphon]

Vu le peu de temps que j'arrive à y consacrer, ça sera pour celles de 2022
Sinon vous pouvez voir la vidéo directement ou vous êtes obligés de vous farcir une pub interminable ?

[Stef]

Lorsque j'avais regardé ton Sprite Engine (il doit y avoir plus d'un an), je pensais qu'il n'était pas assez performant, mais j'ai vraiment l'impression qu'il a beaucoup progressé et j'avoue que j'ai hésité. Mais c'est de toutes façons plus formateur pour moi de bosser de zéro. J'ai juste peur que, ta fonction de VInt étant prévue pour fonctionner avec tes libs, je fasse quelque chose de sous-optimal avec mon VInt_callback perso (genre interférer avec ta gestion du DMA).

Je ne suis tout de même pas certain d'être plus efficace que toi   Mais moi aussi c'est encore du 100% C  

En fait j'ai réécrit le Sprite Engine il n'y a pas très longtemps pour le rendre à la fois plus flexible et aussi plus performant.
Malgré tout le fait qu'il soit "générique" le rend non seulement plus complexe mais aussi moins performant. Si tu lis le code de l'unité spr_eng.c tu risques d'avoir peur et te dire qu'il n'y a aucune chance que ça tourne correctement ^^
Heureusement comme tu peux paramétrer pas mal de choses (passer en allocation semi statique plutot que du full dynamique par exemple, ou simplifier le calcul de visibilité..) tu peux quand même obtenir des performances acceptables mais c'est sur qu'il ne sera jamais aussi rapide qu'un moteur fabriqué sur mesure pour les besoins spécifiques d'un jeu.
Et le fait que le code soit encore 100% en C n'arrangent rien (il faudrait au moins passer certaines méthodes critiques en asm).

C'est plus ou moins ce que je fais. Sachant quand même que la force brute est impraticable ici (il y a trop de façons de découper un metasprite), je ne considère que deux ou trois heuristiques et je garde celle qui minimise le coût :

1) je considère tous les découpages possibles en bandes de 8, 16, 24 ou 32 pixels, puis tous les découpages de chaque bande en rectangles de 8, 16, 24 ou 32 pixels, en favorisant et virant les rectangles vides (je crois que c'est l'algo utilisé par Mortal Kombat)

2) même chose mais en commençant par des colonnes

3) je considère toutes les façons de poser une grille de cellules carrées 8x8 (en virant les carrés vides) sur le metasprite, puis toutes les façons de recoller les cellules adjacentes en rectangles

La fonction coût peut être précisée, là j'ai gardée celle qui minimise la taille totale (data + sprite table) en VRAM.

Ici, l'heuristique 3 est trop lente (ou y'a un bug dans mon code) sur certains metasprites, donc je me suis contenté de la 1) (j'ai pas testé la 2). En général, d'après mes tests sur Shinobi, la 3 est meilleure (pas toujours) mais les résultats sont du même ordre de grandeur.

Je suis quand même à la recherche d'un algo plus efficace (temps et résultat).

En réfléchissant un peu je me dis qu'effectivement tu ne peux pas faire un brut force sur chaque combinaisons, rien que le fait que les tiles de 8x8 ne soient pas forcément aligner (je sais pas pourquoi j'étais parti dans cette logique) peut t'engendrer une quasi infinité de combinaison :-/ Il faut donc procéder autrement...
Je vais chercher s'il n'existe pas déjà d'algos tout fait pour ça... sinon je vais surement tenter un algo type génétique avec un calcul de couts à minimiser. J'aime bien regarder l'évolution de ces algos (voir le cout qui chute au fil des itérations) :)

[Tryphon]

Je m'y connais pas vraiment en algos génétiques (je connais le principe, mais je suis pas complètement sûr de voir comment ça marcherait ici) et je suis très très curieux de voir ce que ça peut donner

J'ai implémenté la "mise à jour retardée", sur une simple anim c'est insensible, après faudra voir ce que ça donne au niveau du gameplay.

Je suis en train de décortiquer la doc Mugen pour savoir comment est implémentée la "physique" (vitesse de marche, de chute, impulsion de saut).

[Stef]

L'idée de l'algo de génétique c'est de partir de plusieurs générations aléatoires de solutions (ici un découpage aléatoire des sprites en tuiles de 8x8 jusqu'à 32x32) et ensuite tu le fais évoluer les générations en croisant les meilleurs générations entre elles (en utilisant un calcul de score) et tu conserves les meilleurs générations résultantes et ainsi de suite. Aussi parfois tu ajoutes quelques 'mutations' aléatoires à tes générations pour éviter de rester bloquer dans un minimum local... Les différentes paramètres (nbr de génération, mutation..) s'ajustent selon les besoins.

Cool si la maj retardée fonctionne bien, c'est une idée à laquelle j'ai toujours pensé mais jamais expérimenté en conditions réelles. Perso excepté pour un coup instantané (type petit coup de poing ou pied) je pense que c'est imperceptible.

[Invité]

et puis rien ne t'empêche de garder à chaque vblank combien tu as transféré après chaque DMA, et de ne retarder que si tu es hors budget pour le suivant .

[Tryphon]

L'idée de l'algo de génétique c'est de partir de plusieurs générations aléatoires de solutions (ici un découpage aléatoire des sprites en tuiles de 8x8 jusqu'à 32x32) et ensuite tu le fais évoluer les générations en croisant les meilleurs générations entre elles (en utilisant un calcul de score) et tu conserves les meilleurs générations résultantes et ainsi de suite.

Oui je connais le principe. Ce qui m'embête ici, c'est :

* le découpage aléatoire ne peut pas être totalement aléatoire (tu dois quand même recouvrir tout le sprite, si possible sans redondances)

* comment tu croises deux découpages ? En sélectionnant 50% de deux bons découpages, tu as peu de chance que le fils soit bon ?

Aussi parfois tu ajoutes quelques 'mutations' aléatoires à tes générations pour éviter de rester bloquer dans un minimum local... Les différentes paramètres (nbr de génération, mutation..) s'ajustent selon les besoins.

Cool si la maj retardée fonctionne bien, c'est une idée à laquelle j'ai toujours pensé mais jamais expérimenté en conditions réelles. Perso excepté pour un coup instantané (type petit coup de poing ou pied) je pense que c'est imperceptible.

J'ai étudié un Ryu et Kung-Fu Man (le perso de base de Mugen qui sert de tuto) et même un petit coup attend 3 frames avant de cogner. De plus, je vais essayer de faire en sorte que les hitbox soient mises à jour immédiatement, quitte à ce qu'elle ne correspondent pas à la frame affichée pendant 1 tick.

@Touko : bonne idée. Parce qu'à part quelques persos énormes, la MAJ des deux persos doit passer. Ça peut même me permettre d'animer du décor (parce que si lui est retardé d'une frame, ça gêne pas).

[ichigobankai]

Pour animer du decor -a mon sens- le plus pertinent est de charger tes tiles au départ et de faire les update pendant l'affichage actif. Et donc de garder le précieux temps du VBL pour les maj sprites (chargement, attributs & affichage)

[Stef]

Oui je connais le principe. Ce qui m'embête ici, c'est :

* le découpage aléatoire ne peut pas être totalement aléatoire (tu dois quand même recouvrir tout le sprite, si possible sans redondances)

* comment tu croises deux découpages ? En sélectionnant 50% de deux bons découpages, tu as peu de chance que le fils soit bon ?

Alors oui le découpage initiale n'est pas complètement aléatoire, disons qu'il faut que tu partes de plusieurs solutions qui fonctionnent (sans chercher l'optimal). Par contre t'as raison, ici la notion de "croisement" ne fonctionne pas vraiment, ou plutot tu es obligé de croiser et d'injecter des modifs pour les croisements ne se chevauchent pas :-/
Du coup ça me parait un peu tricky à réaliser... une autre méthode est juste d'appliquer quelques mutations aux meilleurs générations mais en général la méthode des croisements donnent de meilleurs résultats (ou plutot plus rapidement).

[Tryphon]

Dans tous les cas, je suis très intéressé par tout progrès dans ce domaine Mais j'ai vraiment l'impression que c'est pas un problème simple. J'ai un pote prof d'Info que ça pourrait intéresser mais je doute qu'il en sache plus que toi sur le sujet

Pour animer du decor -a mon sens- le plus pertinent est de charger tes tiles au départ et de faire les update pendant l'affichage actif. Et donc de garder le précieux temps du VBL pour les maj sprites (chargement, attributs & affichage)

Oui, si le décor bouge peu. Je pensais à ces stages sous la tempête avec les arbres qui bougent. Ça doit pouvoir se faire par de l'animation de tiles, mais ça nécessite du DMA.

Bon de toutes façons j'en suis pas encore là. Les fichiers CNS de Mugen sont des horreurs à relire, et j'ai de la physique à bosser.

[Invité]

Oui, si le décor bouge peu. Je pensais à ces stages sous la tempête avec les arbres qui bougent. Ça doit pouvoir se faire par de l'animation de tiles, mais ça nécessite du DMA.

Tout dépend de ce que tu veux faire, mais un hscroll ligne peut aussi bien faire l'affaire .

[Tryphon]

En l’occurrence non, ça sera pas possible. Mais de toutes façons y'aura du hscroll pour le sol :)