Pygame et path finding
Fermémamiemando Messages postés 33539 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 19 février 2025 - 7 juil. 2023 à 15:29
1 réponse
7 juil. 2023 à 15:29
Bonjour,
Je ne connais pas pygame dans le détail, mais à un moment il faut que ta fonction find_path rafraîchisse l'affichage. Sauf erreur de ma part, comme tu ne le fais pas, il ne se passe rien.
Ensuite comme tu demandes comment améliorer ton programme et qu'il s'agit de trouver un chemin, je t'invite à regarder l'algorithme de Dijkstra. Celui-ci nécessite de représenter ton terrain de jeu par un modèle de graphe (c'est-à-dire un ensemble de sommet connecté par des liens). Plus précisément :
- Chaque sommet correspond à une case du terrain.
- On connecte (i, j) à (i', j') si on autorise un déplacement de (i, j) vers (i', j') : en pratique on connecte donc une case aux cases voisines (accessibles)
- On peut pondérer les liens (par exemple pour matérialiser le fait que selon la nature de la case de départ et la case d'arrivée, le coût est plus ou moins important).
- Si tu n'as pas de notion de coût, il suffit de leur assigner à toutes le même coût strictement positif (par exemple 1).
- La connexion peut être bidirectionnelle ou unidirectionnelle (si tu as une notion de sens unique, on utilise un lien unidirectionnel). Le coût peut être égal de (i, j) vers (i', j') et (i', j') vers (i, j) ou non.
- Si tous les liens sont unidirectionnels et que le coût d'un lien ne dépend pas du sens dans lequel on le traverse, un modèle de graphe non dirigé est suffisant.
- Sinon il faut utiliser un graphe orienté.
- Le plus souvent, on considère que le coût d'un chemin est obtenu en additionnant le coût de ses liens (à valeurs réelles positives) et que le but est de trouvé le chemin de coût minimal. En maths on parle alors de la structure algébrique (R+, min, +), car min joue le rôle d'opérateur de comparaison et + celui d'opérateur de concaténation. Il a en effet été démontré que l'algorithme de Dijkstra restait valide tant que la structure algébrique était un semi anneau (ou de dïoïde). Ainsi l'algorithme de Dijkstra s'applique pour les structures algébriques suivantes :
- (R+, min, +) : plus court chemin
- (R°, max, min) : chemin de meilleur bande passante
- ([0, 1], min, x) : chemin le plus sûr
Une fois le graphe et le semi anneau algébrique choisie, l'algorithme de Dijkstra calcule depuis un sommet s un arbre de plus court chemins optimaux vers chaque autre sommet (atteignable). Ce calcul se fait en temps polynomial (en terme simple : ce calcul est très rapide).
Une implémentation simpliste de l'algorithme de Dijkstra est disponible ici qui présuppose qu'on travaille avec (R+, min, +). Des implémentations plus avancées de l'algorithme de Dijkstra permettent de choisir l'opérateur de comparaison et de concaténation (voir par la BGL en C++ ; ou cette adaptation en python et quelques exemples).
Bonne chance