Quelle structure de données pour un jeu de plate-forme ?
Vaste question... Et surtout, qu´est-ce que j´entends par là ?

Alors c´est simple, imaginez le truc : vous vous réveillez un jour en vous disant "tiens,
et si je me faisait un petit jeu de plate-forme ?" .

Ca n´a pas l´air bien dur comme çà : un petit script de chargement de niveau à partir d´un fichier quelconque, une gestion d´évenements utilisateur, 2-3 déplacements de sprites, chargement de séquences pour animation, une IA peut-être un jour, et des collisions...
Plein, plein, plein de collisions...

D´abord parce que le sol, c´est pas forcément un truc plat et unique (entendez par là la présence de plates-formes justement) et qu´il va bien falloir indiquer à mon petit bonhomme qu´il arrête de tomber, maintenant ça suffit !

Alors voilà, au vu de ce que les gens font depuis des années pas mal de solutions s´offrent à moi.
D´abord les collisions c´est plus facile à gérer entre rectangles, orientés tous pareils,

pas d´angles bizarre, etc. D´où les tiles... Mais bon, des tiles bien rectilignes, c´est pas drôle pour faire du Level Design marrant. Remarque, je peux tricher et mettre des propriétés d´angles sur certains tiles et en adaptant le comportement de mon perso quand il se trouve en contact avec celle-là.
Par exemple sur une pente montante de gauche à doite, le tile est infranchissable par en dessous et par la droite et l´entrée par la gauche ou le haut entraine une modification du comportement de mon perso (animation spéciale (peut-être), déplacement sur x et y en même temps, etc.) En gros ça ressemble à ce qu´ils ont fait pour Megaman... Et c´est cool.

Mais bon, et si je ne veux pas m´arrêter là ? Je voudrais des déplacements à la Sonic, ou de la grimpette à la Strider... Comment modeliser des changements d´angles comme ça ? Et puis je peux pas modéliser d´angles aigus...
Oh, on peut toujours se debrouiller avec des tiles à propriétés particulières, mais quand on insiste un peu, on touche du doigt ce qui fonctionne dans LineRider : la ligne de déplacement.
Bon, alors comme je suis une faignasse, je vais conserver mes tiles et leur affecter une ligne de collision. Une ligne de collision est un vecteur (orienté, donc) franchissable dans un sens et pas dans l´autre. Bon arrivé là, ça fait plein de nouveaux problèmes.

D´abord pourquoi est-ce que je me traine encore des tiles ? Ok, on les jette.
Ensuite l´animation... Ben ouais, quoi, j´ai un ensemble de surfaces de déplacement qui n´est plus discret, alors que l´ensemble de mes animation l´est, lui. Je dois donc modifier mes anims on the fly. Bon je ne suis pas graphiste, et encore moins animateur, et travaille donc avec des sprites tout faits...
La question c´est dans quelle mesure, est-ce que je peux pivoter certaines parties du perso (jambes par rapport au corps, par exemple) sans que ça fasse bizarre ? De même, jusqu´où puis-je bourriner en laisser mon perso droit quand les pentes changent sans que ça choque ?
Etc., etc...

Et puis, bon je peux arrêter de faire la fine bouche et tenter des collisions sur des objets géométriques complexes, et puis évaluer un comportement entre plusieurs objets (si un objet que se déplace rencontre les surfaces de plusieurs objets irréguliers en même temps), et puis, et puis... Bon on va s´arrêter là, hein ? J´imaginais seulement un vieux platformer old-school.

Voilà en gros l´état de ma réflexion. J´ai cherché de par le net, des gens qui se seraient
posé les mêmes questions. Un rapport sur "Avantages et inconvénients de la méthode Mario par rapport à la méthode Heart of Darkness", par exemple. Et rien.
Donc je cherche des avis, des expériences, sur la façon de modéliser un niveau de plate-forme, en prenant en compte la façon d´y lier des graphismes (genre pour un tile c´est simple, mais pour un vecteur ? (en fait, je rend indépendants le décor dans lequel on évolue et le chemin sur lequel on se déplace)), la façon de le charger, les possibilités pour sauvegarder une altération d´état, pour affecter des effets divers et variés au personnage, etc.

Ca reste bien entendu de la théorie pure, mais essayez de rester réalistes quant aux prérequis pour la mettre en pratique... Tant matériels qu´humains, les prérequis, d´ailleurs...
Je fais deux trois tests en java pour l´instant et mes premiers essais avaient été effectués avec c++ et sdl, assaisonnés d´un poil d´allegro. Donc si vous avez besoin de recourir à des termes plus techniques pour décrire les idées, n´hésitez pas.
J´accepte les schémas UML, les diagrammes en tous genre et même les gribouillis sur papier :D

Je suis en train de me mettre au xna, pour rire, alors si vous en faites et que vous voyez des trucs qui me feraient tout le boulot, n´hésitez pas à prévenir :D

Merci d´avance à tous...

Houlalaaa
Arrête le café ou reprends la clope mais la t´es trop stressé !! ;- )

Je voulais mettre une réponse pour félicité ce message interressant. Malheureusement je ne pourrai aider de ce coté pour plusieurs raisons :

1. je ne code pas en 2d

2. je code via un moteur 3d qui m´aide pour tout les aspects techniques du dev (vecteurs, collisions, etc)

3. je pourrai meme pas te donner de piste car je code en vb et pas en c++

Par contre si tu veux un jour t´essayer a vb.net avec tv3d et que tu as besoin d´un coup de main, je t´aiderai du mieux possible !
Non, non, je ne monte aucune secte ..... :-þ

A++
Nico

Bon j´ai laché prise au millieu et je vois pas trop ce que tu demande. Mais au risque d´etre hors sujet avec Multimedia fusion tu fait tout de dont tu a enoncé plus haut sans prog.

En fait touhizy se pose la question de la structure de donnée a adopté pour un jeu de plateforme. Plusieurs structures différentes sont utilisées dans les jeux commerciaux. Ils se demandent quels sont les avantages/inconvénients de chacune de ces méthodes.

J´en ait déjà parler avec lui. Ce qu´il présente est le fruit d´une rélexion basique. On cherche a obtenir des avis complémentaire.

daedalus, sais tu quel est le format interne de multimedia fusion et les raison de ses choix ? Peut etre une page d´explication ?

Houlala, on joue pas dans la meme cour là ! je dois bien avouer que je n´en ai aucune idée. Je ne sais pas trop ce que tu entend par "format interne" donc c´est plutot mal barré. Je me contente juste d´utiliser le logiciel !

Nikko, en fait le problème ne dépend ni du langage ni du type de developpement(3D/2D). Imagine juste que t´ais à faire un mario... Comment représente-tu les blocs sur lesquels tu vas marcher et dans lesquels tu va mettre des coups de tête ? Si c´est en 3d, tu vas dire "dans un repère xyz, j´ai un sol de telle dimension, avec telle texture", ou bien en 2D "j´ai un tableau de 200 cases par 200 et les trois rangées du bas contiennent des blocs de briques".
Je me demande juste quelles structure sont marrantes et quelles sont leur limites. Par exemple, tu sens bien qu´un tableau, pour représenter les loopings de sonic c´est pas cool, alors que faire des plateformes de FlashBack ça passe...

Daedalus, c´est dommage que tu n´es pas une idée de comment fonctionne Multimédia Fusion, parce qu´en fait c´est justement le côté "mais à quoi ont pensé les mecs qui ont fait ça" qui m´intérresse. En même temps, je suis allé voir leur page et leur truc à l´air de faire tellement de trucs que pour imaginer les concepts qu´il y a derrière, faut s´accrocher...

PS: désolé si mon post est trop long... comme on dit, c´est pas la taille qui compte :D

C´est pas le fait que ton post soit long, c´est juste que j´ai décroché car le language de prog et tout, j´y connais rien.

C´est vrai que MMF est assez particulier, tout peut ce gerer par evenement et conditions. Du coup avec ce logiciel on peut faire des petits programmes mais egalement de bon jeux. Quand à la techologie untilisé, j´en ai pas la moindre idée. Désolé.

Sujet tres intéressant !! !

Pour ma part, voici l´idée que j´en ai (cette idée, je l´ai adapté a mon exemple "promenade", sur mon site §2.A.2)

Je définis des zones "interdites", c´est a dire que, dans ma classe "map", j´ai une fonction qui s´appelle "Interdit", qui prend en entrée le rectangle englobant du perso, et qui me dit vrai ou faux, selon que j´ai le droit d´etre la ou pas (par rapport a la map) : typiquement si je suis dans un mur ou pas.

A partir de la, il me suffit de déplacer mon perso, en testant, a chaque déplacement, si je ne rentre pas dans un mur. Si je rentre dans un mur (donc si la coordonnée finale est interdite), alors je ne valide pas le déplacement, histoire de ne jamais etre dans le mur...

A partir de la, je peux faire une map en tile, ou alors d´une autre méthode, tant que la fonction "interdit" est fiable.

Apres, on peut imaginer un moteur physique (pensanteur gérée par f = ma)...

Idées a développer...

Bien touhizy!

Ca fait plaisir de voir des codeurs en 2D !

Perso je travaille sous mon nouveau moteur de carte qui me servira aussi bien à faire de la plateforme que de la baston à la STREETS OF RAGE.

Pour simplifier, le moteur utilise un bloc qui entour le personnage, et calcule si il touche un bloc décor. Si oui, alors il regarde la position du joueur du tampon précédent positionne correctement le joueur : haut, bas, gauche ou droite.

Je peux donc faire pleins de choses comme bloquer le joueur, le téléporter, lancer des évenements, glisser, mourrir, sauvegarde, etc.

Je pense qu´au final je me la régalerai bien, car j´ai inclus l´éditeur qui va avec. Il est assez évolutif car par la suite je pourrai ajouter de la plateforme irrégulière à la GHOULS´N GHOSTS ou de la collision à la STRIDER. Mais bon, pour l´instant je reste dans du classique.

Quand à SONIC 1, c´est un travail de fou ! Gérer les boucles avec en plus une "physique" sur ces mêmes boucles, c´est assez énorme. Je pense qu´il doit y avoir beaucoup de math derrière ; arriver à ce stade ça ne m´interrese pas encore, mais je salut le gros travail des programmeurs ;)

Sujet interressant en effet. J´ai etudié un peu la question pour mon jeu de plateforme 2D.

Pour le decor, j´ai choisi la facilité. Un tableau et pour chaque case, le type de tile : un mur, une echelle, une corde, etc... C´est simple mais comme tu dis ca empeche de faire des niveaux avec des pentes, des denivelés.

Les plateforme, c´est des rectangle qui se deplace. Le perso peut les traverser par dessous mais pas par dessus. A ce moment il y a collision.

Pour les persos et objet, j´ai fait une vraie physique et les deplacements c´est des impulsions. Ca ca marche bien.

J´ai beaucoup galeré pour les collision entre formes, mais j´ai trouvé un truc sympa : Gere les collisions axe par axe (deja le long de X et ensuite le long de Y). Ca simplifie tous les problemes (le plus gros probleme = quand on collision un coin).

reno_ > en effet, les boucles dans sonic, ça doit etre plus dur a gérer.

Pour ce qui est des courbes, pentes, looping de sonic, ou n´importe quel courbe "parfaite" si j´ose dire : c´est a dire douce sans cassures (polynomiale, C1 ou C2 continue), il y a ce qu´on appelle les courbes de Bézier, c´est un outil tres puissant, qui permet la douceur d´une courbe si j´ose dire, le level of details, le controle totale de l´allure grace aux points de controles.
Il est facile de calculer la pente, ainsi qu´une normale a une courbe de Bézier en n´importe quel point paramétré, ce qui permet, couplé a un moteur physique, de faire, entre autres, des pentes quelconques, en sachant en tout point comment doit agir la physique...

Les Béziers sont des cas particuliers des B-Splines, eux meme cas particuliers des NURBS.

Bon, je voulais juste mentionner cet outil, puisqu´on parlait de pentes et des loopings. Si vous voulez en parler, je reste dispo.

Fvirtman 1> La fonction interdit c´est un peu bourrin à mon gout. Imagine que j´arrive sur une pente : la fonction interdit teste si je peux me déplacer de x vers la droite. Ma zone de collision entre en contact avec le sprite de la pente et me dit "ha non, tu peux pas" alors qu´il aurait suffit que je me déplace un peu de y en haut pour que ça passe.

reno_> Tu met le doigt là où ça fait mal. Tu testes la présence d´objets dans la zone de collision et tu te repositionnes, et tout va bien. Mais quand tu vas placer tes plateformes irrégulières, vas-tu laisser l´animation d´origine, à la Ghouls&Ghosts ou Megaman, avec un perso qui marche tout droit dans une pente, ou bien inclure des variations dans l´animation ?
Les variations peuvent être prévues à l´avance par type de pente comme dans Strider, auquel cas tu ne disposes que d´un nombre fini d´animations. Ou alors, tu peux les modifier en tournant ton sprite on the fly, pour obtenir un effet Sonic (cela dit, après avoir maté des planches de sprites, il me semble que Sonic utilise des animations qui ont été pivotée à l´avance, d´où beaucoup de sprites).

Lapintade > Gérer les plateformes bizarres indépendemment du décor, c´est une super idée... On peut leur affecter un comportement comme pour les ennemis, etc. On pourrais d´ailleurs les charger et les gérer dans les mêmes fonctions que les ennemis. Mais, dans ton modèle, un plafond, c´est une plateforme spéciale (qu´on peut passer par en dessus et pas par au dessous) ou bien c´est du décor ?
Sinon t´as une vraie physique de collision ? C´est pas trop compliqué à mettre en place ? C´est quoi, un vecteur vitesse et un coef de poids par objet (ou même pas de poids)? Et du coup, y as-tu couplé des plateformes en pente ?
Je pensais aussi aux collisions par axe, d´où le fait que les zones de collision soient modélisées par des rectangles alignés : c´est beaucoup plus facile de repérer les intersections. Mais du coup je suis limité pour les pentes... C´est toujours le même problème...

Fvirtman 2> J´aime bien les bézier pour tracer des trucs bizarres... Le problème, ça va être comment réagir lorsque je détecte une collision avec une bézier. Je mets les coins inférieurs de la zone de collision en contact avec la courbe, quitte à avoir un effet de "je vole au dessus du sol", ou bien j´y colle le milieu-bas de mon sprite quitte à ce que les coins mordent un peu la bézier et que, dans les coins, l´anim donne l´impression de mettre les pieds dans le sol ?
C´est là qu´il nous faudrait l´avis d´un animateur, je crois, qui pourrait nous dire jusqu´où on peut aller sans que ça choque...
Et sinon, as-tu une idée pour indiquer un sens dans lequel la bezier est franchissable ? C´est vrai qu´on peut aussi la laisser infranchissable tout le temps, c´est ce qui est bien avec les lignes de déplacement...

En tout cas, merci vous triturer les méninges avec moi. Vous me donnez plein de nouveaux angles d´attaque.

touhizy > "l´anim donne l´impression de mettre les pieds dans le sol "

Une belle façon de tricher pour éviter ce probleme (qui en est quand meme un) :

http://image.com.com/gamespot/images/2003/screen0/918792_20030826_screen001.jpg

Autrement dit un sol en profondeur, qui fait joli, et meme en cas de pente, tu n´auras pas l´impression que le perso rentre dans le sol, mais est juste légerement plus en avant (illusion d´optique powa)

Il est vrai que pour les pentes, ça posera probleme avec une fonction "interdit", c´est vrai que cette fonction est idéale pour les jeux de plateforme bien carrés, mais quand il y a des pentes ça change un peu.

http://yannick.fleurit.free.fr/Culture/Retro%20Super%20Mario/Super%20Mario%20Bros.%203%20(3).png

On peut s´inspirer des précurseurs (comme SMB3), on y voit des pentes régulieres : ici, on voit clairement 2 tiles de pentes : un a 45°, l´autre un peu plus plat.
Faudrait voir comment ils ont fait exactement. (surement pas des Bézier a l´époque)

"Et sinon, as-tu une idée pour indiquer un sens dans lequel la bezier est franchissable ? C´est vrai qu´on peut aussi la laisser infranchissable tout le temps, c´est ce qui est bien avec les lignes de déplacement... "

--> Oui, la Bézier va te permettre pas mal de choses :
Elle est paramétrique, donc de 0 à 1, tu avances sur la courbe, elle a donc un sens. A partir de la, tu peux calculer un vecteur vitesse. 2 façons :
- tu prends la dérivée de la courbe (comme elle est polynomiale, ça se fait bien) au point P de parametre t sur la courbe. (point en face duquel tu es)
- tu calcules un point P, et P +dt, tu obtiens un vecteur (P,P+dt)

Une fois que tu as ce vecteur un produit vectoriel avec (0,0,1) (ou alors un déterminant), ça se simplifie bien, te donne la normale au point P.
Cette normale te donne le "haut" de la courbe.
Elle te sera utile pour le sens, mais aussi pour d´éventuels rebonds sur la courbe.

A partir de la, pour un point X donné, le signe du produit scalaire PX.N va te dire si tu es en dessous ou au dessus de la courbe.
De la, je pense que tu peux t´en sortir pour connaitre le sens pour franchir la courbe.

Fviertman> J´aime bien l´idée à la Rayman de rendre la zone profonde pour dissimuler qu´on est flou sur la jonction !
En fait maintenant que j´y pense, ils ont triché pareil dans plein de trucs : MarioWorld, Ghouls&Ghost. Pas en profondeur, mais avec des sols épais ou ça ne génait pas trop que le pied s´enfonce.

Pour SMB3, j´ai ma petite idée, c´est un peu comme ça que je comptais procéder. Les tiles de pentes induisent un déplacement modifié (ajout d´un déplacement sur y et reduction sur x). Suivant le type de tile de pente, on peut déduire facilement où se situe le contact en y par rapport à où on a avancé en x. Si je suis au début, je touche le sol quand je suis en bas du tile et plus j´avance plus je monte, par exemple.

Ca devient ennuyeux comme méthode dès lors qu´on imagine des pentes séparées par de très petits angles (une montée avec un plafond qui monte aussi en dessous) et que ces pentes ne peuvent être séparées par une horizontale, ou une verticale. La il ya deux comportement à gérer sur un seul tile, il faut vérifier ta position relative quand tu arrive dessus, etc.. Et du coup, t´as plus vite fait de gérer ça comme des traits et de dégager le concept de tile.

C´est cool avec des béziers, faut que je vois ce que ça donne...

A mon avis, pour certains cas particuliers dont tu parles, les level-designers doivent etre brieffés

Par exemple, je suis sur que les level designers de SMB3 ont eu comme consigne de ne pas faire de plateformes juste au dessus des pentes.

Ne jamais oublier que les programmeurs sont des tricheurs : quand un cas particulier peut arriver, mais de façon improbable, au lieu de faire 200 tests a chaque boucle, on brief les level-designers en leur disant "ne fait pas ce cas", ainsi, on ne demande plus au programmeur de tester ça, on gagne en vitesse, et on sait que ça n´arrivera pas

-"les courbes de Bézier" ; il faudra que je me renseigne là-dessus un jour, mais pour l´instant j´en ai pas encore besoin.

-pour les pentes, j´ai utilisé le systeme de l´évenement automatiques pour "ALICE AND THE GOLDEN COINS" : quand le joueur touche ce type de bloc, le joueur monte ou descend tout seul ; par exemple, dès la première collision, la position d´arret de l´evenement automatique sera lorsque le joueur aurra atteind la position Y=Y-TailleBlocY. Ce systeme aurrait pu être manuel, mais ça me posait un problème pour replacer le joueur lorsqu´il sautait sur la pente... d´ou peut être l´utilité d´une courbe Bézier sur ce type de bloc décor.

-Tu as aussi le choix de faire de tous petit blocs dans le moteur que le joueur descendra comme des escaliers, alors qu´à l´affichage il y aurra une belle pente avec une belle pelouse déssinée !

-avec mon moteur actuel, je peux inclure tout type de collision pour chaque type de bloc. Pour "GHOULS´N GHOST", je fairais bien une collision en calculant une barre verticale en plein milieu de mon joueur et le bloc du sol ; si les points non transparents de la barre touchent les points du bloc decor non transparents, alors je boucle y=y-1 jusqu´à ce qu´il n´y ait plus la collision ! Je peux aussi régler dans quel évenement le joueur se trouve et comment il doit réagir lorsqu´il touche chaque bloc décor.

-pour SONIC 1 ( c´est mon préféré ), j´ai réfléchis au sujet aujourd´hui. Je pense que c´est plus simple que ce qu´on pense : le joueur se déplace et touche le bloc décor de la boucle. A ce moment un evenement automatique est lancé. Selon la vitesse lors de la collision, Sonic faira un tour complet plus ou moins rapide, alors que si il arrive lentement il reviendra en arrière ou tomber lorsqu´il aurra la tête en bas. C´est qu´une idée...

c´est pas bete cette idée d´evenmeent. Pour le sonic 1, je vois bien les bloc de la boucle te donner de l´acceleration pour aller vers le prochain bloc. Et comme il y a quand meme de la gravité, si tu ne vas pas assez vite , tu vas tomber...

->

-pour SONIC 1 ( c´est mon préféré ), j´ai réfléchis au sujet aujourd´hui. Je pense que c´est plus simple que ce qu´on pense : le joueur se déplace et touche le bloc décor de la boucle. A ce moment un evenement automatique est lancé. Selon la vitesse lors de la collision, Sonic faira un tour complet plus ou moins rapide, alors que si il arrive lentement il reviendra en arrière ou tomber lorsqu´il aurra la tête en bas. C´est qu´une idée...

C´est une idée mais j´ai pas l´impression que les développeurs procèdent comme ça... ?

A ce propos, je pense que reno a raison, mais pour le premier sonic :

Il me semble (mais je ne suis pas sur) que dans le premier sonic, quand tu amorces une loop, soit tu la passe, soit tu reviens au départ, mais touours en suivant le chemin de la loop :
il me semble que la chute dans la loop n´est pas gérée (si par exemple, tu arrives a vitesse 0 en haut, normalement, tu tombes, mais la, tu te contentes de repartir en arriere en suivant bien le mouvement de la loop.
Il me semble...

Je ne crois pas, il me semble que l´on pouvait meme sauter (donc aller vers le bas) quand on était en haut d´une boucle.