Fond
Il y a une carte carrée avec quelques obstacles. Les obstacles sont représentés par des polygones. J'ai implémenté l'algorithme de recherche de chemin suivant:
1) Choisir la précision (cela sera noté k)
2) Diviser la carte en k x k carrés.
3) Faire un graphique à partir de ces carrés selon les règles suivantes:
- Chaque nœud représente un carré
- Deux nœuds sont connectés si et seulement s'ils sont adjacents et qu'aucun d'eux ne comporte d'obstacle.
4) Trouver plus court chemin en utilisant un algorithme * (ou Dijkstra ou autre ...)Orientation optimale
Cet algorithme fonctionne très bien si la carte est pas dynamique. Cela signifie que les obstacles ne peuvent pas être déplacés.
Questions
1) Cette approche est-elle efficace?
2) Que faire si les obstacles peuvent être déplacés?
3) Comment traiter les autres agents? Considérons la situation où il y a des objets dans la pièce. Il y en a deux. Tous les agents sont dans un groupe, et ce groupe près d'une des sorties. Si tous les agents vont à la sortie la plus proche, cela causera un goulot d'étranglement. Certains d'entre eux devraient aller à l'autre sortie pour minimiser le temps nécessaire pour sortir. Comment obtenir un tel résultat?