[MD] Gestion des ennemis dans un niveau

[Tryphon]

Salut les codeurs

dans mon projet de Shinobi, j'ai un truc qui m'agace un peu, c'est la gestion des ennemis présents sur un écran à un moment donné.

Je m'explique : un niveau fait 2048 pixels de long, sur lesquels 320 sont affichés à un moment donné à l'écran. Dans le niveau, il y a (mettons) une vingtaine d'ennemis (c'est plutôt 50 en fait).

Je ne peux pas, à chaque frame, mettre à jour les 20 ennemis, ce serait trop long. Je ne mets donc à jour que les actifs, ceux qui sont présents à l'écran.

J'ai 3 idées pour procéder :

1) j'ai une liste des 20 ennemis quelque part, et à chaque frame, je teste si un objet est apparu à l'écran. Il devient actif, jusqu'à sa mort. Problème : ça m'oblige à faire 20 tests à chaque frame, et c'est lent sur une Megadrive. Je peux un peu ordonner la liste, mais c'est vite limité car certains niveaux sont vraiment en 2D (1024 par 1024 par exemple).

2) je fais 4 listes ordonnées, une par direction (chaque entrée est un pointeur vers un ennemi, pour éviter que ça bouffe trop de place et les redondances)

3) je découpe le niveau en blocs carrés plus petits (genre 128 x 128) dans une structure type quadtree, et je ne parcours que les blocs affichés (en tout ou partie) à l'écran

Est-ce que quelqu'un sait quelles sont les techniques utilisées dans les JV de l'époque 8/16 bits ? Dans les générations ultérieures, je pense que regarder toute la liste n'est pas vraiment un problème.

[Hpman]

Tu évolues comment dans ton jeu? Comme Shinobi (scroll horizontal uniquement, sens unique, pas de retour) ?

[Tryphon]

Shinobi c'est scrolling dans les quatre directions, retour possible, certains ennemis respawnent...

[upsilandre]

En général j'ai plutot l'impression que les ennemis sont chargé en meme temps que la tilemap, ils font partie des metadata de l'environnement (comme les items par exemple)

[Hpman]

Shinobi c'est scrolling dans les quatre directions, retour possible, certains ennemis respawnent...

Ah ok, j'ai la mémoire qui flanche passé les premiers stages 


Bon, je pense que tu devrais pouvoir test si une 20aine d'entités sont à l'écran ou pas. Dans mes bricolages en mode bourrin sur neo je peut en check dans les 150 sans soucis. Faut voir le temps cpu que t'as de dispo pour cette méthode toute en finesse 


Tu as un papier sur MC kids qui aborde le sujet, bien qu'un peu flou à mon gout sur l'axe Y: http://games.greggman.com/game/programming_m_c__kids/

Personnellement je couperais ça en blocs ou bandes horizontales, pour avoir un premier tri rapide. Si la densité est relativement égale dans tout le niveau tu dois pouvoir faire des blocs assez grands.

[Invité]

Je vais te dire je que je fais dans mon jeu (vu que je gère 64 ennemi par map grand max).
Si le nombre max de perso a l'écran est atteint je ne fait rien sinon :
A chaque frame je regarde si l'ennemi est a" l'écran" (enfin dans les fait il faut qu'il soit hors de l'écran mais pas trop loin) pour pas qu'il apparaît subitement a l'écran , s'il est a l'écran je l'affiche( et je fait tous les calculs relative a l'ennemi).

Vu que testé 64 ennemi est beaucoup , je ne teste que par bloc de 8 (donc en 8 frame je test le tout).
Vu que la MD est plus puissante que la SNES en cpu tu peux peut être testé par bloc de 16 (et donc en 16 frame tu test les 256 ennemis).

[Stef]

Je pense que la structure classique est de type "graphe", du moins c'est comme ça que je ferai. Quand tu te balades dans ton niveau, tu te balades également dans le graphe qui représente ton niveau, chaque noeud du graphe peut représenter un espace écran de 512x512. Et pour chaque noeud tu as un certains nombre "d'events" (arrivé d'un nouveau ennemi, bonus, cutscène, boss...) selon les conditions (position du joueur, défaite d'un ennemi...). L'avantage c'est que du coup, au maximum tu testes les conditions que pour un espace de 512x512, ce qui réduit de beaucoup comparé à un niveau complet.

[philip]

Oui, il faut organiser plusieurs zones de jeu, chaque zone gérant ses propres objets interactifs.

[Tryphon]

Je connaissais le blog sur mc kids mais j'ai pas pensé à le consulter. Si j'ai bien compris, il fait deux listes ordonnées, l'une horizontalement, l'autre verticalement.

Je pense que je vais essayer ça. Je pense pouvoir bientôt montrer quelque chose, en Python pour l'instant.

[bfg]

Un tableau d'objet tabObj en rom, trié par toi en x pour l'apparition.

un index qui garde la position dans le tableau : index_obj = 0

structure de ce qu'il y à dans le tableau :

Position x dans la map
Position y dans la map
identifiant de l'objet = index du tableau pour simplifier

Si tabObj[index_obj].x < (position x +largeur) du scrolling Alors
 Existe t'il un objet créer avec l'identifiant index_obj ?
 Non --> Crééer l'objet index_obj en x,y et incrémenter index_obj
 
Quand l'obj sort de l'écran, tu le détruis.

Je met un identifiant à l'objet pour éviter de le recréer si le joueur fait droite/gauche et que le monstre à été créé. Si il est détruit car il est sorti de l'écran, alors il pourra respawner car l'indentifiant n'existera plus.

C'est brouillon ce que je raconte, mais je crois qu'il y à moyen de s'en sortir dans les 2 sens (test inverse pour la gauche + décrémentation). Après c'est ptet aussi de la merde   J'ai pas testé ...

[Tryphon]

Un tableau d'objet tabObj en rom, trié par toi en x pour l'apparition.

un index qui garde la position dans le tableau : index_obj = 0

structure de ce qu'il y à dans le tableau :

Position x dans la map
Position y dans la map
identifiant de l'objet = index du tableau pour simplifier

Si tabObj[index_obj].x < (position x +largeur) du scrolling Alors
 Existe t'il un objet créer avec l'identifiant index_obj ?
 Non --> Crééer l'objet index_obj en x,y et incrémenter index_obj
 
Quand l'obj sort de l'écran, tu le détruis.

Je met un identifiant à l'objet pour éviter de le recréer si le joueur fait droite/gauche et que le monstre à été créé. Si il est détruit car il est sorti de l'écran, alors il pourra respawner car l'indentifiant n'existera plus.

C'est brouillon ce que je raconte, mais je crois qu'il y à moyen de s'en sortir dans les 2 sens (test inverse pour la gauche + décrémentation). Après c'est ptet aussi de la merde   J'ai pas testé ...

Merci pour le retour. C'est à peu près ce que j'ai fait. Les différences principales :

* dans la struct je code à la fois la position que doit avoir la caméra pour que l'ennemi apparaisse, et la position de l'ennemi : ça permet de faire apparaître des ennemis ailleurs qu'au bord de l'écran (les ninjas ont une fâcheuse tendance à apparaître près de toi)

* plutôt qu'un identifiant j'ai mis un flag : True si l'objet est actif, False s'il est inactif. Ça permet de respawner certains ennemis, mais pas d'autres (suffit de laisser leur flag à True quand ils sont morts)

Inconvénient : je suis obligé de copier le tableau en RAM au début du niveau pour pouvoir modifier le flag. Mais c'est pas trop gênant : ça me permet d'empêcher certains ennemis de réapparaître quand on perd une vie (les gros plein de soupe avec leur sabre n'apparaissent plus si on a libéréééé, délivrééé l'otage à côté d'eux).

[Invité]

Inconvénient : je suis obligé de copier le tableau en RAM au début du niveau pour pouvoir modifier le flag. Mais c'est pas trop gênant : ça me permet d'empêcher certains ennemis de réapparaître quand on perd une vie (les gros plein de soupe avec leur sabre n'apparaissent plus si on a libéréééé, délivrééé l'otage à côté d'eux).

Pk ne pas juste garder le flag en RAM au lieu du tableau complet ?

[Tryphon]

Oui c'est vrai, pourquoi pas ?

Mais je me demande : je vais devoir parcourir les deux tables "en parallèle", donc si je veux l'optimiser je vais devoir utiliser deux registres d'adresse, est-ce que ça vaut vraiment le coup ?

[Invité]

Oui c'est vrai, pourquoi pas ?

Mais je me demande : je vais devoir parcourir les deux tables "en parallèle", donc si je veux l'optimiser je vais devoir utiliser deux registres d'adresse, est-ce que ça vaut vraiment le coup ?

Après c'est à voir, mais si par exemple ton flag se résume par juste 1/0, tu peux utiliser un mot de 32 bits pour 32 entrées ..
Après je sais pas ce que vaut le 68k dans les tests de bits, donc faut voir .