Salut !

je reviens avec encore une question de débutant qui en est encore a réfléchir a la conception,

Dans la plupart des jeux, est ce qu'on utilise plutot la logique Discrete :
en gros la map est une matrice de cases qui ne peuvent contenir qu'une unité, chaque entité se situe avec des coordonnées entieres,( ou mieux en inscrivant l'identifiant de l'entité dans la case,)
pour tout les déplacements, on utilise de l'interpolation pour simuler les phases de déplacement entre deux cases


ou alors plutot la logique continue :
chaque entité a deux coordonnées flottantes x et y,
on conserve les entités dans une liste, et on doit effectuer les calculs de collisions/distance en parcourant a chaque fois toute la liste et en recalculant sqrt((x*x)+(y+y))

ou carrement un peu les deux :
des cases qui ne peuvent contenir qu'une unité, mais l'unité peut avoir plusieurs positions dans la case (je pencherai pour ca)
des cases qui  peuvent contenir plusieurs unités et on fait du continu dans la case

les jeux actuels utilisent quelles méthodes ? par exemple si vous deviez faire un warcraft 3 dans lequel on peut facilement voir 300 unités en meme temps


Merci de vos lumieres

Dernière modification par Jerry Kan (25-12-2006 10:45:34)

Hello,

Comme je vois que personne n'a répondu... Faut reconnaitre que la question n'est pas évidente à comprendre, ni a répondre quand on l'a compris.
Bon je vais essayer de faire au mieux.
Je pense que tu fais allusion aux algorithmes de Quadtree.
C'est assez complexe à expliquer, mais je vais essayer de t'expliquer au plus simple :
Immagine une scene 3D complète avec un terrain, des arbres, des humains, des maisons, un petit chemin, des fleurs, des anges, des chiens, des chats, des papillons (comment ça je dérive -> ok j'arrete ).Bon t'a une scene complète quoi !
Bein cette scene tu la quadrille avec un grand grillage de X->10*Z->10 que tu poses à plat.Dans chaques carreaux de se grillage tu en redessine 4 autre plus petits qui seront les enfants de chaques grand carreaux qu'on appelera Parent.

Tu aurras donc 100 Carreaux Parents comme ça :
____
|_|_|
|_|_|

Se qui te fera un total de 400 petits carreaux enfants.

Ensuite il faudra découper ta scene de façon à se que chaques objets se trouve dans son petit carreaux enfants respectif.
Cela te permettra de faire un rendu qui n'affichera et ne calculera que les objets à dessiner.

Cela se calcule en fonction du FOV (Field Of View -> Champ De Vision)de la camera.
On calcule d'abord quels Grand carreaux parents sont visiblent par le champ de vision, et on exclus tout les autres carreaux Parents et leurs enfants.
Une fois qu'on a trié tout les grands carreaux Parents visibles, on recommence avec chaques carreaux enfants des carreaux parents restant afin d'en enlever un maximum.
Une fois qu'on a récupéré tout les carreaux visible, il ne reste plus qu'a afficher les objets contenus dans ses carreaux.

Il existe ensuite d'autre technique comme l'octree sauf qu'au lieu de se Calculer avec X et Z, on va le calculer avec des carreaux 3D en X,Y et Z et c'est biensûr plus complexe à mettre en place.

Voilà j'espère que t'a compris mon explication, si c'est pas le cas n'hésite pas à le dire je verrai alors de faire un petit shéma.
@+

Ah merde d'ailleurs j'ai pas compris, j'ai encore répondu à côté de la plaque je crois.
Tu parlais des déplacements non :s ?
Si c'est des déplacements+collisions que tu parlais, chaque objets sont rangés dans une classe, et on ne calculera les collisions du joueur que lorsqu'il se déplace par exemple.
Pour se qui est des déplacements, chaque joueur fait appel à une autre classe de PathFinding afin de se diriger en un point précis, en s'alignant toujours dans la bonne direction.

en fait j'ai mal posé ma question, (mais ces quadtree m'ont bien interressé, merci pour l'explication )

ce que je veux dire, c'est comment simuler des déplacements fluides sur la scene de rendu tout en continuant a avoir un découpage simple de la map, (du point de vue du codeur du jeu, pas du moteur)

mettons qu'on soit a Warcraft 3, on a un péon qui doit trouver son chemin entre la mine d'or et l'hotel de ville,
on aimerai découper l'espace avec un cadrillage, parce que ca facilite tout (interractions, pathfinding, vision, calcul de distances etc)
mais une fois qu'on a placé tout nos personages sur des cases, comment fait on pour que le joueur n'ai pas l'impression de jouer "a un jeu d'echec" (le perso qui va du milieu d'une case a un autre milieu de cases)

Dernière modification par Jerry Kan (29-12-2006 09:58:55)

lol décidément moi aussi je comprends rien
Je dirais lissage avec courbes de béziers?

izguit :

lol décidément moi aussi je comprends rien
Je dirais lissage avec courbes de béziers?

ca implique qu'on connaisse toutes les positions successives a l'avance, et aussi qu'on sauvegarde les précédentes non ?
et si on reste sur le principe d'une structure de données en cases, on ne peut pas s'arreter "entre deux cases"


la question que je me pose, c'est quelle structure de donnée utiliser pour gerer simplement un grand nombre d'objets rapidement et simplement, tout en gardant un affichage fluide

en bref, dans vos jeux/programmes, quelle structure de données utilisez vous pour stocker les positions

jusqu'ici je vois 4 solutions :

une matrice de cases toute bete, et on interpole autant qu'on veux,
inconvénient: deux interpolations peuvent conduire a placer deux objets au meme endroit, et ca implique de stocker les positions précédentes

une liste des positions des objets (float x, float y) qu'il faut parcourir dans tout les sens a chaque interaction,
inconvénient : temps de calcul exponentiel fonction du nombre d'objets

des cases qui contiennent des listes d'objets, et on fait des parcours uniquement avec les objets de la case, (et ceux des cases adjacentes)
inconvénient : un peu long a coder, interactions compliqués a gerer a l'interieur d'une meme case

des cases qui ne contiennent qu'un objet, lequel peut se déplacer dans la case, jusqu'a ce qu'il change de case
incovénient : mal adapté aux objets non rectangulaires, il y a des zones libres d'une case qui sont inaccessibles aux autres objets tant que la case est occupé

Je pense qu'il y a autant de facons d'aborder ce probleme que de programmeurs et de programmes.
Tu te places dans le cas ou il y a beaucoup d'objets.

donc tu peux:
- soit utiliser la methode de Copland avec des Quad/OcTree (ce qui va etre long et fastidieux a programmer) mais qui est a mon avis la plus elegante (mais je ne l'ai encore jamais utilisee pour faire un jeu) car elle va te permettre de customiser toutes les interactions et de ne stocker que ce dont tu as besoin.

(je prefere cette deuxieme solution qui est la plus rapide a mettre en oeuvre)- soit d'utiliser une simple matrice de liste d'objets. Tu stockes donc dans chaque case de ta matrice l'ensemble des objets qui s'y trouvent. Avec une methode de "trace ligne discrete", tu obtiens l'ensemble des cases que tu vas intersecter. Ainsi, tu obtiens rapidement un sous ensemble des objets qui se trouvent sur tes cases, il ne te reste plus qu'a savoir si la boite englobante de ton personnage passe entre la liste des objets stockes qui se trouvent sur ton chemin.

un petit exemple peut aider:
- Tu as une matrice de listes (qui correspond a ton monde).
- Tu as un ensemble d'objets qui ont une position (x,y,z) et une forme (generalement, un pave ou une spere)
- Stockes ces objets dans les cases qui correspondent le mieux a leur position (quel niveau d'approximation te suffit).
(petite disgression: tu peux stocker plusieur fois le meme objet dans des cases differentes si leur volume est important)
- Tu as ton personnage (qui est aussi un objet 3d avec une forme)
- Tu fais un petit moteur de choc qui calcul l'intersection entre les differentes formes que tu utilises.
- A chaque deplacement, tu recuperes l'ensemble des objets sur ton chemin (sans te poser la question de la hauteur au debut) et tu appelles ton moteur de collision sur chacun des objets pour savoir si tu as percute un objet.

Maintenant, c'est vrai qu'avec un exemple concret, ce serait plus facile de repondre a ta question...

Bonne chance pour la suite.

WT

merci pour la réponse, ca me donne a réfléchir,

en fait pour un exemple, c'est plutot difficile, actuellement je suis sur un petit jeu de simulation d'évolutions de fourmis, assez basique, (c'est pour un projet scolaire) et si elles doivent etre tres nombreuses, il n'est pas vraiment nécessaire que la structure soit parfaite, et j'ai choisit l'option de la matrice de cases avec une seule fourmi par case, plus simple et rapide a coder,
(les graphismes sont ok, reste justement a paufiner les interactions, et justement, j'ai réalisé que je ne saurais pas bien m'y prendre si tout aurait du etre parfait)

de facon générale, je m'interresse plus aux jeux dans lesquel on voit un grand nombre d'élements en interactions, j'ai encore du mal a voir comment marche et s'organise l'architecture d'un jeu, donc toutes les infos sont bonnes pour moi

Jerry Kan :

mais une fois qu'on a placé tout nos personnages sur des cases, comment fait on pour que le joueur n'ai pas l'impression de jouer "a un jeu d'échec" (le perso qui va du milieu d'une case a un autre milieu de cases)

Dans pas mal de jeux, on met en place un ensemble de waypoints, de points de passage quoi.

Pour que les déplacements des joueurs ou des bots paraissent moins "robotisés", on peut mettre plusieurs chemins de waypoints et laisser emprunter aléatoirement le chemin n°1, 2 ou 3.

Il faut également donner au personnage l'intelligence de se décaler sur le côté afin d'éviter une collision avec un autre objet ou perso avant de reprendre sa "quête" vers le prochain waypoint.

Cette méthode peut faire des choses sympathiques, imagine ton exemple avec les fourmis :

Un terrier A, un terrier B. Entre ces deux terriers, tu as placé suffisamment de waypoint pour qu'il y ait plusieurs chemins empruntables par les fourmis. Les plus rapides devront à certainement moment se décaler du chemin afin d'éviter certains de leurs congénères. A la fin de ce décalage, elles devront localiser le waypoint le plus proche d'elles qui leur permettra de se remettre sur le chemin qui les mènera au terrier souhaité. 

Pour faire tout cela, il est conseillé d'utiliser (ou de concevoir ^^) un éditeur de niveau ; cela permet de placer de manière graphique ces fameux waypoints et de visualiser ainsi aisément les différents chemins empruntables par les personnages.

Il existe bien d'autres techniques mais celle-ci permet d'éviter de concevoir une usine à gaz...

voila je vais me répondre a moi meme ayant finalement trouvé ma réponse :

une matrice de 1000*1000 avec des mesh qui occupent graphiquement 50x50 cases et se déplacent de une ou plusieurs cases par "tour" suffit largement a donner une impression de fluidité, a tel point qu'on ne peut pas dire que les Mesh ont un déplacement saccadé

au niveau de la structure de donnée, une grosse matrice donc, avec un élément par case, éventuellement on peut gérer les collisions en ne permettant pas a deux éléments de trop s'approcher

c'est pratique et ca se développe vite, ca permet de résoudre rapidement les problèmes de visions (on récupere les cases autour de l'objet)

voila c'est un peu idiot comme réponse (ma question l'est aussi un peu)

donc en bref tout dépends de la taille des mesh et des cases et la fluidité apparait