IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Simulation de traffic routier avec priorité à droite


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    723
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 723
    Points : 745
    Points
    745
    Par défaut Simulation de traffic routier avec priorité à droite
    Bonjour,

    J'essaie de simuler un traffic routier avec potentiellement de très nombreux véhicules (max 10k). L'optimisation est donc primordiale.

    Soit G un graphe orienté dont chaque sommet S[i] est "matérialisé" par une spline Sp[i]. Sur la seconde image, les points vert représentent les sommets de G.

    Nom : fofo2.jpg
Affichages : 132
Taille : 178,5 Ko

    Si deux voitures V1 et V2 sont sur la même spline qui est située sur une route, alors je pensais détecter le chevauchement de 2 rectangle, le jaune étant celui de V1 et l'orange celui de V2. Si chevauchement, V1 décélère, et on évite la collision
    A noter que ces rectangles sont alignés sur le repère orthonormé (0, x, y) quelle que soit l'orientation de la voiture (rectangles mis à jour à chaque frame évidement), donc alorigthme extrêmemen peu couteux.

    Est-ce le plus optimal ?


    Nom : fofo3.jpg
Affichages : 128
Taille : 68,5 Ko

    Concernant les intersections, je souhaite n'appliquer que la priorité à droite. Ne souhaitant pas réinventer la roue, connaissez vous svp un algorithme bien optimisé adapté ?

    Merci

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 085
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 085
    Points : 9 457
    Points
    9 457
    Par défaut
    Cette histoire de rectangles qui se chevauchent présentent quelques inconvénients :
    1) je pense que tu parles de carrés, et pas de rectangles, sinon une portion horizontale (parallèle à l'axe des x) donnera des distances très différentes d'une portion 'verticale'.
    2) si la route est 'horizontale' ou 'verticale' (c.a.d. parallèle à l'un des axes du plan), les rectangles vont se chevaucher très tard, quand dist (V1,V2) < L (L est le coté du carré), contre L* racine(2) dans le cas extrême opposé.
    3) calculer si 2 rectangles se chevauchent, ça a un coût , peut-être plus important que calculer tout simplement la distance entre les 2 centres des véhicules.

    Pourquoi ne pas simplement calculer la distance euclidienne ( x1-x2)²+(y1-y2)² et vérifier si cette distance est inférieure à un certain seuil. Je prends le carré de la distance, et pas la distance elle-même, pour optimisation. En plus, cette méthode permet de doser. Si la distance est inférieure à un seuil 1, le véhicule qui est derrière ralentit un peu; et si cette distance est inférieure à un autre seuil, il ralentit beaucoup.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    723
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 723
    Points : 745
    Points
    745
    Par défaut
    Merci beaucoup, oui effectivement je parlais de carrés.

    N'est-ce pas plus optimisé la détection de chevauchement de deux carrés alignés sur les axes du repère cartésien, plutôt que la distance euclidienne (sans la racine carrée) ?

    La fonction ci-dessous m'a l'air extrêmement peu couteuse

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    bool UMyMaths::AlignedAxisRectanglesAreOverlapping(TArray<FVector> Rectangle1, TArray<FVector> Rectangle2) { //Teste collision entre 2 rectangles alignés sur le repère cartésien
     
     
    	FVector l1, r1, l2, r2;
     
    	if (Rectangle1.Num() == 0 || Rectangle2.Num() == 0){
    		UE_LOG(LogTemp, Warning, TEXT("Le tableau de vecteurs Rectangle1 ou Rectangle2 est vide dans la fonction AlignedAxisRectanglesAreOverlapping() dans MyMaths.cpp"));
    		return false;
    	}
     
    	l1 = Rectangle1[0];
    	r1 = Rectangle1[2];
    	l2 = Rectangle2[0];
    	r2 = Rectangle2[2];
     
     
    	// If one rectangle is on the side of other
    	if (l1.X > r2.X || l2.X > r1.X)
    		return false;
     
    	// If one rectangle is above other
    	if (l1.Y > r2.Y || l2.Y > r1.Y)
    		return false;
     
    	return true;
    }

  4. #4
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 394
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 394
    Points : 4 363
    Points
    4 363
    Par défaut
    Bonjour,

    Je pense qu'on ne peut éviter le sens de progression (où les tronçons de splines - apparemment orientés - à emprunter en se limitant, pour chacun, aux véhicules sur ce spline et sur les prédécesseurs immédiats et les successeurs immédiats).

    La seule distance ne peut suffire : deux véhicules qui se croisent peuvent être très proches l'un de l'autre, plus proches sans danger que s'ils se suivent (la plupart des véhicules sont plus longs que larges ).

    S'ils se baladent sur des splines, on a donc des positions relatives sur ces courbex qui pourraient servir de distance (à un facteur statique près) si on suppose que la courbure n'est pas trop accentuée.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 085
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 085
    Points : 9 457
    Points
    9 457
    Par défaut
    @Guesset : je pense que l'idée est de comparer 2 voitures qui sont sur le même spline dans la même direction. Pas de gestion des croisements à ce niveau.

    avantage des carrés : pas de 'multiplication, que des soustractions / additions. mais plus de calculs, plus de tests à effectuer (test sur x et sur y, au lieu de test sur d)
    avantage de la distance : on évite cette différence assez énorme entre les trajets horizontaux/verticaux et les autres (un facteur de 1.414 au pire)

    Mais en fait, la bonne idée vient de guesset.
    Sur chaque spline, tu vas a priori noter la position de chaque véhicule par un nombre entre 0 et 1. Et du coup, sauf accident majeur, une simple différence sur cet indicateur devrait convenir. Pour un spline, tu connais la longueur totale du trajet. Et une règle de 3 à partir de ce nombre entre 0 et 1 va donner une bonne approximation de la distance entre 2 véhicules.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 394
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 394
    Points : 4 363
    Points
    4 363
    Par défaut
    Bonjour tbc92,

    Citation Envoyé par tbc92 Voir le message
    ...je pense que l'idée est de comparer 2 voitures qui sont sur le même spline dans la même direction. Pas de gestion des croisements à ce niveau...
    Même si l'anticollision ne s'intéresse qu'à un sens (mais les segments se croisent...), on ne peut rester sur un seul segment (un seul spline). Si un véhicule est à la fin d'un segment, il peut heurter un véhicule qui est sur le (ou l'un des) segment(s) le prolongeant. Simplement parce que les véhicules ne sont pas ponctuels.

    ...Sur chaque spline, tu vas a priori noter la position de chaque véhicule par un nombre entre 0 et 1. Et du coup, sauf accident majeur, une simple différence sur cet indicateur devrait convenir. Pour un spline, tu connais la longueur totale du trajet. Et une règle de 3 à partir de ce nombre entre 0 et 1 va donner une bonne approximation de la distance entre 2 véhicules.
    Il y a un autre post sur le même sujet du même PO pour lequel j'ai un peu précisé les choses :

    "Sur un même segment Sn de longueur Ln, la distance entre 2 véhicules a et b (b derrière a : ratiob < ratioa) est approximativement (ratioa - ratiob) * Ln.

    Avec a et b sur deux segments de suite, Lm et Ln, ce n'est guère plus compliqué : ratioa*Lm + Ln - ratiob*Ln.

    Il y a sans doute mieux, mais cela semble déjà intéressant. De plus on peut aisément gérer des véhicules de longueurs différentes (la position est celle de l'avant de chaque)."

    Correction : dans le calcul de la distance, pour la détection de collision, il faudrait retirer la longueur du véhicule de devant.

    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  7. #7
    Membre éclairé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    Juillet 2006
    Messages
    723
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : Juillet 2006
    Messages : 723
    Points : 745
    Points
    745
    Par défaut
    Merci à tous pour vos réponses. Je vous tiens au courant

Discussions similaires

  1. [C#]Comment forcer la sélection d'un noeud avec bouton droit
    Par irnbru dans le forum Windows Forms
    Réponses: 3
    Dernier message: 16/11/2005, 19h39
  2. [Conception] Queue avec priorité
    Par Mobius dans le forum Général Java
    Réponses: 4
    Dernier message: 11/04/2005, 08h26
  3. Utiliser MySqlAdmin avec des droits utilisateurs sur XP
    Par thorgal85 dans le forum Outils
    Réponses: 2
    Dernier message: 18/03/2005, 12h19
  4. pb avec "bordure" droite d'un tableau
    Par 3psilOn dans le forum Balisage (X)HTML et validation W3C
    Réponses: 5
    Dernier message: 05/11/2004, 03h14
  5. Lancement de processus avec priorité
    Par GMI3 dans le forum Administration système
    Réponses: 2
    Dernier message: 14/06/2004, 16h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo