-
Notifications
You must be signed in to change notification settings - Fork 0
/
pathing.py
146 lines (104 loc) · 4.76 KB
/
pathing.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
from pprint import pprint as p
########################################################################
class AStar(object):
"""pathfinding"""
#----------------------------------------------------------------------
def __init__(self, start, end):
"""Constructor"""
self.openList = []
self.closedList = []
self.edgeG = 10
self.cornerG = 14
self.start = start
self.end = end
print 'starting search'
self.beginSearch()
print 'done searching'
#----------------------------------------------------------------------
def beginSearch(self):
"""starts pathfinding"""
# ( tile , parent ) > now it's just tile
self.start.parent = self.start
self.start.G = 0
self.start.H = self.calcH(self.start, self.end)
self.start.F = self.calcF(self.start)
self.openList.append(self.start) #1
#loop starts here
x = 1
#print 'end:', self.end
while self.end not in self.closedList:
self.openList.sort(key=lambda tile:tile.F, reverse=False)
print 'loop start, round', x
#print 'len of closed list', len(self.closedList)
#print 'lowest
x += 1
#4, find lowest F from openlist put it in closed
possibleTile = self.openList[0]
self.openList.remove(possibleTile)
self.closedList.append(possibleTile)
#5 check nearby, add them to open if not in open or closed list
for tile in possibleTile.nearby:
if tile not in self.closedList:
if not tile.ID[0] < 0 \
and not tile.ID[1] < 0\
and not tile.ID[0] > 1000 \
and not tile.ID[1] > 1000\
and not tile.unwalkable: #and also unwalkable
if tile not in self.openList:
tile.parent = possibleTile
tile.G = self.calcG(tile.parent, tile)
tile.H = self.calcH(tile, self.end)
tile.F = self.calcF(tile)
tile.parent = possibleTile
self.openList.append(tile)
elif tile in self.openList:
#6 if going through possible tile is faster
if self.calcG(possibleTile, tile) < \
tile.G: #possibleTiles not the parent, test the G
# to see if it is faster if it IS.
tile.parent = possibleTile
tile.G = self.calcG(tile.parent, tile)
tile.F = self.calcF(tile)
print 'done searching, length of path:', len(self.closedList)
return self.buildPath()
#----------------------------------------------------------------------
def buildPath(self):
"""go through all the tiles parents to another"""
self.path = []
node = self.end
while node != self.start:
self.path.append(node)
node = node.parent
print 'done building path'
return self.path
#----------------------------------------------------------------------
def calcH(self, currentTile, endTile):
"""finds the h with manhattan algo"""
sx, sy = currentTile.ID
ex, ey = endTile.ID
H = (ex - sx) + (ey - sy)
return H
#----------------------------------------------------------------------
def calcG(self, sourceTile, currentTile):
"""finds G from sourceTile to currentTile by adding
sources's G to e's corner or edge value"""
sx, sy = sourceTile.ID
ex, ey = currentTile.ID
if sx != ex and sy != ey:
#print 'corner!'
g = self.cornerG
else:
#print 'edge!'
g = self.edgeG
return g + sourceTile.G
#----------------------------------------------------------------------
def calcF(self, currentTile):
"""adds G and H together"""
F = currentTile.G + currentTile.H
return F
#########################################################################
#class AI:
#"""class that handles all AI"""
##----------------------------------------------------------------------
#def __init__(self):
#"""Constructor"""