ECS170 Python
from copy import deepcopy
from queue import PriorityQueue
Copyright By PowCoder代写 加微信 powcoder
from Point import Point
import math
”’AIModule Interface
createPath(map map_) -> list
class AIModule:
def createPath(self, map_):
A sample AI that takes a very suboptimal path.
This is a sample AI that moves as far horizontally as necessary to reach
the target, then as far vertically as necessary to reach the target.
It is intended primarily as a demonstration of the various pieces of the
class StupidAI(AIModule):
def createPath(self, map_):
explored = []
# Get starting point
path.append(map_.start)
current_point = deepcopy(map_.start)
# Keep moving horizontally until we match the target
while(current_point.x != map_.goal.x):
# If we are left of goal, move right
if current_point.x < map_.goal.x:
current_point.x += 1
# If we are right of goal, move left
current_point.x -= 1
path.append(deepcopy(current_point))
# Keep moving vertically until we match the target
while(current_point.y != map_.goal.y):
# If we are left of goal, move right
if current_point.y < map_.goal.y:
current_point.y += 1
# If we are right of goal, move left
current_point.y -= 1
path.append(deepcopy(current_point))
# We're done!
return path
class Djikstras(AIModule):
def createPath(self, map_):
q = PriorityQueue()
explored = {}
for i in range(map_.width):
for j in range(map_.length):
cost[str(i)+','+str(j)] = math.inf
prev[str(i)+','+str(j)] = None
explored[str(i)+','+str(j)] = False
current_point = deepcopy(map_.start)
current_point.comparator = 0
cost[str(current_point.x)+','+str(current_point.y)] = 0
q.put(current_point)
while q.qsize() > 0:
# Get new point from PQ
v = q.get()
if explored[str(v.x)+’,’+str(v.y)]:
explored[str(v.x)+’,’+str(v.y)] = True
# Check if popping off goal
if v.x == map_.getEndPoint().x and v.y == map_.getEndPoint().y:
# Evaluate neighbors
neighbors = map_.getNeighbors(v)
for neighbor in neighbors:
alt = map_.getCost(v, neighbor) + cost[str(v.x)+’,’+str(v.y)]
if alt < cost[str(neighbor.x)+','+str(neighbor.y)]:
cost[str(neighbor.x)+','+str(neighbor.y)] = alt
neighbor.comparator = alt
prev[str(neighbor.x)+','+str(neighbor.y)] = v
q.put(neighbor)
while not(v.x == map_.getStartPoint().x and v.y == map_.getStartPoint().y):
path.append(v)
v = prev[str(v.x)+','+str(v.y)]
path.append(map_.getStartPoint())
path.reverse()
return path
class AStarExp(AIModule):
def createPath(self, map_):
class AStarDiv(AIModule):
def createPath(self, map_):
class AStarMSH(AIModule):
def createPath(self, map_):
import argparse
from time import time
from AIModule import StupidAI, Djikstras, AStarExp, AStarDiv, AStarMSH
from Map import Map
parser = argparse.ArgumentParser(description='Run programming assignment 1')
parser.add_argument('-w', default=500, type=int, help='Width of map')
parser.add_argument('-l', default=500, type=int, help='Length of map')
parser.add_argument('-start', nargs='+', type=int, help='Set the start point position')
parser.add_argument('-goal', nargs='+', type=int, help='Set the goal point position')
parser.add_argument('-seed', default=None, type=int, help='Seed for random generation')
parser.add_argument('-cost', default='exp', type=str, help='Cost function. Use any of the following: [exp, div]')
parser.add_argument('-AI', default='AStarExp', type=str, help='AI agent to use. Use any of the following: [AStarExp, AStarDiv, AStarMSH, Djikstra]')
parser.add_argument('-filename', default=None, type=str, help='Filepath for .npy file to be used for map')
args = parser.parse_args()
w = args.w
l = args.l
start = args.start
goal = args.goal
seed = args.seed
cost = args.cost
ai = args.AI
filename = args.filename
agents = {'AStarExp': AStarExp, 'AStarDiv': AStarDiv, 'AStarMSH': AStarMSH, 'Djikstra': Djikstras, 'StupidAI':StupidAI}
m = Map(w,l, seed=seed, filename=filename, cost_function=cost, start=start, goal=goal)
alg = agents[ai]()
t1 = time()
path = alg.createPath(m)
t2 = time()
print('Time (s): ', t2-t1)
m.createImage(path)import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
import math
from Point import Point
from AIModule import StupidAI, Djikstras, AStarExp
from perlin import perlin
from random import random, randint
from copy import deepcopy
from time import time
def scale(X):
X = ((X+1)/2 * 255).astype(int)
class Map():
def __init__(self, length, width, seed=None, filename=None,
cost_function='exp', start=None, goal=None):
self.seed = seed
if self.seed == None:
# Randomly assign seed from 0 to 10k if not provided
self.seed = randint(0,10000)
self.length = length
self.width = width
self.generateTerrain(filename)
self.explored = []
self.explored_lookup = {}
for i in range(self.width):
for j in range(self.length):
self.explored_lookup[str(i)+','+str(j)] = False
if start == None:
self.start = Point(int(self.width*0.5),int(self.length*0.5))
self.start = Point(start[0], start[1])
if goal == None:
self.goal = Point(int((self.width-1)*0.9),int((self.length-1)*0.9))
self.goal = Point(goal[0], goal[1])
if cost_function == 'exp':
self.cost_function = lambda h0, h1: math.pow(2,h1-h0)
self.cost_function = lambda h0, h1: h1/(h0 + 1)
'''generateTerrain: modifes self.map to either be the specified file, or
randomly generated from perlin noise.
filename - str, string of the npy file to generate the map
seed - int, integer for reproducibility of a particular map
octaves - int parameter for perlin noise
None, self.map modified'''
def generateTerrain(self, filename=None):
if filename is None:
linx = np.linspace(0,5,self.width,endpoint=False)
liny = np.linspace(0,5,self.length,endpoint=False)
x,y = np.meshgrid(linx,liny)
self.map = scale(perlin(x, y, seed=self.seed))
self.map = np.load(filename)
self.width = self.map.shape[0]
self.length = self.map.shape[1]
def interpolate(self, a0, a1, w):
if (0.0 > w):
if (1.0 < w):
return (a1 - a0) * ((w * (w * 6.0 - 15.0) + 10.0) * w ** 3) + a0
def calculatePathCost(self, path):
prev = path[0]
if self.start != prev:
print('Path does not start at start. Path starts at point: ' , str(prev.x),
',', str(prev.y))
return math.inf
for item in path[1:]:
if self.isAdjacent(prev, item):
cost += self.getCost(prev, item)
prev = item
print('Path does not connect at points: ', str(prev.x), ',', str(prev.y),
' and ', str(item.x), ',', str(item.y))
return math.inf
if prev != self.goal:
print('Path does not end at goal. Path ends at point: ' , str(prev.x),
',', str(prev.y))
return math.inf
return cost
def validTile(self, x, y):
return x >= 0 and y >= 0 and x < self.width and y < self.length
'''def validTile(self, p1):
return self.validTile(p1.x, p1.y)'''
def getTile(self, x, y):
return self.map[x][y]
print(self.length)
print(self.width)
'''def getTile(self, p1):
return self.getTile(p1.x, p1.y)'''
def getCost(self, p1, p2):
h0 = self.getTile(p1.x, p1.y)
h1 = self.getTile(p2.x, p2.y)
return self.cost_function(h0, h1)
def isAdjacent(self, p1, p2):
return (abs(p1.x - p2.x) == 1 or abs(p1.y - p2.y)) == 1 and (abs(p1.x - p2.x) < 2 and abs(p1.y - p2.y) < 2)
def getNeighbors(self, p1):
neighbors = []
for i in [-1, 0, 1]:
for j in [-1, 0, 1]:
if i == 0 and j == 0:
possible_point = Point(p1.x + i, p1.y + j)
if self.validTile(possible_point.x, possible_point.y):
neighbors.append(possible_point)
if not self.explored_lookup[str(possible_point.x)+','+str(possible_point.y)]:
self.explored_lookup[str(possible_point.x)+','+str(possible_point.y)] = True
self.explored.append(possible_point)
return neighbors
def getStartPoint(self):
return self.start
def getEndPoint(self):
return self.goal
def getHeight(self):
return np.amax(self.map)
'''Creates a 2D image of the path taken and nodes explroed, prints
pathcost and number of nodes explored'''
def createImage(self, path):
img = self.map
path_img = np.zeros_like(self.map)
explored_img = np.zeros_like(self.map)
for item in self.explored:
explored_img[item.x, item.y] = 1
path_img_x = [item.x for item in path]
path_img_y = [item.y for item in path]
print('Path cost:', self.calculatePathCost(path))
cmap = mpl.colors.ListedColormap(['white', 'red'])
print('Nodes explored: ', len(self.explored) + len(path))
plt.imshow(img, cmap='gray')
plt.imshow(explored_img, cmap=cmap, alpha=0.3)
plt.plot(path_img_y, path_img_x, linewidth=1)
plt.show()
'''Set the start and goal point on the 2D map, each point is a pair of integers'''
def setStartGoal(self, start, goal):
self.start = Point(np.clip(start[0], 0, self.length-1), np.clip(start[1], 0, self.width-1))
self.goal = Point(np.clip(goal[0], 0, self.length-1), np.clip(goal[1], 0, self.width-1))
import math
import numpy as np
class Point():
def __init__(self, posx, posy):
self.x = posx
self.y = posy
self.comparator = math.inf
def __lt__(self, other):
return self.comparator < other.comparator
def __gt__(self, other):
return self.comparator > other.comparator
def __eq__(self, other):
return self.x == other.x and self.y == other.y
import numpy as np
import matplotlib.pyplot as plt
from random import random
# Perline noise code courtesy of tgroid on SO
def perlin(x,y,seed=0):
# permutation table
np.random.seed(seed)
p = np.arange(256,dtype=int)
np.random.shuffle(p)
p = np.stack([p,p]).flatten()
# coordinates of the top-left
xi = x.astype(int)
yi = y.astype(int)
# internal coordinates
xf = x – xi
yf = y – yi
# fade factors
u = fade(xf)
v = fade(yf)
# noise components
n00 = gradient(p[p[xi]+yi],xf,yf)
n01 = gradient(p[p[xi]+yi+1],xf,yf-1)
n11 = gradient(p[p[xi+1]+yi+1],xf-1,yf-1)
n10 = gradient(p[p[xi+1]+yi],xf-1,yf)
# combine noises
x1 = lerp(n00,n10,u)
x2 = lerp(n01,n11,u)
return lerp(x1,x2,v)
def lerp(a,b,x):
“linear interpolation”
return a + x * (b-a)
def fade(t):
“6t^5 – 15t^4 + 10t^3”
return 6 * t**5 – 15 * t**4 + 10 * t**3
def gradient(h,x,y):
“grad converts h to the right gradient vector and return the dot product with (x,y)”
vectors = np.array([[0,1],[0,-1],[1,0],[-1,0]])
g = vectors[h%4]
return g[:,:,0] * x + g[:,:,1] * y
if __name__ == ‘main’:
lin = np.linspace(0,5,100,endpoint=False)
x,y = np.meshgrid(lin,lin)
plt.imshow(perlin(x,y,seed=5),origin=’upper’)
plt.show()
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com