Discussion :

[guitz]

Bonjour,

J'essaie de simuler un traffic routier, donc potentiellement un très grand nombre de véhicules, et j'en suis à gérer la priorité à droite.



V1 va vers le haut ,et V2 va vers le bas. V2 est donc prioritaire sur V1.

Notez que pour tout V1 de l'intersection j'ai déjà implémenté un tableau de véhicules V2 (ayant potentiellement la priorité à droite).

Mon algo de detection de proximité de V2 est le suivant : si l'un des deux points rouge est à l'intérieur du rectangle jaune (rectangle aligné sur le repère cartésien, permet d'exclure des véhicules V2 candidats à très faible coût algorithmique) alors on verifie si ce dernier est dans le rectangle vert (enveloppe convexe de V2), si oui, alors on réduit la vitesse de V1

Est il possible svp d'optimiser d'avantage cet algorithme ?

Merci

[Guesset]

Bonjour,

N'ayant qu'une vision partielle, il est difficile de juger l'algorithme global.

Cependant la vérification de l'appartenance du point rouge au rectangle vert peut se faire de différentes manières.

La première consiste à mesurer les distances aux cotés. En s'y prenant bien, on peut se limiter à deux "distances" au lieu de 4 (distances signés au centre du rectangle vert) mais cela fait quelques multiplications (4). Pour éviter d'avoir d'autres opérations coûteuses, on travaillera sur des segments unitaires (cos, sin) afin d'éviter d'avoir un module à calculer et une division. Comme les segments sont orthogonaux, l'un se réduit de l'autre. On travaillera en séquence pour pouvoir exclure certains cas sans avoir à calculer la deuxième projection (gain assez faible mais non négligeable).

On pourrait aussi faire tourner le point rouge autour du centre commun des deux rectangles pour se placer dans le repère propre au rectangle vert. Cela simplifierait la comparaison mais la rotation demande également 4 multiplications.

Salutations

[dourouc05]

Les jeux similaires ont-ils déjà résolu le problème ? Je ne pense pas que Cities Skylines (1 et 2) ou Transport Fever (1 et 2) le gèrent : tu as des cédez le passage, des priorités de rond-point ou des feux de signalisation (comme en Amérique du Nord), mais pas vraiment de priorité à droite ou à gauche comme on la connaît en Europe. Je me suis toujours dit que c'était parce que c'était difficile à implémenter efficacement...

[guitz]

Merci encore les amis

[Mat.M]

il y a très simple :calculer la distance entre un véhicule A et un véhicule B.
Ensuite si la distance est inférieure à un certain seuil mettons 10 unités 3d , si le véhicule B a un cap et par conséquent une trajectoire selon cet angle compris entre 0 et 180degrés alors il vient de la droite et il y a risque de collision.

[anapurna]

bonjour

intuitivement j'aurais mis les vehicule dans un cercle circonscrit à la taille du vehicule
selon la distance ou se trouve les vehicules les uns des autres, leurs vitesses et le cadrans dans lequels le contact se ferait
cela devrais pouvoir determiner qui aura la priorité

[mach1974]

Autour de chaque véhicule , il faut calculer une sphère et calculer le prolongement de la trajectoire Bref un problème de trains qui se croisent...

[Guesset]

Bonjour,

Globalement, il semble qu'utiliser un rectangle englobant soit une bonne approche pour diminuer le nombre de calculs en une phase simple et fortement discriminante ne gardant que quelques calculs plus complexes.

Ce qui me gène est que c'est une approche de position non dynamique. Par exemple, deux véhicules peuvent chacun tourner à droite et donc ne pas se gêner en occupant des positions qui seraient inacceptables s'ils allaient tout droit.

Je pense qu'il serait peut être plus efficace d'utiliser les vecteurs vitesses pour calculer l'intersection éventuelle mais de discriminer au préalable avec un calcul de distance Manhattan (D = |dx| + |dy|) assez simple.

Salutations

[guitz]

Guesset je suppose que tu préconises la distance de Manhattan pour éviter à tout prix la norme euclidienne qui utilise la racine carrée bien trop couteuse ?

[Guesset]

Bonjour guitz,

...je suppose que tu préconises la distance de Manhattan pour éviter à tout prix la norme euclidienne qui utilise la racine carrée bien trop couteuse ?

Oui, au moins comme discriminant premier quitte à faire des calculs plus lourds pour ceux qui passent ce premier test. Deux valeurs absolues au lieu de deux multiplications, il n'y a pas photo.

La racine carrée est rarement nécessaire pour la comparaison de distances donc je ne la compte pas ici dans les gains.

Salut

[anapurna]

salut

on est bien d'accord que pour detecter une collision un simple test sur les bouding box devrais suffir ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Function DetectCollision(Rv1,Rv2 : Trect) : Boolean;
Begin 
  if ((Rv1.x < Rv2.x + Rv2.w) and (Rv1.y < Rv2.y + Rv2.h) and
      (Rv1.x + Rv1.w > Rv2.x) and (Rv1.y + Rv1.h > Rv2.y) )  Then  // Collision detected!
    Result := True
  else   // No collision
     Result :=  False;
End;

une fois ce risque detecté si j'ai bien compris tu veux determiner qui à la priorité

en faite le vehicule le plus a gauche n'as pas la priorité
sauf si l'autre Vehicule a un stop,un ceder le passage ou un feu tricolor au rouge
Par contre si la moitier de son vehicule est deja engagé celui-ci devient prioritaire

[guitz]

Merci encore à tous pour vos réponses, je vous fait un retour sous peu