AStar v1.1
A simple python implementation of the A* (a-star) path finding algorithm. The source contains the algorithm and a simple proof-of-concept example using pygame.
The code only implements support for a plain square map but it should be fairly simple to implement support for any map type. If you have any questions regarding this don't hesitate to ask.
AStarExample Instructions
Edit the map by first selecting a tile type. The blocking tiles can not be passed. The walkable tiles has values from 1-4 (also known as move cost) where 1 represents easy terrain (low cost) and 4 is rough terrain (high cost). You can also place the start and ending points.
When you are finished editing press the Find path button and the AStar algorithm will try to find the path with the lowest cost. If any path is found it will be displayed with white lines.
Screenshot
Related links
Downloads
- AStar_v1.1.tar.gz - Current version.
No License
Both the AStar implementation and the example code is public domain.
Comment this project:
Steven Zhou 2011-08-07 05:06:15
It will faster 10 times.
I test a map(34,1000),old code will using 3 seconds to find path at my PC,
new code will using 0.3 seconds.
I know why cutted my code: (smaller and bigger symbol etc..)
class Path:
def init(self,nodes, totalCost):
self.nodes = nodes;
self.totalCost = totalCost;
def getNodes(self):
return self.nodes
def getTotalMoveCost(self):
return self.totalCost
class Node:
def init(self,location,mCost,lid,parent=None):
self.location = location
self.mCost = mCost
self.parent = parent
self.score = 0
self.lid = lid
def eq(self, n):
if n.lid == self.lid:
return 1
else:
return 0
class AStar:
def init(self,maphandler):
self.mh = maphandler
self.searchnodes = 0
def _tracePath(self,n):
nodes = [];
totalCost = n.mCost;
p = n.parent;
nodes.insert(0,n);
while 1:
if p.parent is None:
break
nodes.insert(0,p)
p=p.parent
return Path(nodes,totalCost)
def _handleNode(self,node,end):
scores = self.on[node.score]
del self.o[node.lid]
del scores[node.key]
if not scores: del self.on[node.score]
self.c[node.lid] = 1
nodes = self.mh.getAdjacentNodes(node,end)
for n in nodes:
if n.location == end:
return n
elif self.c.has_key(n.lid):
continue
elif self.o.has_key(n.lid):
on = self.o[n.lid]
if n.mCost(using smaller)on.mCost:
scores = self.on[on.score]
del self.o[on.lid]
del scores[on.key]
if not scores: del self.on[on.score]
else:
continue
scores = {}
if self.on.has_key(n.score):
scores = self.on[n.score]
self.searchnodes += 1
thekey = -self.searchnodes
n.key = thekey
scores[thekey] = n
self.on[n.score] = scores
self.o[n.lid] = n
return None
def findPath(self,fromlocation, tolocation):
self.o = {}
self.on = {}
self.c = {}
self.searchnodes = 0
end = tolocation
fnode = Node(fromlocation,0,((fromlocation.y*self.mh.w)+fromlocation.x))
nodes = {}
self.searchnodes += 1
thekey = -self.searchnodes
fnode.key = thekey
nodes[thekey] = fnode
self.on[fnode.score] = nodes
self.o[fnode.lid] = fnode
nextNode = fnode
while nextNode is not None:
finish = self._handleNode(nextNode,end)
if finish:
return self._tracePath(finish)
nextNode = None
k = self.on.keys()
if not k: continue
k.sort()
then = self.on[k0]
k = then.keys()
k.sort()
nextNode = then[k0]
return None
class SQ_Location:
def init(self,x,y):
self.x = x
self.y = y
def eq(self, l):
if l.x self.x and l.y self.y:
return 1
else:
return 0
class SQ_MapHandler:
def init(self,mapdata,width,height):
self.m = mapdata
self.w = width
self.h = height
def getAdjacentNodes(self, curnode, dest):
result = []
cl = curnode.location
dl = dest
#
n = self._handleNode(cl.x+1,cl.y,curnode,dl.x,dl.y)
if n: result.append(n)
n = self._handleNode(cl.x-1,cl.y,curnode,dl.x,dl.y)
if n: result.append(n)
n = self._handleNode(cl.x,cl.y+1,curnode,dl.x,dl.y)
if n: result.append(n)
n = self._handleNode(cl.x,cl.y-1,curnode,dl.x,dl.y)
if n: result.append(n)
#
n = self._handleNode(cl.x+1,cl.y+1,curnode,dl.x,dl.y,True)
if n: result.append(n)
n = self._handleNode(cl.x-1,cl.y+1,curnode,dl.x,dl.y,True)
if n: result.append(n)
n = self._handleNode(cl.x+1,cl.y-1,curnode,dl.x,dl.y,True)
if n: result.append(n)
n = self._handleNode(cl.x-1,cl.y-1,curnode,dl.x,dl.y,True)
if n: result.append(n)
return result
def _handleNode(self,x,y,fromnode,destx,desty, bCost = False):
location = SQ_Location(x,y)
x = location.x
y = location.y
if x(using smaller)0 or x(using bigger)=self.w or y(using smaller)0 or y(using bigger)=self.h:
return None
d = self.m[(y*self.w)+x]
if d == -1:
return None
n = Node(location,d,((y*self.w)+x))
if n is not None:
dx = max(x,destx) - min(x,destx)
dy = max(y,desty) - min(y,desty)
emCost = (dx+dy) * 10
if bCost:
n.mCost = fromnode.mCost + n.mCost * 14
else:
n.mCost = fromnode.mCost + n.mCost * 10
n.score = n.mCost+emCost
n.parent=fromnode
return n
return None
my code is cutted.
I only paste core code here:
def _handleNode(self,node,end):
scores = self.on[node.score]
del self.o[node.lid]
del scores[node.key]
if not scores: del self.on[node.score]
self.c[node.lid] = 1
nodes = self.mh.getAdjacentNodes(node,end)
for n in nodes:
if n.location == end:
return n
elif self.c.has_key(n.lid):
continue
elif self.o.has_key(n.lid):
on = self.o[n.lid]
if n.mCost
Good job.
I modified source using Dict.
#self.on is a {}, key = node.score,value = {}
#self.on's value: key = 0 - all searched nodes count, value = node
#so ,getBestOpenNode will using hash sort to get the best nodes(nodes,not is
#node),then ,get the latest searched node from best nodes
class AStar:
def init(self,maphandler):
self.mh = maphandler
self.searchnodes = 0
def _tracePath(self,n):
nodes = [];
totalCost = n.mCost;
p = n.parent;
nodes.insert(0,n);
while 1:
if p.parent is None:
break
nodes.insert(0,p)
p=p.parent
return Path(nodes,totalCost)
def _handleNode(self,node,end):
scores = self.on[node.score]
del self.o[node.lid]
del scores[node.key]
if not scores: del self.on[node.score]
self.c[node.lid] = 1
nodes = self.mh.getAdjacentNodes(node,end)
for n in nodes:
if n.location == end:
return n
elif self.c.has_key(n.lid):
continue
elif self.o.has_key(n.lid):
on = self.o[n.lid]
if n.mCost
thanks for sharing.