Bonjour a tous, je me présente,je m'appelle Guillaume j'ai 19ans je suis actuellement a l’école 42.
Je me suis lance un petit défi, celui de créer un petit jeux sans prétention avec le framework love2D en Lua mais voila,
le moment ou le path finding arrive je commence a trembler et des gouttes de sueurs apparaissent x)
Donc pour la faire courte, j'utilise le a* que j'ai implémenter a partir de ce lien que j'ai traduit en Lua du Pyhon mais deja dans sa verion python il y a un bug avec une carte comme celle-ci :
Tandis que si je retire le moindre mur il fonctionne :
Voila voila...
J'ai essaye de debuger le code mais je ne parviens pas a le trouver precisement :/
function dist(x1, y1, x2, y2)
return math.sqrt((x2-x1)^2+(y2-y1)^2)
end
function createNode(parent, pos)
node = {}
node.position = {}
node.position.x = pos[1]
node.position.y = pos[2]
node.parent = parent
node.g = 0
node.h = 0
node.f = 0
return node
end
function get_tuple(x, y)
tuple = {}
tuple.x = x
tuple.y = y
return tuple
end
function debugPos(pos)
print("Pos : X="..pos.x.." Y="..pos.y)
end
function debugNode(node)
debugPos(node.position)
print("G: "..node.g.." H: "..node.h.." F: "..node.f)
print("===========")
end
function compareNode(node1, node2)
if node1.position.x == node2.position.x and node1.position.y == node2.position.y then return true end
return false
end
function isInInterval(val, max)
if val < 1 or val > max then return false end
return true
end
function a_star(src, dst, map)
passes = 0
map_height = table.getn(map[table.getn(map) - 1])
map_width = table.getn(map) + 1
src = {src[2], src[1]}
dst = {dst[2], dst[1]}
start_node = createNode(nil, src)
end_node = createNode(nil, dst)
if not isInInterval(start_node.position.x, map_width) then
return nil
elseif not isInInterval(start_node.position.y, map_height) then
return nil
elseif not isInInterval(end_node.position.x, map_width) then
return nil
elseif not isInInterval(end_node.position.y, map_height) then
return nil
end
open_list = {}
closed_list = {}
table.insert(open_list, start_node)
while table.getn(open_list) > 0 and passes < 1000 do
current_node = open_list[1]
current_index = 1
for index, item in ipairs(open_list) do
if item.f < current_node.f then
current_node = item
current_index = index
end
end
table.remove(open_list, current_index)
table.insert(closed_list, current_node)
if compareNode(current_node, end_node) then
path = {}
current = current_node
while current ~= nil do
table.insert(path, current.position)
current = current.parent
end
new_path = {}
j = table.getn(path)
i = 1
while i <= table.getn(path) do
new_path[i] = path[j]
j = j - 1
i = i + 1
end--]]
return new_path
end
children = {}
tab = {}
tab[1] = get_tuple(0, -1)
tab[2] = get_tuple(0, 1)
tab[3] = get_tuple(-1, 0)
tab[4] = get_tuple(1, 0)
tab[5] = get_tuple(-1, -1)
tab[6] = get_tuple(-1, 1)
tab[7] = get_tuple(1, -1)
tab[8] = get_tuple(1, 1)
for k,v in ipairs(tab) do
node_position = {}
node_position.x = current_node.position.x + v.x
node_position.y = current_node.position.y + v.y
if node_position.y > map_height or
node_position.y < 1 or
node_position.x > map_width - 1 or
node_position.x < 1 then
goto acontinue
end
if map[node_position.x][node_position.y] ~= 0 then goto acontinue end
new_node = createNode(current_node, {node_position.x, node_position.y})
table.insert(children, new_node)
::acontinue::
end
for k,child in ipairs(children) do
for l,closed_child in ipairs(closed_list) do
if compareNode(child, closed_child) then goto cont end
::cont::
end
child.g = current_node.g + 1
child.h = ((child.position.x - end_node.position.x) ^ 2) + ((child.position.y - end_node.position.y) ^ 2)
child.f = child.g + child.h
for l, open_node in ipairs(open_list) do
if compareNode(child, open_node) and child.g > open_node.g then goto cont2 end
::cont2::
end
table.insert(open_list, child)
end
passes = passes + 1
--[[print("====> PASSE : "..passes.." <====")
for k,v in ipairs(open_list) do
debugNode(v)
end--]]
end
end
PS : c'est un code lua mais le langage n'etait pas disponible pour le formattage
Si vous trouvez plus simple de le voir en python dans la mesure ou l avait le même problème je vous le mets en copie.
class Node():
"""A node class for A* Pathfinding"""
def __init__(self, parent=None, position=None):
self.parent = parent
self.position = position
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.position == other.position
def astar(maze, start, end):
"""Returns a list of tuples as a path from the given start to the given end in the given maze"""
# Create start and end node
start_node = Node(None, start)
start_node.g = start_node.h = start_node.f = 0
end_node = Node(None, end)
end_node.g = end_node.h = end_node.f = 0
# Initialize both open and closed list
open_list = []
closed_list = []
# Add the start node
open_list.append(start_node)
# Loop until you find the end
while len(open_list) > 0:
# Get the current node
current_node = open_list[0]
current_index = 0
for index, item in enumerate(open_list):
if item.f < current_node.f:
current_node = item
current_index = index
# Pop current off open list, add to closed list
open_list.pop(current_index)
closed_list.append(current_node)
# Found the goal
if current_node == end_node:
path = []
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
return path[::-1] # Return reversed path
# Generate children
children = []
for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
# Make sure within range
if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:
continue
# Make sure walkable terrain
if maze[node_position[0]][node_position[1]] != 0:
continue
# Create new node
new_node = Node(current_node, node_position)
# Append
children.append(new_node)
# Loop through children
for child in children:
# Child is on the closed list
for closed_child in closed_list:
if child == closed_child:
continue
# Create the f, g, and h values
child.g = current_node.g + 1
child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)
child.f = child.g + child.h
# Child is already in the open list
for open_node in open_list:
if child == open_node and child.g > open_node.g:
continue
# Add the child to the open list
open_list.append(child)
def main():
maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
start = (0, 0)
end = (7, 6)
path = astar(maze, start, end)
print(path)
if __name__ == '__main__':
main()
Un grand merci par avance a vos intervention en esperant une solution
Il y a une petite erreur dans le programme python :
ornode_position[1] > (len(maze[len(maze)-1]) -1)
à mon avis c'est plutôt ceci :
ornode_position[1] > (len(maze) -1)
Et une grosse erreur dans l'utilisation de l'instruction continue.
Celle ci fait sortir de la boucle à laquelle elle est rattachée mais elle ne fait pas sortir de toutes les boucles imbriquées
donc il faut modifier le programme comme ceci :
# Child is on the closed list
top=0
for closed_child in closed_list:
if child == closed_child:
top=1
continue
if top==0:
# Create the f, g, and h values
child.g = current_node.g + 1
child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2)
child.f = child.g + child.h
#print("B ",child.position[0],child.position[1],child.f)
# Child is already in the open list
top1=0
for open_node in open_list:
if child == open_node and child.g > open_node.g:
top1=1
continue
if top1==0:
# Add the child to the open list
open_list.append(child)
Mais il y a peut être mieux car je ne suis pas un spécialiste python !!!!
Bon courage
- Edité par PaulDurelin 8 décembre 2019 à 21:31:43
@PaulDurelin Bonjour, c'est bien d'aider, merci à vous, mais le code que vous proposez serait plus facilement lisible si vous utilisez la coloration syntaxique fournie dans ce forum.
Pour ce faire vous avez la possibilité d'éditer votre message affin d'utiliser le bouton code </> de l'éditeur. Merci.
Désolé du retard, je pensé ce post enterré mais merci beaucoup pour ta réponse je teste ça dés que possible
Etudiant à 42 Lyon ! :)
Path finding A* en lua
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Etudiant à 42 Lyon ! :)
Etudiant à 42 Lyon ! :)
Etudiant à 42 Lyon ! :)