from random import *
import sys
from copy import deepcopy

global GRASS_BLOCK
global WALL_BLOCK
global DIAGONAL
global DEBUG

DEBUG = False
DIAGONAL = 1.412
GRASS_BLOCK = 0
WALL_BLOCK = 101

# Sole class needed for use of the wavefront expansion algorithm.
# Each frame where any objectives move or the map changes call
# updateObjectivesPF(), and for each WFEAObject whose velocity is due
# to be updated call getNextMovementVector"""
class WFEASearch:
	#grid = the Grid this search is in, objs = the objectives in a list
	def __init__(self, grd, objs):
		self.grid = grd
		self.objectives = objs
	# Adds an objective to the WFEA search. Linear increase in time/frame per
	# objective,depending on the radius of the objective
	def addObjective(self, obj):
		self.objectives.append(obj)
	
	# Removes an objective from the WFEA search
	def removeObjective(self, obj):
		self.objectives.remove(obj)
	# Updates the performance fields of each objective
	def updateObjectivesPF(self, counter):
		for i in range(len(self.objectives)):
			o = self.objectives[i]
			radius = o.radius
			ox = o.x
			oy = o.y
			rad = 0
			self.grid.setDistanceValue(o, ox, oy, 0, counter)
			
			previousExpansion = [[o.x, o.y]] # The files that were marked in the
			# last loop
			currentExpansion = [] # The files that we are marking in this loop
			n = True
			while rad in range(radius):
				lenMarked = len(previousExpansion)
				for i in range(lenMarked):
					ox = previousExpansion[i][0]
					oy = previousExpansion[i][1]
					points = self.getAdjacent(o, ox, oy, counter)
					for i in range(len(points)):
						if points[i][0] >= self.grid.width or points[i][1] >= self.grid.height:
							continue
						resistance = self.RESIST(o, points[i][0], points[i][1], ox, oy)
						if not self.grid.isUpdated(o, points[i][0], points[i][1], counter):
							if resistance > 0:
								self.grid.setDistanceValue(o, points[i][0], points[i][1], resistance, counter)
								currentExpansion.append([points[i][0], points[i][1]])
				rad = rad + 1
				#print("End of radius", rad, "previousExpansion:", str(previousExpansion),
				#	"currentExpansion:", str(currentExpansion))
				previousExpansion = []
				for temp in range(len(currentExpansion)):
					previousExpansion.append(currentExpansion[temp])
				currentExpansion = []
				

	# Checks the location of the WFEA object and returns a vector for the
	# next location that the WFEA object should go. Normalized to [-1, 1]
	# Objective and a WFEAObject
	def getNextMovementVector(self, objective, obj, counter): 
		if DEBUG:
			print("Checking next movement vector")
		xBlock = int(obj.x / 32)
		yBlock = int(obj.y / 32)
		if DEBUG:
			print("Object location:", xBlock, yBlock)

		if xBlock == obj.nextDesiredBlockX and yBlock == obj.nextDesiredBlockY:
			obj.nextDesiredBlockX = -1
			obj.nextDesiredBlockY = -1
			if DEBUG:
				print("Made it to the objective")
		elif counter - obj.lastUpdated > 50:
			obj.nextDesiredBlockX = -1
			obj.nextDesiredBlockY = -1
			if DEBUG:
				print("Probably stuck")
		else:
			obj.lastUpdated = deepcopy(counter)
		
		if obj.nextDesiredBlockX >= 0 and obj.nextDesiredBlockY >= 0:
			if DEBUG:
				print("Next location already set")
			goalX = obj.nextDesiredBlockX * 32 + 8
			goalY = obj.nextDesiredBlockY * 32 + 8
			if DEBUG:
				print("Trying to get to", goalX, goalY, "from", obj.x, obj.y)
			dirX, dirY = self.getDirectionVector(obj.x, obj.y, goalX, goalY)
			if DEBUG:
				print("Direction to go in:", dirX, dirY)

			return dirX, dirY
		adjacent = self.getAdjacent(objective, xBlock, yBlock, counter)
		lowest = self.grid.getDistanceValue(objective, xBlock, yBlock)
		if DEBUG:
			print("Currently situated on a block with distance", lowest)
		locationLowest = None
		for l in range(len(adjacent)):
			loc = adjacent[l]
			if self.grid.isUpdated(objective, loc[0], loc[1], counter):
				if self.grid.getDistanceValue(objective, loc[0], loc[1]) < lowest:
					lowest = self.grid.getDistanceValue(objective, loc[0], loc[1])
					locationLowest = [loc[0], loc[1]]
		if locationLowest == None:
			if DEBUG:
				print("No adjacent blocks with a lower value, staying still")
			return 0, 0
		else:
			if DEBUG:
				print("Found the next desired block", str(locationLowest))
			obj.nextDesiredBlockX = locationLowest[0]
			obj.nextDesiredBlockY = locationLowest[1]
			goalX = obj.nextDesiredBlockX * 32 + 8
			goalY = obj.nextDesiredBlockY * 32 + 8
			if DEBUG:
				print("Trying to get to", goalX, goalY, "from", obj.x, obj.y)
			dirX, dirY = self.getDirectionVector(obj.x, obj.y, goalX, goalY)
			if DEBUG:
				print("Direction to go in:", dirX, dirY)

			return dirX, dirY
			
	def getDirectionVector(self, x1, y1, x2, y2):
		dX = x2 - x1 # delta x
		dY = y2 - y1 # delta y
		distance = abs(dX) + abs(dY)

		if distance == 0:
			return 0, 0
		return dX / distance, dY / distance

	def RESIST(self, obj, x, y, ox, oy):
		if x >= 20 or y >= 15 or x < 0 or y < 0:
			return -1
		if self.grid.getType(x, y) != WALL_BLOCK and self.grid.getPassingValue(x, y) != None:
			tp = self.grid.getPassingValue(x, y)
			if ox != x and oy != y:
				tp = tp * DIAGONAL
		elif self.grid.getType(x, y) == WALL_BLOCK and self.grid.getPassingValue(x, y) != None:
			return -1
		else:
			print("The apocolypse has occurred") 
			return -1
		tpn = tp + self.grid.getDistanceValue(obj, ox, oy)
		return tpn

	def getAdjacent(self, o, x, y, counter): 
		points = []
		
		points.append([x, y-1]) # Order is important, diagonals come after
		points.append([x-1, y]) 
		points.append([x+1, y])
		points.append([x, y+1])

		if self.grid.getPassingValue(x, y - 1) > 0 and self.grid.getPassingValue(x + 1, y) > 0:
			points.append([x+1, y-1])

		if self.grid.getPassingValue(x, y - 1) > 0 and self.grid.getPassingValue(x - 1, y) > 0:
			points.append([x-1, y-1])

		if self.grid.getPassingValue(x, y + 1) > 0 and self.grid.getPassingValue(x + 1, y) > 0:
			points.append([x+1, y+1])

		if self.grid.getPassingValue(x, y + 1) > 0 and self.grid.getPassingValue(x - 1, y) > 0:
			points.append([x-1, y+1])

		for i in range(len(points)):
			if i >= len(points):
				continue
			passingValue = self.grid.getPassingValue(points[i][0], points[i][1])
			if points[i][0] < 0 or points[i][1] < 0 or points[i][0] >= self.grid.width or points[i][1] >= self.grid.height or passingValue == None or passingValue < 0 or x < 0 or y < 0 or x >= self.grid.width or y >= self.grid.height:
				points.pop(i)
				i = i - 1
		return points

# A basic objective with an x location, y location, and maximum
# radius of relevance
class Objective:
	def __init__(self, rad):
		self.radius = rad
		self.x = 0
		self.y = 0

# Holds necessary data for the WFEASearch
class WFEAObject:
	def __init__(self):
		self.x = 0
		self.y = 0
		self.width = 16
		self.height = 16
		self.lastUpdated = 0
		self.nextDesiredBlockX = -1
		self.nextDesiredBlockY = -1
		self.priority = 0

class Grid:
	def __init__(self, width, height):
		self.width = width
		self.height = height
		self.objectives = []
		self.grid_data = []
		for x in range(width):
			self.grid_data.append([])
			for y in range(height):
				newType = randrange(0, 101)
				if newType <= 12:
					self.grid_data[x].append(Block(WALL_BLOCK, []))
				else:
					self.grid_data[x].append(Block(GRASS_BLOCK, []))
	
	def addObjective(self, o): # o is an Objective
		self.objectives.append(o)
		index = len(self.objectives) - 1

		for x in range(self.width):
			for y in range(self.height):
				self.grid_data[x][y].objectiveData.append(ObjectiveData())

	def removeObjective(self, o): # o is an Objective
		index = self.objectives.index(o)
		self.objectives.pop(index)

		for x in range(self.width):
			for y in range(self.height):
				self.grid_data[x][y].objectiveData.pop(index)

	def getPassingValue(self, x, y): # x is an int, y is an int
		if x < 0 or y < 0 or x >= self.width or y >= self.height:
			return -2
		block = self.grid_data[x][y]

		if(block.mType == GRASS_BLOCK):
			return 10
		elif(block.mType == WALL_BLOCK):
			return -1
		else:
			return -2
		
	def getDistanceValue(self, o, x, y, counter): # o is an objective, x, y, and counter are ints
		index = self.objectives.index(o)
		objData = self.grid[x][y].objectiveData[index]
		if objData.lastUpdated != counter:
			return -1
		return objData.effortToObjective

	def getDistanceValue(self, o, x, y):
		index = self.objectives.index(o)
		objData = self.grid_data[x][y].objectiveData[index]
		return objData.effortToObjective
		
	def setDistanceValue(self, o, x, y, value, counter): # o is an objective, x, y, and counter are ints
		if x < 0 or y < 0 or x >= self.width or y >= self.height:
			return -9999999
		index = self.objectives.index(o)
		objData = self.grid_data[x][y].objectiveData[index] # errors
		objData.lastUpdated = counter
		objData.effortToObjective = value
		
	def isUpdated(self, o, x, y, counter): # o is an objective, x, y and counter are ints
		index = self.objectives.index(o)
		objData = self.grid_data[x][y].objectiveData[index]

		return objData.lastUpdated == counter
		
	def getType(self, x, y):
		return self.grid_data[x][y].mType
	def setType(self, x, y, newType):
		self.grid_data[x][y].mType = newType

class Block:
	def __init__(self, blockType, objectiveData):
		self.mType = blockType
		self.objectiveData = objectiveData

class ObjectiveData:
	def __init__(self):
		self.effortToObjective = 0
		self.lastUpdated = 0