Discussion :

[poringkiller]

Bonjour, je cherche des pistes pour coder un algorithme qui calcule le plus court chemin sur une carte à 2 dimensions, pouvant contenir des obstacles, qui seraient des polygones.

Le trajet serait donc représenté sous forme de plusieurs lignes droites mises bout à bout.

Tout ce que j'ai trouvé pour le moment sont des algorithmes permettant de trouver le plus court chemin dans un graphe pondéré, ce qui ne correspond pas trop (mais je peux me tromper) à ma problématique.

J'imagine que la première étape serait de tracer une ligne droite entre mon point de départ et d'arrivée, et de vérifier si un polygone se trouve sur sa route.
(je ne cherche pas le calcul pour tester les "collisions" entre mon chemin et les polygones hein) Mais je suis bloqué à partir de là.

Quelques idées comme ça :
- faire varier l'angle du premier vecteur de déplacement jusqu'à ce qu'il ne soit plus en collision avec le polygone (mais comment déterminer le pas : le nombre de degrés ajoutés/retirés à chaque itération ? Comment faire, puisque le bon angle sera probablement atteint entre 2 itérations)
- il faudra surement calculer plusieurs chemins valides, avant de comparer leurs distances totales respectives

Voilà, je n'ai pas beaucoup plus à ajouter, si vous avez des idées, ou juste un nom d'algorithme vers lequel je pourrais me tourner, je suis preneur =)
Merci d'avance !

[pseudocode]

Le plus simple est de construire un graphe réunissant tous les points de visibilité = les points de départ/arrivé/angles des obstacles + toutes les arrêtes reliant ces points sauf celles qui passent au travers des obstacles. Reste a trouver le plus court chemin dans ce graphe qui rejoint le point de départ au point d'arrivé.

Sinon, on peut aussi créer un quadrillage afin de pouvoir utiliser les algos classiques et avoir rapidement un chemin valide. Reste a retravailler ce chemin pour passer au plus proche des obstacles.

google: Pathfinding 2d polygons

[GPPro]

Si tu connais tes cartes à l'avance, il s'agit d'un problème classique rencontré dans les jeux vidéos. Voir pour le pathfinding. Grosso modo, tu annotes ta carte a priori.

La solution de pseudocode correspond à du raycasting, c'est pas forcément simple mais une des solutions qu'il te reste si les cartes ne sont pas connues à l'avance..