Graphe orienté et graphe non orienté pour modélisation de réseau de routes et traffic

Bonjour,

J'essaie de développer un réseau de routes et son traffic.

Pour se faire j'ai pensé deux graphe : G1 et G2.

G1 étant un graphe non orienté (en vert sur le shéma) qui servirait uniquement à l'affichage des routes (splines, etc....)
G2 étant un graphe orienté (sommets en noir et arêtes en bleu) qui servirait pour pour un algorithme de pathfinding genre A*.

Pièce jointe 647296

Est ce la meilleure façon de procéder sachant que G1 contiendra maximum 5000 sommets et 8 arêtes adjacentes par sommet et G2 contiendra maximum 5000 x 9= 45000 sommets et 7 arêtes adjacentes par sommet.
Dois-je utiliser deux graphes indépendants ? Ou est ce plus propre d'utiliser un graphe et son sous-graphe ?

:salut:

As-tu besoin d'un graphe pour l'affichage ? N'est-ce pas plutôt un ensemble de segments (dans une structure de données appropriée) ? Je ne vois pas en quoi le graphe apporte quelque chose dans ce cas. A priori, la liste des segments sera plus utile sur GPU qu'en RAM, alors que les GPU n'apprécient pas fortement les graphes et structures de données pas hyper compactes.

Salut Dourouc05,

Pièce jointe 647445

Commet tu le vois je dois afficher aussi bien des arêtes que des sommets du graphe (encerclés de rouge).

J'ai créé une classe MySpline qui entre autres comme propriétés :

Code:

---

1 2 3 4

bool IsOnANode; //vaut true si cette spline correspond à un sommet, sinon elle correspond à une arête int NodeArrayIndex; //index du tableau de structs GraphNodes correspondant au sommet en question int EdgeArrayIndex; //index du tableau de structs GraphEdges correspondant à l'arête en question TArray<FVector> SplinesControlPoints; //tableau de vecteurs servant à dessiner la spline

---

Peut être que je me trompe, mais pour l'affichage j'ai besoin ET d'un ensemble d'arêtes ET d'un ensemble de sommets ?

Citation:

---

Envoyé par guitz

Peut être que je me trompe, mais pour l'affichage j'ai besoin ET d'un ensemble d'arêtes ET d'un ensemble de sommets ?

---

À moins d'avoir des segments qui se superposent et des modèles 3D qui marchent bien dans ce cas (j'en doute !), oui.

Merci encore dourouc05, je vais rester sur une graphe unique (orienté) et plusieurs arêtes ou sommets pointeront vers le meme objet Spline pour l'affichage.