Discussion :

[guitz]

Bonjour,

Existe-t'il s'il vous plait un algorithme de pathfinding sur un graphe du genre "A star" incluant certaines règles de circulation ?

Par exemple : possibilité de faire un demi tour sur un sommet de type "cul de sac", mais interdiction sur un sommet de type "virage" ou "carrefour".

[dourouc05]

Ne s'agit-il pas plutôt de règles à appliquer quand tu crées ton graphe ? Mon idée : les nœuds du graphe représentent les routes à emprunter, avec des arêtes pour chaque carrefour, qui indiquent les transitions possibles.

Sinon, des Coréens ont déjà développé des extensions de Dijkstra et Floyd-Warshall pour ces cas : https://patents.google.com/patent/KR100653036B1/en. (La différence entre Dijkstra et A*, c'est une distance heuristique, ça devrait donc aussi s'appliquer.)

En parlant de routes, A* n'est pas le plus approprié pour ce genre de graphe. Regarde du côté des construction hierarchies (CH).

[guitz]

Merci beaucoup je vais creuser de ce côté

[guitz]

Bonjour,

Voici un exemple de graphe orienté simplifié :



Le triangle rouge est la position et l'orientation initiale de la voiture. Le cercle vert est le nœud de destination.

Je souhaite interdire un demi-tour dans un virage et un carrefour mais je l'autorise dans une impasse (nœud 4).

Le tableau de nœuds (3, 6, 8) est donc interdit.
De même (3, 1, 6, 8) est interdit.
En revanche, (3, 1, 2, 3, 6, 8) et (3, 4, 3, 6, 8) sont autorisés. Ce dernier étant le chemin le plus court.

Comment s'il vous plaît modifier la structure de données de mon graphique et l'algorithme A * (ou Dijkstra) pour atteindre mes objectifs?

On m'a parlé de contractions hiérarchiques et du coup j'ai commencé à lire cet article :
https://drops.dagstuhl.de/opus/vollt...MOS-2020-9.pdf

Vous pensez que le modèle compact répond à ma problématique ?

Modèle compact. Le modèle compact [18, 11] conserve les intersections comme sommets, mais associe
une table de virages p × q Tv avec chaque sommet v, où p et q sont les nombres de
arêtes entrantes et sortantes, respectivement. L'entrée Tv(i, j) représente le coût du virage du i-ème
arête entrante e vers le j-ième arête sortante f, c'est-à-dire Tv(i, j) = c(e, f). Pour chaque arête (v, w),
sa queue correspond à un point de sortie en v et sa tête correspond à un point d'entrée en w.
On note v|i la i-ième sortie (ou
point d'entrée) en v et par (v|i, w|j) l'arête dont la queue correspond au i-ième point de sortie en
v et dont la tête correspond au j-ième point d'entrée en w. Le principal avantage de la
modèle compact est sa faible surcharge d'espace puisque les tables de virages peuvent être partagées entre les sommets.

Merci

[Flodelarab]

Bonjour

Parce que ton vrai graphe, c'est ça :

Ou ça:

[guitz]

Merci d'avoir pris le temps de dessiner mon graphe.

Donc si j'ai bien compris il y a un graphe global pour toutes mes voitures qu'on va nommer G et un graphe propre à chaque voiture qu'on va nommer Gi (avec i compris entre 1 et le nombre de voiture). En effet vu l'interdiction de faire demi tout dans un noeud qui n'est pas un cul de sac, le graphe Gi (dont tu viens de dessiner un exemple) va dépendre de l'orientation et la position initiale de chaque voiture Vi
Est ce que je vais pas avoir un soucis de mémoire si j'ai spawn 5000 voitures et que G contient 2000 noeuds ?

[Flodelarab]

il y a un graphe global pour toutes mes voitures qu'on va nommer G et un graphe propre à chaque voiture qu'on va nommer Gi

Plutôt non. Ce graphe est général est modélise vraiment ta situation, quelque soit la voiture.

Est ce que je vais pas avoir un soucis de mémoire si j'ai spawn 5000 voitures et que G contient 2000 noeuds ?

5000 voitures n'est pas un problème. Par contre, les 2000 carrefours, un peu plus. Les carrefours sont multipliés par le nombre de routes qui les connectent. Dans ton exemple, on passe de 9 carrefours à 20 nœuds. Avec 2000 carrefours et 3 routes par nœud en moyenne, il faudra un graphe avec 6000 nœuds. Ta mémoire tiendra le choc.

[guitz]

Merci encore, je crois que je vais opter pour ta solution parce que je n'arrive pas à modifier l'algorithme A* pour n'autoriser les demi tours que sur les culs de sac . c'eut été tellement plus simple

Edit : mais au final ta méthode est plus flexible que de bricoler ponctuellement l'algo de pathfinding A*, car si demain par exemple je rajoute des routes à sens unique ou d'autres règles de circulation je sera bien content d'avoir un graphe qui le permet.