Tom's Guide > Forum > Programmation > Algo colision

Algo colision

Forum Programmation : Algo colision

TomsGuide.com : 800 000 inscrits répondent à toutes vos questions high-tech et informatique. Pour obtenir de l'aide, inscrivez-vous gratuitement !

Créer un nouveau sujet Répondre

Bas de page Chercher dans ce sujet

Salut

Je suis actuelement en train de faire un programme en Lua qui à besoin d'un algo de colision : il s'agit de comparer toutes les coords de tous les cercles entre eux poour savoir si ils sont sécants.
Actuelement l'algo que j'utilise est basé sur une itération for (et pas de rires s'il vous plait) terme général du nombre d'incréments n²-n, ce qui est assez lent vous en conviendrez.
Il me faut donc l'algo le plus rapide qu'on connais pour itérer une table n*n.

Merci pour vos réponses
PS : Lua utilise les fonction, les objets, les listes chainées et les fonctions récursives.
Je maîtrise la plupart de ces concepts....

Répondre

Inscrivez-vous ou connectez-vous pour masquer ceci.

Peut-être en découpant l'espace en zones ?
Si 2 cercles ne sont pas dans la même zone ou dans 2 zones adjacentes, inutile de faire le test de collision.
Après il faut voir comment découper les zones (pas trop petites et pas trop grandes).

Répondre à CRicky

Les cercles nont pas tous le meme rad :-?

Répondre à Tcherno_bill

C'est pas un problème , il faut que que les zones soient évidemment plus grandes que les diamètres des cercles.
Ce que je vux dire, c'est que si tu découpe ton espace en 9 cases, si tu as un cercle dans la case en haut à gauche, même s'il empiète un peu sur une autre case, tu ne vas pas effectuer le test de collision avec les cercles situées dans la case en bas à droite par exemple, car tu es sûr que ces cercles-ci ne se toucheront pas.

Répondre à CRicky

mwé ça peut se faire, mais ça renouvelle le problème, chaque cercle devra appartenir à une box plus grand que lui et il faudra TOUT DE MEME effectuer les test de collision pour tous les tests.

Bon j'ai plus ou mois resulu le problème :
j'utilise au sein de l'objet cercle un méthode permettant l'acces aux autres cercles par liste chainée.

Répondre à Tcherno_bill

Simple curiosité, c'est quoi ton programme ? (je veux dire, à quoi il sert ?)

Dites-moi ... : http://www.infos-du-net.com/forum/ [...] 21#1483260

Répondre à mexson

Tres simple, juste pour m'amuser en cours d'histoire.
Il s'agit d'afficher un nombre n de cercles, de rayons différents et de les annimer avec des vecteurs vitesse différent (tout ça se passe dans le plan).
Il s'agit également de faire en sorte que les cercles rebondissent sur les parois et sur eux mêmes
Il faut donc effectuer des tests de colision pour savoir s'ils sont sécants, si tel est le cas, on échange leurs vecteurs dirécteurs.

Répondre à Tcherno_bill

Citation :

Tcherno_bill a écrit :
mwé ça peut se faire, mais ça renouvelle le problème, chaque cercle devra appartenir à une box plus grand que lui et il faudra TOUT DE MEME effectuer les test de collision pour tous les tests.

je pense pas.
Je suppose que tes cercles se déplacent dans un découpage de k * k zones. Donc à chaque déplacement tu mets à jour ta table de zones dont chacune contient la liste des cercles de la zone.
A chaque mouvement tu testes si le cercle change de zone, tu as donc 4*n tests rapide à effectuer. On peut considérer que c'est n car les calculs sont plus simples que pour faire la collision entre cercles, mais je vais quand même continuer avec 4n.
Ensuite, pour tes tests de collisions, tu ne fais les tests que pour les 9 zones entourant la zone du cercle à tester. Donc, en moyenne, tu ne testeras que (9 * (n - 1))/(k*k) car la probabilité de placer un cercle dans cette zone est le rapport des surface 9 / (k*k).
(je compte pas le cas particulier des bords qui ont moins de 9 tests)
Ce test, tu le fais pour tous les cercles, donc le nombre moyen de tests est multiplié par n, soit 9n(n - 1)/(k²)

Donc au final, pour chaque déplacement, le nombre de tests moyen sera de:
A = 4n + 9n(n - 1)/(k²)
D'un point de vue complexité, toi tu avais n(n -1) = O(n²) mais aussi n(n-1) = o(n²)
Moi, j'ai A = o(n²), mais A = O(9n²/(k²))

Donc, on a tous les 2 o(n²). Donc si n est grand, on aura toujours un facteur de n² (complexité croissante au carré du nombre de cercle).
Mais moi, j'ai un facteur de 9/(k²), donc le rapport de temps ne sera pas grandissant lorsque n devient grand, mais plus on aura de zones, plus le rapport sera petit.

On pourrait naïvement dire de choisir k de l'ordre de n comme ça, on aurait A ~ 4n + 9n(n - 1)/(n²) = O(4n) ou o(n) !!!
Ce qui reviendrait à faire essentiellement des tests de zones car sil l'on a plein de zones, on ne fera, en moyenne, pas beaucoup de test de collision.
Imagine une grande zone avec de tout petits cercles et beaucoup de zones, les tests de cercles seront très rares (mais pas nuls évidemment) car les cercles seront éparpillés (ou finiront par l'être). Bon là c'est le cas extrême, mais c'est en voyant ça qu'on comprend qu'on peut optimiser.

Ceci dit, j'ai dit naïf, car j'ai supposé que les tests se limitaient aux 8 cases qui entourent la zone (+ la zone courante). Il faut donc que la taille de la zone soit au moins supérieure au diamètre du plus grand cercle.
Donc, pour optimiser le tout, je prendrais k = largeur de zone / diamètre du plus grand cercle
Et donc pour que ça marche il faut que la taille du plus gros cercle soit bien inférieur à 1/3 de la largeur de la zone pour faire suffisamment de zones.

si tu ne comprends pas certaines choses n'hésite pas à me demander, et si je me suis trompé, n'hésite pas à me rectifier ;-)

Répondre à CRicky

J'ai parfaitement compris comment cu compte procéder.
Le problème est le suivant : on devra bien comparer grâce à la grille pou savoir si les cercles ont une proba de colision mais tu oublies (ou alors g mal lu) qu'il faudra itérer la table de grille et stocker les resultats dans une table qu'il faudra aussi itérer de mon point de vue, je suis pas sûr que le jeu en vaille la chandelle, d'autant qu'il faudra rajouter au Stack (en Lua c'est l'espace mémoir courant par opposition au Garbage) des threads qui ralentiront l'allure générale du prog :x

Je vais faire un bref resumé de ce que j'ai codé jusqu'ici (attention Lua = language de haut niveau)

-- Methodes utilisés par les objets, ici les cercles

diverses méthodes comme le déplacement

col_circle = function ( self )
-- self est l'equivalent de this en Cpp
local l = self.pre
while l do
if test_col ( self.x , self.y, self.r, l.x, l.y, l.r ) then
-- echange vecteurs dirs
self.v[1], l.v[1] = l.v[1], self.v[1]
self.v[2], l.v[2] = l.v[2], self.v[2]
break
-- je sais ça se fait pas
end
-- on prend l'objet precedent et on recommencer jusqu'au début
l = l.pre
end

-- objets
cercles = {}
add_circle = coroutine.resume (
function ()
i = 1
repeat
cercles[i] = {
x = random ( 16, 143 ),
y = random ( 16, 204 ),
r = random ( 5, 15 ),
v = { random(), random() }
les diverses méthodes
cercles.col = col_circle
cercles.pre = cercles[i-1]
-- ici pas de pb si il il sagit du premier objet car on store alors Nil
}
i = i+1
coroutine.yeild()
until false
-- en lua c'est autorisé dans le cadre des coroutines
end )

Répondre à Tcherno_bill

Non, je compte pas itérer sur la grille des zones.
C'est vrai que j'ai pas trop décrit l'algo: j'itère simplement sur les cercles.

Sur le cercle courant de centre (x,y), je trouve la zone de la grille correspondante sur un tableau TAB[X = x * largeur d'une zone / largeur totale, Y = y * hauteur d'une zone / zone totale].
Une fois la position trouvée sur la grille, chaque case de TAB pointe sur la liste des cercle qu'il contient. On boucle sur les cercles des listes pointée par les cases TAB[X - 1, Y - 1], TAB[X, Y - 1], TAB[X + 1, Y - 1], TAB[X - 1, Y], TAB[X, Y], TAB[X + 1, Y], TAB[X - 1, Y + 1], TAB[X, Y + 1], TAB[X + 1, Y + 1]

On effectue les tests uniquement sur ces listes.

Ensuite, lorsque l'on fait déplacer les cercles, pour chaque cercle, on met à jour la zone si besoin, c'est-à-dire que si le cercle avant déplacement est sur TAB[X = x * largeur d'une zone / largeur totale, Y = y * hauteur d'une zone / zone totale] et qu'après il est sur TAB[X2 = x2 * largeur d'une zone / largeur totale, Y2 = y2 * hauteur d'une zone / zone totale]. Si X est différent de X2 ou Y différent de Y2, alors on retire le cercle courant de TAB[X,Y] pour le mettre dans TAB[X2, Y2]

D'ailleurs, une petite remarque: le temps doit être suffisamment précis (mais c'est pas un problème) pour que le cercle ne saute pas une zone, car sinon on a oublié des test de collisions.

Bref, tout ça pour dire que je n'itère jamais sur les zones, seulement sur les cercles. Donc à ta place j'utiliserais 2 chainages:
- 1 pour la liste de tous les cercles (pour itérer dessus
- 1 pour les listes dans le tableau TAB

Voilà, sinon tu pourrais chercher un autre truc en gardant ton algo sur le tri de la liste de tes cercle par rapport à leur distance. Ceci pour essayer d'arrêter la boucle lorsque 2 cercles ne sont pas en collisions. Le problème c'est le tri et la mise à jour de la liste, mais là ça peut devenir très compliqué si l'on veut bien optimiser, alors j'y réfléchis même pas :-D

Répondre à CRicky

puisque le problème à l'air de te passionner, je te fournis même le code
valable sur classpad 300 (fait en cours d'Histoire)

Code :

require("draw" )
--require("table" )
showgraph()
keypad(0)
fullscreen(0)
draw.onbuffer(1)
nombre_cercle = 4
max_cercles = 4
vitesse_cercle = 3
-- fonctions
function col_test ( c1x, c1y, c1r, c2x, c2y, c2r )
if ( ((c1x-c2x)^2)+((c1y-c2y)^2) <= ((c1r+c2r)^2) ) then
return true
end
return false
end
-- methodes
mov_circle = function ( self )
self.x = self.x + self.v[1]
self.y = self.y + self.v[2]
end
aff_circle = function ( self )
draw.circle ( self.x, self.y, self.r )
end
ver_circle = function ( self )
if ( self.x >= 158-self.r ) or ( self.x <= 1+self.r )then
self.v[1] = -self.v[1]
end
if ( self.y >= 210-self.r ) or ( self.y <= 1+self.r ) then
self.v[2] = -self.v[2]
end
end
col_circle = function ( self )
l = self.pre
while l do
if col_test ( self.x, self.y, self.r, l.x, l.y, l.r ) then
self.v[1], l.v[1] = l.v[1], self.v[1]
self.v[2], l.v[2] = l.v[2], self.v[2]
break
end
l = l.pre
end
end
-- coroutines
add_circle = coroutine.create ( function ()
local i = 1
repeat
cercles[i] = {
r = math.random( 5, 15 ),
x = math.random( 16, 143 ),
y = math.random( 16, 104 ),
v = {
vitesse_cercle *math.random(),
vitesse_cercle *math.random()
}
}
cercles[i].pre = cercles[i-1]
cercles[i].mov = mov_circle
cercles[i].aff = aff_circle
cercles[i].ver = ver_circle
cercles[i].col = col_circle
i = i+1
if i>max_cercles then i = 1 end
coroutine.yield()
until false
end )
-- objets
cercles = {}
for i=1, nombre_cercle do
coroutine.resume ( add_circle )
end
-- Kernel
repeat
draw.clear()
for i in pairs ( cercles ) do
cercles[i].aff ( cercles[i] )
cercles[i].mov ( cercles[i] )
cercles[i].ver ( cercles[i] )
cercles[i].col ( cercles[i] )
end
if testkey(K_PLUS) then
coroutine.resume ( add_circle )
end
draw.update()
until testkey(K_EXE)

Répondre à Tcherno_bill

Pour moi, un algo ne se réfléchit pas avec du code ;-)

En plus, avec ton code, je dois déchiffer et réfléchir à chaque ligne pour comprendre parce qu'il n'y a pas de commentaire, alors je ne lis même pas.

Répondre à CRicky

lol y'a pas 50 lingnes
bah ct juste pour faire le malin comme d'hab, j'illustre mes propos en somme...

Pour résumer, je créé séparément les objets et les fonctions qui les régissent (pas de calembourg avec le prénom) je créé un nombre fini d'objet mais non constant et j'utilise les méthodes pour les agencer

voila voila
à tout hasard tu sais pas ou je peu trouver un manuel Lua en FR ?

Répondre à Tcherno_bill

Créer un nouveau sujet Répondre

Tom's Guide > Forum > Programmation > Algo colision

Aller à :

Aide |
Règles du forum

Il y a 2256 utilisateurs connus et inconnus. Pour voir la liste des connectés connus, cliquez ici.

Page générée en 0,450 secondes

Attention

Vous allez répondre sur un sujet resté inactif pendant plus de 6 mois.
Assurez-vous d'apporter des éléments nouveaux à la discussion avant de poursuivre.

Répondre Annuler

Liens