Discussion :

[guitz]

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.



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 ?




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

[tbc92]

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.

[guitz]

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;
}

[Guesset]

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

[tbc92]

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

[Guesset]

Bonjour tbc92,

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

[guitz]

Merci à tous pour vos réponses. Je vous tiens au courant