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