Leider ist er nicht sonderlich schnell (viel zu langsam, längere Strecken brauchen schonmal schnell ne Sekunde oder länger), allerdings finde ich den "Flaschenhals" nicht... Hier der Code:
Code: Alles auswählen
def astar(self, startPos, endPos):
times = [0, 0, 0, 0]
clock = pygame.time.Clock()
start = (int(startPos[0] / 50), int(startPos[1] / 50))
end = (int(endPos[0] / 50), int(endPos[1] / 50))
def nodeKeyFunc(node): # Funktion zur Sortierung
return node.getRating()
def getNeighbours(node):
def checkAndAdd(x, y, list):
if x >= 0 and x <= 99 and y >= 0 and y <= 74:
# kontrolliert python die bedingungen automatisch von links nach rechts ?!
# wenn nicht, sorge dafuer, dass es keinen "Out-of-Range" error gibt
node = self.nodes[x][y]
if node.passable and not node in closedList:
list.append(node)
neighbours = []
x, y = node.position
checkAndAdd(x - 1, y - 1, neighbours)
checkAndAdd(x, y - 1, neighbours)
checkAndAdd(x + 1, y - 1, neighbours)
checkAndAdd(x - 1, y, neighbours)
checkAndAdd(x + 1, y, neighbours)
checkAndAdd(x - 1, y + 1, neighbours)
checkAndAdd(x, y + 1, neighbours)
checkAndAdd(x + 1, y + 1, neighbours)
return neighbours
def cost(node1, node2):
if abs((node1.position[0] - node2.position[0]) * \
(node1.position[1] - node2.position[1])) == 1: # diagonal
return 14 + node1.cost
return 10 + node1.cost
def manhatten(node1, node2):
return (abs(node1.position[0] - node2.position[0]) + \
abs(node1.position[1] - node2.position[1])) * 10
endNode = self.nodes[end[0]][end[1]]
startNode = self.nodes[start[0]][start[1]]
startNode.cost = 0
startNode.heuristic = manhatten(startNode, endNode)
openList = [startNode]
closedList = []
pathFound = 0
clock.tick()
while not pathFound:
if not len(openList):
pathFound = 1
continue
currentNode = openList[0]
for node in openList:
if node.getRating() < currentNode.getRating():
currentNode = node
openList.remove(currentNode)
# openList.sort(key = nodeKeyFunc)
# currentNode = openList.pop(0)
closedList.append(currentNode)
times[0] += clock.tick()
neighbours = getNeighbours(currentNode)
times[1] += clock.tick()
for neighbour in neighbours:
if not neighbour in openList:
neighbour.previous = currentNode
if neighbour == endNode:
pathFound = 2
else:
neighbour.cost = cost(currentNode, neighbour)
neighbour.heuristic = manhatten(currentNode, endNode)
openList.append(neighbour)
times[2] += clock.tick()
else:
tempCost = cost(currentNode, neighbour)
if tempCost < neighbour.cost:
neighbour.cost = tempCost
neighbour.previous = currentNode
times[3] += clock.tick()
if pathFound:
breakAn den Zeiten kann man erkennen, dass vor allem das Suchen der Nachbarn sehr Zeitaufwendig ist. Worin liegts?
[1] an mir
[2] an Python
[3] an Listen
MfG
Edit (Leonidas): Code in Python Tags gesetzt.
Davon abgesehen würde ich den inzwischen mit yield machen.
