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

  • Python - The python programming language.
  • PyGame - Game development for Python.

Downloads

No License

Both the AStar implementation and the example code is public domain.


Comment this project:

Your name:
Your email (hidden):
Message:
Enter the validation code :
Private! (visible for webmaster only)

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.

Steven Zhou 2011-08-07 04:17:45

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

Steven Zhou 2011-08-07 04:05:02

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

Steven Zhou 2011-08-07 04:01:05

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

Tiersen 2011-02-27 21:18:35

thanks for sharing.

View all