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...