Wavefront Expansion Algorithm

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