1 """Some handy algorithms for use in games, etc.
3 Please note that this file is alpha, and is subject to modification in
4 future versions of pgu!
7 # The manhattan distance metric
8 def manhattan_dist(a,b):
9 return abs(a[0]-b[0]) + abs(a[1]-b[1])
12 def __init__(self, prev, pos, dest, dist):
13 self.prev,self.pos,self.dest = prev,pos,dest
14 if self.prev == None: self.g = 0
15 else: self.g = self.prev.g + 1
16 self.h = dist(pos,dest)
17 self.f = self.g+self.h
20 def astar(start,end,layer,dist=manhattan_dist):
21 """Uses the a* algorithm to find a path, and returns a list of positions
25 start -- start position
27 layer -- a grid where zero cells are open and non-zero cells are walls
28 dist -- a distance function dist(a,b) - manhattan distance is used
33 w,h = len(layer[0]),len(layer)
34 if start[0] < 0 or start[1] < 0 or start[0] >= w or start[1] >= h:
35 return [] #start outside of layer
36 if end[0] < 0 or end[1] < 0 or end[0] >= w or end[1] >= h:
37 return [] #end outside of layer
39 if layer[start[1]][start[0]]:
40 return [] #start is blocked
41 if layer[end[1]][end[0]]:
42 return [] #end is blocked
47 cur = node(None, start, end, dist)
52 if cur.pos not in open: continue
55 if cur.pos == end: break
56 for dx,dy in [(0,-1),(1,0),(0,1),(-1,0)]:#(-1,-1),(1,-1),(-1,1),(1,1)]:
57 pos = cur.pos[0]+dx,cur.pos[1]+dy
58 # Check if the point lies in the grid
59 if (pos[0] < 0 or pos[1] < 0 or
60 pos[0] >= w or pos[1] >= h or
61 layer[pos[0]][pos[1]]):
63 #check for blocks of diagonals
64 if layer[cur.pos[1]+dy][cur.pos[0]]: continue
65 if layer[cur.pos[1]][cur.pos[0]+dx]: continue
66 new = node(cur, pos, end, dist)
67 if pos in open and new.f >= open[pos].f: continue
68 if pos in closed and new.f >= closed[pos].f: continue
69 if pos in open: del open[pos]
70 if pos in closed: del closed[pos]
76 if new.f < opens[mid].f: hi = mid
84 while cur.prev != None:
92 """Returns a path of points from a to b
104 dx,dy = abs(x2-x1),abs(y2-y1)
106 if x2 >= x1: xi1,xi2 = 1,1
107 else: xi1,xi2 = -1,-1
109 if y2 >= y1: yi1,yi2 = 1,1
110 else: yi1,yi2 = -1,-1