Pygame et path finding
Bonjour,
J'ai pour projet de créer un programme de path finding en python. J'ai rencontré un problème dans la fonction find_path dans le if (ligne 48) : la fonction find_path.add_block() ne fonctionne pas... alors que si je mets un print, il s'affiche
Pourriez-vous m'aider a résoudre ce problème voir à améliorer mon programme ?
Merci
import pygame, sys, math cell_size = 30 NB_column = 12 NB_row = 15 x = 0 y = 190 find = False class Block: def __init__(self, posx, posy, color): self.posx = posx self.posy = posy self.color = color def get_coord_x(self): return self.posx def get_coord_y(self): return self.posy class Path: def __init__(self): self.all_block = [] def get_block(self): return self.all_block def add_block(self): new_block = Block(block.posx, block.posy, block.color) self.all_block.append(new_block) def draw_block(self): for block in self.all_block: rect = pygame.Rect(math.floor(block.posx / 30) * cell_size, math.floor(block.posy / 30) * cell_size, cell_size, cell_size) pygame.draw.rect(screen, pygame.Color(str(block.color)), rect) def grid(): for i in range(0, NB_column): for j in range(0, NB_row): rect = pygame.Rect(i * cell_size, j * cell_size, cell_size, cell_size) pygame.draw.rect(screen, pygame.Color("black"), rect, width=1) def find_path(): for block in path.get_block(): for direction in move: if math.floor(block.get_coord_x() / 30) == move[direction][0] and math.floor(block.get_coord_y() / 30) == move[direction][1]: block = Block(60, 100, "red") path_find.add_block() timer = pygame.time.Clock() game_on = True path = Path() path_start = Path() path_find = Path() pygame.init() screen = pygame.display.set_mode((NB_column * cell_size, NB_row * cell_size)) pygame.display.set_caption('path_finding') block = Block(0, 190, "green") path_start.add_block() block = Block(30, 190, "black") path.add_block() block = Block(0, 190, "red") path_find.add_block() while game_on: for event in pygame.event.get(): if event.type == pygame.QUIT: game_on = False for event in pygame.event.get(): if event.type == pygame.MOUSEBUTTONDOWN: pass x = math.floor(path_find.get_block()[len(path_find.get_block()) - 1].get_coord_x() / 30) y = math.floor(path_find.get_block()[len(path_find.get_block()) - 1].get_coord_y() / 30) move = {"right": [x + 1, y], "left": [x - 1, y], "up": [x, y - 1], "down": [x, y + 1]} grid() find_path() path.draw_block() path_find.draw_block() path_start.draw_block() pygame.display.update() game_on = False timer.tick(60)
Android / Chrome 114.0.0.0
- Pygame pathfinding
- Modulenotfounderror: no module named 'pygame' ✓ - Forum Python
- Pygame importer une police d'écriture ✓ - Forum Python
1 réponse
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