程序代写 ECS170 Python

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: Adds points to a path”’
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