Bonjour
 
Je programme en ce moment un jeu de stratégie (genre total annihilation simplifié) et je bloque sur la détection des collisions.
Je cherche un moyen rapide de connaitre pour chaque unité:
   Les cases de la carte qui sont "sous" l'unité.
   Les unités qui la touchent.
   S'il y a collision avec un ou des projectiles
 
Mes unités sont facilement assimilables à des pavés de taille varibale définis grâce aux attributs de la classe Unite (position, taille X, taille Y, taille Z)
La carte est simplement un tableau nombres qui correspondent à des cases (carrées) et dont la valeur indique les propriétés de la casse (terre,  mer, rochers,...).
 
Le problème étant évidemment de trouver un (des) algo qui soi(en)t rapide(s) car le nombre d'unités va toujours croissant au cours du jeu.

des pavés... qui ont une orientation je supose ? Sinon c'est beaucoup plus facile...
A vrai dire, les deux detections de collisions les plus faciles à calculer sont surement la collision point-polygone(plan) et  sphere-sphere ou polygone.
Pour ce qui est de savoir sur quelle case ils sont... tu peux pas utiliser leurs coordonées pour le récuperer facilement ? si la coord d'une unité est 12.254 , 65.35 alors la case sera 12,65 non ?

Bonjour,
Une autre méthode qui nécessite aucun calcul mais qui nécessite un peu de mémoire (donc à voir si intéressant selon la taille de ta map).
 
Tu stockes dans un tableau de type (entier, entier, booléen) l'ensemble des points de ta map. les deux premiers éléments représentent les coordonnées des points et le booléen si la case est occupée ou non.
 
A bientot.
 
 

Cette methode est un peu dépassée dans le sens ou elle nessesite qu'une seule unité soit sur une seule case en meme temps... ce qui implique qu'il est impossible par exemple de placer un régiment en diagonale ou autre... avec cette methode, tout parait tres...carré, rangé, et très peu pratique à manier
Ceci dit, c'est vrai que c'est surement la methode la plus optimisée... mais avec les procc d'aujourdhui, c'est dommage

Salut,
 
A la place d'un booléen, tu peux mettre une liste:
- d'id d'unités
- les pointeurs vers les unités

Ouais sauf qu'apparement il cherche l'inverse... pour chaque unité il veut les cases qui se trouve dessous.  
 
Dans ce cas, il faut calculer les cases se trouvant sous les 4 coins de ton unité (en supposant que tu prenne une base carrée pour l'espace occupé par tes unités, donc la c'est simple style t'as une mini mini carte de 4x4 avec des cases de 40 pixels a l'écran, si un coin se trouve en 60,60 il se trouve sur la case 2,2 (en numérotant à partir de 1), et hop on refait la même chose pour les 3 autres coins) et après extrapoler... par contre j'ai pas d'idée comme ça pour un algo d'extrapolation efficace.

Oui, désolé :$
 
Tout dépend de l'organisation mise en place, mais des unités liées au terrain par une liste de pointeurs vers tiles (dans les unités) et inversement éviterai de se poser la question non?
Sans compter que ça facilite la prise en compte du terrain s'il entraîne une modification des facteurs d'attaque/défense.

Merci pour vos réponses
 
J'ai oublié de préciser pas mal de choses:
j'utilise OpenGL avec la SDL pour les graphismes et la gestion du clavier et de la souris.
mes cases sont petites pour que le terrain soit moins moche donc la carte est grande et une unité occupe beaucoup de cases.
je cherche une solution plutôt rapide, quitte à consommer de la mémoire car l'affichage 3D prend du temps.
Lier les unités aux cases faciliterait beaucoup le calcul des collisions entre unités mais à chaque tour il faudrait calculer les cases occupées pour chaque unité selon son vecteur vitesse,sa position et ses dimensions. Ne permettre qu'une unité par case donnerait un resultat type warcraft 2 où on a l'impression de voir la grille.
 
Je pense que je vais tenter plusieurs solutions pour voir les résultats...
 

pour savoir sur quelle case le perso est, ce que je ferais:  
on prend les positions X et Y du perso, tu les divise par D et tu les remultiplie par D.  
D= largeur des cases de ta grille
 
tu obtiens le N° de la case où se situe verticalement et horizontalement ton perso
 
 
ensuite pour les collisions je ferais un truc qui calcule la distance entre les 2 objets où il faut tester la collision. le repère est pris au centre du sprite. ensuite vu que tu connais la taille de chaque sprite tu peux déterminer précisément si l'objet sera en collision ou non.
 
 
(note: je fais pas du c++, je fais de la programmation évenementielle, je sais pas comment coder tout ça...)

Le souci comme je l'ai dit c'est qu'une unité occupe plusieurs cases, pas forcément entière, l'unité n'est pas toujours un carré de la bonne taille, vertical et tt et tt.
 
Je possède déjà des méthodes qui me donne la case en fonction des coordonnées d'un point mais ce qu'il me faudrait c'est un moyen de ne vérifier que les cases nécessaires ou quelque chose comme ca parce que recalculer à chaque tour toutes les cases pour toutes les unités en mouvement (ma seule unité déjà créée occupe environ  4*2 cases et c'est une petite) ça risque d'être très long si on imagine 4 joueurs possédant chacun 100 unités (voir +).
Après, peut-etre que ces calculs st indispensables... dans ce cas, je vais continuer à optimiser la partie graphique. D'ailleurs je vais aussi avoir besoin de conseils pour ça mais je ne sais pas si je dois en parler ici ou créer un autre sujet.

Pour les collisions entre unités, j'avais pensé à créer des cases virtuelles, grandes, qui possèderaient la liste de toutes les unités présentes dessus comme ça pour les collisions entre elles, il ne suffit de vérifier que les autres de la case. Par contre, j'ai toujours le même souci des unités qui débordent mais dans ce cas, une unité ne fait partie que de 4 cases maximum. Après il si je fais ça, je vais devoir trouver le compromis entre des cases assez grandes pour contenir la plus grosse unité facilement mais assez petite pour minimiser les recherche d'unités.

ça dépends comment tu gère le débordement d'un case a l'autre.
il faut que tu trouves une astuce pour cela.

Je pense qu'il faut plus ou moins "abandonner" l'idée de mettre une unité par case... à part pour le placement des batiments, je pense que ce principe n'a pas été utilisé depuis un bout de temps, pour des raisons de déplacement en diagonale...
cependant, tu dois pouvoir l'améliorer... je m'explique : ton jeu est en 3D, ce qui complique les recherches de collisions ! cependant, ton problème est plan... je pense que pour chaque unité, tu devrais en plus du modele 3D lui assigner une forme plane, une sorte de "vue de haut" très grossiere de la forme de ton unité (un genre de tableau de booléens ou TRUE équivaut à une partie solide, et FALSE à du vide)... ensuite, reste plus qu'à créer une matrice de ta map, ou tu places chaque vue de haut de chaque unité...sauf quand il y a superposition ! (auquel cas tu gères la collision en fonction)
 
Dis moi si ma solution ne te parait pas claire

En fait ca revient à ramener ton jeu de la 3D à la 2D, ou les collisions sont beaucoup plus simples à gérer (cf les collision de sprites 2D)

bin ouais, mais 99% des moteurs de terrain sont des moteurs de terrain parceque c'est du 2D avec élévation ce qui simplifie les requetes de collision avec le terrain.
 
créer un système d'occupation par secteur a toujours existé.

Et ? ca contredit pas vraiment mon post non ?
Ce que je voulais dire, c'est qu'il ne falait pas associer 1 case avec 1 unité, mais plusieurs cases avec une unité... Les unités n'ont pas à se restreindre à la grille pour se déplacer.question de fluidité des mouvements ! Le principe est pas nouveau non plus mdr...

à vrai dire, j'ai déjà associé une forme plane très grossière pour mes unités: le plus petit rectangle la contenant, je pense que c'est assez précis pour la qualité du jeu que je veux créer. Ok je pense que je vais gérer mes collisions en 2D et si besoin je contrôlerais l'altitude en cas d'avion ou de projectile.

t'a pas besoin de collisions en 2D, t'as besoin d'une technique de hiérarchisation(oulà ) genre octree pour dégrossir les collisions.
 
ça sert uniquement a determiner le lot minimal d'objets potentiellement en collision.
une fois que tu as ce lot tu peux parfaitement remonter vers une collision 3D et faire des intersections triangles/triangles et même implémenter un moteur physique pour que la tourelle d'un tank qui se fait sécher vole dans la bonne direction.

et t'aurais des liens vers des pages qui m'expliqueraient ce que tu dis? ça à l'air interessant.

Sur alrj.org y'a pas mal de tutos dans ce genre, genre octree

Tout dépend du résultat attendu, mais je pense pas qu'il soit nessesaire de monter un systeme avec octree et detection de collision polygonale pour un petit projet... Et quoi qu'on en dise, la performance des octree n'est plus à prouver, mais c'est surtout efficace pour des detections de collision 3D, alors qu'ici, le problème est simplifié, étant donné que les unités sont (a priori) toutes sur le meme plan   (ou presque...en tous cas elles ne peuvent pas se superposer! )
Je pense donc qu'un octree sera superflu, et qu'une detection 2D sera plus performante ! et surtout beaucoup plus simple à coder
 
Apres, à ptitchep de voir ce qu'il cherche exactement

D'ailleurs le tuto d'alrj sur les octree est signé chrisbk

qui estce ?

un regretté forumeur de talent.

merci, je vais aller y faire un tour
Mes unités ne se superposeront pas tant que je n'aurais pas créé d'avions, mais c'est prévu dès que le jeu tourne avec des unités terrestres.

chrisbk: j'en ai dejà entendu parler. Sur ce forum?

http://forum.hardware.fr/hardwaref [...] 0732-1.htm