Das ganze braucht auf einem 160*116 Feld schon mal gut und gerne 1-2 Sekunden, wenn kein Weg verfügbar ist, was viel zu viel ist.
Ich habe hier einfach mal die Implementation rausgerissen, und das komplette ausführbare Projekt zusätzlich angehängt. (Macht euch nicht die Mühe auf die Knöpfe der anderen Algorithmen ausser A* zu klicken, die gehen alle noch nicht.)
Code: Alles auswählen
def useAstar(self, start, goal):
self.path = []
currList = (start.HCost,0,Edge(None,start,0))
self.openList = [currList]
self.openHash = {}
self.openHash[id(start)] = currList
print self.openList
self.closedList ={}
print self.closedList
while self.openList != []:
currList = heappop(self.openList)
nodeID = id(currList[2].terminalNode)
if nodeID in self.closedList:
continue
self.closedList[nodeID] = currList
del self.openHash[nodeID]
if currList[2].terminalNode is goal:
self.internalAstar_reconstructPath(start, goal)
return self.path
for edge in currList[2].terminalNode.outgoingEdges:
self.internalAstar_checkEdge(edge, currList, goal)
def internalAstar_reconstructPath(self,start,goal):
print "found goal"
node = goal
while node != None:
self.path.append(node)
list = self.closedList[id(node)]
node = list[2].initialNode
self.path.reverse()
return self.path
def internalAstar_checkEdge(self, edge, currList, goal):
nodeID = id(edge.terminalNode)
if nodeID in self.closedList:
closed = self.closedList[nodeID]
if edge.weight + currList[1] < closed[1]:
del self.closedList[nodeID]
edge.terminalNode.checkInheritedHCost(edge)
self.internalAstar_insert(edge, currList, nodeID)
return
if nodeID in self.openHash:
opened = self.openHash[nodeID]
if edge.weight + currList[1] < opened[1]:
self.internalAstar_insert(edge, currList, nodeID)
return
edge.terminalNode.computeHCost(goal, edge)
self.internalAstar_insert(edge, currList, nodeID)
def internalAstar_insert(self, edge, currList, nodeID):
gcost = currList[1]+edge.weight
currList = (gcost+edge.terminalNode.HCost, gcost, edge)
heappush(self.openList, currList)
self.openHash[nodeID] = currList
Ich wäre euch wirklich sehr dankbar für Ideen, wie man das noch beschleunigen könnte, oder Anregungen, was ich bei dieser Implementation falsch gemacht habe, denn ich weiß wirklich nicht mehr weiter.
Dass die Demo nicht gut ist, ist mir klar (zb dass direkt alle Suchknoten erstellt werden), oder dass man das beschleunigen kann indem man eine andere Representation für den Suchraum benutzt, aber die Implementation von dem Algorithmus als solche scheint ja schon nicht in Ordnung zu sein, und um den geht es mir hier.
http://fileload.us/49885320-demo.rar