-
Notifications
You must be signed in to change notification settings - Fork 0
/
distanceCalculator.py
157 lines (134 loc) · 4.7 KB
/
distanceCalculator.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
147
148
149
150
151
152
153
154
155
156
# distanceCalculator.py
# ---------------------
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).
"""
This file contains a Distancer object which computes and
caches the shortest path between any two points in the maze.
Example:
distancer = Distancer(gameState.data.layout)
distancer.getDistance( (1,1), (10,10) )
"""
import sys, time, random
class Distancer:
def __init__(self, layout, default = 10000):
"""
Initialize with Distancer(layout). Changing default is unnecessary.
"""
self._distances = None
self.default = default
self.dc = DistanceCalculator(layout, self, default)
def getMazeDistances(self):
self.dc.run()
def getDistance(self, pos1, pos2):
"""
The getDistance function is the only one you'll need after you create the object.
"""
if self._distances == None:
return manhattanDistance(pos1, pos2)
if isInt(pos1) and isInt(pos2):
return self.getDistanceOnGrid(pos1, pos2)
pos1Grids = getGrids2D(pos1)
pos2Grids = getGrids2D(pos2)
bestDistance = self.default
for pos1Snap, snap1Distance in pos1Grids:
for pos2Snap, snap2Distance in pos2Grids:
gridDistance = self.getDistanceOnGrid(pos1Snap, pos2Snap)
distance = gridDistance + snap1Distance + snap2Distance
if bestDistance > distance:
bestDistance = distance
return bestDistance
def getDistanceOnGrid(self, pos1, pos2):
key = (pos1, pos2)
if key in self._distances:
return self._distances[key]
else:
raise Exception("Positions not in grid: " + str(key))
def isReadyForMazeDistance(self):
return self._distances != None
def manhattanDistance(x, y ):
return abs( x[0] - y[0] ) + abs( x[1] - y[1] )
def isInt(pos):
x, y = pos
return x == int(x) and y == int(y)
def getGrids2D(pos):
grids = []
for x, xDistance in getGrids1D(pos[0]):
for y, yDistance in getGrids1D(pos[1]):
grids.append(((x, y), xDistance + yDistance))
return grids
def getGrids1D(x):
intX = int(x)
if x == int(x):
return [(x, 0)]
return [(intX, x-intX), (intX+1, intX+1-x)]
##########################################
# MACHINERY FOR COMPUTING MAZE DISTANCES #
##########################################
distanceMap = {}
class DistanceCalculator:
def __init__(self, layout, distancer, default = 10000):
self.layout = layout
self.distancer = distancer
self.default = default
def run(self):
global distanceMap
if self.layout.walls not in distanceMap:
distances = computeDistances(self.layout)
distanceMap[self.layout.walls] = distances
else:
distances = distanceMap[self.layout.walls]
self.distancer._distances = distances
def computeDistances(layout):
"Runs UCS to all other positions from each position"
distances = {}
allNodes = layout.walls.asList(False)
for source in allNodes:
dist = {}
closed = {}
for node in allNodes:
dist[node] = sys.maxsize #sys.maxint
import util
queue = util.PriorityQueue()
queue.push(source, 0)
dist[source] = 0
while not queue.isEmpty():
node = queue.pop()
if node in closed:
continue
closed[node] = True
nodeDist = dist[node]
adjacent = []
x, y = node
if not layout.isWall((x,y+1)):
adjacent.append((x,y+1))
if not layout.isWall((x,y-1)):
adjacent.append((x,y-1) )
if not layout.isWall((x+1,y)):
adjacent.append((x+1,y) )
if not layout.isWall((x-1,y)):
adjacent.append((x-1,y))
for other in adjacent:
if not other in dist:
continue
oldDist = dist[other]
newDist = nodeDist+1
if newDist < oldDist:
dist[other] = newDist
queue.push(other, newDist)
for target in allNodes:
distances[(target, source)] = dist[target]
return distances
def getDistanceOnGrid(distances, pos1, pos2):
key = (pos1, pos2)
if key in distances:
return distances[key]
return 100000