Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Wavefront Expansion Algorithm

By: a guest on Jan 18th, 2013  |  syntax: Python  |  size: 9.44 KB  |  views: 144  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. from random import *
  2. import sys
  3. from copy import deepcopy
  4.  
  5. global GRASS_BLOCK
  6. global WALL_BLOCK
  7. global DIAGONAL
  8. global DEBUG
  9.  
  10. DEBUG = False
  11. DIAGONAL = 1.412
  12. GRASS_BLOCK = 0
  13. WALL_BLOCK = 101
  14.  
  15. # Sole class needed for use of the wavefront expansion algorithm.
  16. # Each frame where any objectives move or the map changes call
  17. # updateObjectivesPF(), and for each WFEAObject whose velocity is due
  18. # to be updated call getNextMovementVector"""
  19. class WFEASearch:
  20.         #grid = the Grid this search is in, objs = the objectives in a list
  21.         def __init__(self, grd, objs):
  22.                 self.grid = grd
  23.                 self.objectives = objs
  24.         # Adds an objective to the WFEA search. Linear increase in time/frame per
  25.         # objective,depending on the radius of the objective
  26.         def addObjective(self, obj):
  27.                 self.objectives.append(obj)
  28.        
  29.         # Removes an objective from the WFEA search
  30.         def removeObjective(self, obj):
  31.                 self.objectives.remove(obj)
  32.         # Updates the performance fields of each objective
  33.         def updateObjectivesPF(self, counter):
  34.                 for i in range(len(self.objectives)):
  35.                         o = self.objectives[i]
  36.                         radius = o.radius
  37.                         ox = o.x
  38.                         oy = o.y
  39.                         rad = 0
  40.                         self.grid.setDistanceValue(o, ox, oy, 0, counter)
  41.                        
  42.                         previousExpansion = [[o.x, o.y]] # The files that were marked in the
  43.                         # last loop
  44.                         currentExpansion = [] # The files that we are marking in this loop
  45.                         n = True
  46.                         while rad in range(radius):
  47.                                 lenMarked = len(previousExpansion)
  48.                                 for i in range(lenMarked):
  49.                                         ox = previousExpansion[i][0]
  50.                                         oy = previousExpansion[i][1]
  51.                                         points = self.getAdjacent(o, ox, oy, counter)
  52.                                         for i in range(len(points)):
  53.                                                 if points[i][0] >= self.grid.width or points[i][1] >= self.grid.height:
  54.                                                         continue
  55.                                                 resistance = self.RESIST(o, points[i][0], points[i][1], ox, oy)
  56.                                                 if not self.grid.isUpdated(o, points[i][0], points[i][1], counter):
  57.                                                         if resistance > 0:
  58.                                                                 self.grid.setDistanceValue(o, points[i][0], points[i][1], resistance, counter)
  59.                                                                 currentExpansion.append([points[i][0], points[i][1]])
  60.                                 rad = rad + 1
  61.                                 #print("End of radius", rad, "previousExpansion:", str(previousExpansion),
  62.                                 #       "currentExpansion:", str(currentExpansion))
  63.                                 previousExpansion = []
  64.                                 for temp in range(len(currentExpansion)):
  65.                                         previousExpansion.append(currentExpansion[temp])
  66.                                 currentExpansion = []
  67.                                
  68.  
  69.         # Checks the location of the WFEA object and returns a vector for the
  70.         # next location that the WFEA object should go. Normalized to [-1, 1]
  71.         # Objective and a WFEAObject
  72.         def getNextMovementVector(self, objective, obj, counter):
  73.                 if DEBUG:
  74.                         print("Checking next movement vector")
  75.                 xBlock = int(obj.x / 32)
  76.                 yBlock = int(obj.y / 32)
  77.                 if DEBUG:
  78.                         print("Object location:", xBlock, yBlock)
  79.  
  80.                 if xBlock == obj.nextDesiredBlockX and yBlock == obj.nextDesiredBlockY:
  81.                         obj.nextDesiredBlockX = -1
  82.                         obj.nextDesiredBlockY = -1
  83.                         if DEBUG:
  84.                                 print("Made it to the objective")
  85.                 elif counter - obj.lastUpdated > 50:
  86.                         obj.nextDesiredBlockX = -1
  87.                         obj.nextDesiredBlockY = -1
  88.                         if DEBUG:
  89.                                 print("Probably stuck")
  90.                 else:
  91.                         obj.lastUpdated = deepcopy(counter)
  92.                
  93.                 if obj.nextDesiredBlockX >= 0 and obj.nextDesiredBlockY >= 0:
  94.                         if DEBUG:
  95.                                 print("Next location already set")
  96.                         goalX = obj.nextDesiredBlockX * 32 + 8
  97.                         goalY = obj.nextDesiredBlockY * 32 + 8
  98.                         if DEBUG:
  99.                                 print("Trying to get to", goalX, goalY, "from", obj.x, obj.y)
  100.                         dirX, dirY = self.getDirectionVector(obj.x, obj.y, goalX, goalY)
  101.                         if DEBUG:
  102.                                 print("Direction to go in:", dirX, dirY)
  103.  
  104.                         return dirX, dirY
  105.                 adjacent = self.getAdjacent(objective, xBlock, yBlock, counter)
  106.                 lowest = self.grid.getDistanceValue(objective, xBlock, yBlock)
  107.                 if DEBUG:
  108.                         print("Currently situated on a block with distance", lowest)
  109.                 locationLowest = None
  110.                 for l in range(len(adjacent)):
  111.                         loc = adjacent[l]
  112.                         if self.grid.isUpdated(objective, loc[0], loc[1], counter):
  113.                                 if self.grid.getDistanceValue(objective, loc[0], loc[1]) < lowest:
  114.                                         lowest = self.grid.getDistanceValue(objective, loc[0], loc[1])
  115.                                         locationLowest = [loc[0], loc[1]]
  116.                 if locationLowest == None:
  117.                         if DEBUG:
  118.                                 print("No adjacent blocks with a lower value, staying still")
  119.                         return 0, 0
  120.                 else:
  121.                         if DEBUG:
  122.                                 print("Found the next desired block", str(locationLowest))
  123.                         obj.nextDesiredBlockX = locationLowest[0]
  124.                         obj.nextDesiredBlockY = locationLowest[1]
  125.                         goalX = obj.nextDesiredBlockX * 32 + 8
  126.                         goalY = obj.nextDesiredBlockY * 32 + 8
  127.                         if DEBUG:
  128.                                 print("Trying to get to", goalX, goalY, "from", obj.x, obj.y)
  129.                         dirX, dirY = self.getDirectionVector(obj.x, obj.y, goalX, goalY)
  130.                         if DEBUG:
  131.                                 print("Direction to go in:", dirX, dirY)
  132.  
  133.                         return dirX, dirY
  134.                        
  135.         def getDirectionVector(self, x1, y1, x2, y2):
  136.                 dX = x2 - x1 # delta x
  137.                 dY = y2 - y1 # delta y
  138.                 distance = abs(dX) + abs(dY)
  139.  
  140.                 if distance == 0:
  141.                         return 0, 0
  142.                 return dX / distance, dY / distance
  143.  
  144.         def RESIST(self, obj, x, y, ox, oy):
  145.                 if x >= 20 or y >= 15 or x < 0 or y < 0:
  146.                         return -1
  147.                 if self.grid.getType(x, y) != WALL_BLOCK and self.grid.getPassingValue(x, y) != None:
  148.                         tp = self.grid.getPassingValue(x, y)
  149.                         if ox != x and oy != y:
  150.                                 tp = tp * DIAGONAL
  151.                 elif self.grid.getType(x, y) == WALL_BLOCK and self.grid.getPassingValue(x, y) != None:
  152.                         return -1
  153.                 else:
  154.                         print("The apocolypse has occurred")
  155.                         return -1
  156.                 tpn = tp + self.grid.getDistanceValue(obj, ox, oy)
  157.                 return tpn
  158.  
  159.         def getAdjacent(self, o, x, y, counter):
  160.                 points = []
  161.                
  162.                 points.append([x, y-1]) # Order is important, diagonals come after
  163.                 points.append([x-1, y])
  164.                 points.append([x+1, y])
  165.                 points.append([x, y+1])
  166.  
  167.                 if self.grid.getPassingValue(x, y - 1) > 0 and self.grid.getPassingValue(x + 1, y) > 0:
  168.                         points.append([x+1, y-1])
  169.  
  170.                 if self.grid.getPassingValue(x, y - 1) > 0 and self.grid.getPassingValue(x - 1, y) > 0:
  171.                         points.append([x-1, y-1])
  172.  
  173.                 if self.grid.getPassingValue(x, y + 1) > 0 and self.grid.getPassingValue(x + 1, y) > 0:
  174.                         points.append([x+1, y+1])
  175.  
  176.                 if self.grid.getPassingValue(x, y + 1) > 0 and self.grid.getPassingValue(x - 1, y) > 0:
  177.                         points.append([x-1, y+1])
  178.  
  179.                 for i in range(len(points)):
  180.                         if i >= len(points):
  181.                                 continue
  182.                         passingValue = self.grid.getPassingValue(points[i][0], points[i][1])
  183.                         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:
  184.                                 points.pop(i)
  185.                                 i = i - 1
  186.                 return points
  187.  
  188. # A basic objective with an x location, y location, and maximum
  189. # radius of relevance
  190. class Objective:
  191.         def __init__(self, rad):
  192.                 self.radius = rad
  193.                 self.x = 0
  194.                 self.y = 0
  195.  
  196. # Holds necessary data for the WFEASearch
  197. class WFEAObject:
  198.         def __init__(self):
  199.                 self.x = 0
  200.                 self.y = 0
  201.                 self.width = 16
  202.                 self.height = 16
  203.                 self.lastUpdated = 0
  204.                 self.nextDesiredBlockX = -1
  205.                 self.nextDesiredBlockY = -1
  206.                 self.priority = 0
  207.  
  208. class Grid:
  209.         def __init__(self, width, height):
  210.                 self.width = width
  211.                 self.height = height
  212.                 self.objectives = []
  213.                 self.grid_data = []
  214.                 for x in range(width):
  215.                         self.grid_data.append([])
  216.                         for y in range(height):
  217.                                 newType = randrange(0, 101)
  218.                                 if newType <= 12:
  219.                                         self.grid_data[x].append(Block(WALL_BLOCK, []))
  220.                                 else:
  221.                                         self.grid_data[x].append(Block(GRASS_BLOCK, []))
  222.        
  223.         def addObjective(self, o): # o is an Objective
  224.                 self.objectives.append(o)
  225.                 index = len(self.objectives) - 1
  226.  
  227.                 for x in range(self.width):
  228.                         for y in range(self.height):
  229.                                 self.grid_data[x][y].objectiveData.append(ObjectiveData())
  230.  
  231.         def removeObjective(self, o): # o is an Objective
  232.                 index = self.objectives.index(o)
  233.                 self.objectives.pop(index)
  234.  
  235.                 for x in range(self.width):
  236.                         for y in range(self.height):
  237.                                 self.grid_data[x][y].objectiveData.pop(index)
  238.  
  239.         def getPassingValue(self, x, y): # x is an int, y is an int
  240.                 if x < 0 or y < 0 or x >= self.width or y >= self.height:
  241.                         return -2
  242.                 block = self.grid_data[x][y]
  243.  
  244.                 if(block.mType == GRASS_BLOCK):
  245.                         return 10
  246.                 elif(block.mType == WALL_BLOCK):
  247.                         return -1
  248.                 else:
  249.                         return -2
  250.                
  251.         def getDistanceValue(self, o, x, y, counter): # o is an objective, x, y, and counter are ints
  252.                 index = self.objectives.index(o)
  253.                 objData = self.grid[x][y].objectiveData[index]
  254.                 if objData.lastUpdated != counter:
  255.                         return -1
  256.                 return objData.effortToObjective
  257.  
  258.         def getDistanceValue(self, o, x, y):
  259.                 index = self.objectives.index(o)
  260.                 objData = self.grid_data[x][y].objectiveData[index]
  261.                 return objData.effortToObjective
  262.                
  263.         def setDistanceValue(self, o, x, y, value, counter): # o is an objective, x, y, and counter are ints
  264.                 if x < 0 or y < 0 or x >= self.width or y >= self.height:
  265.                         return -9999999
  266.                 index = self.objectives.index(o)
  267.                 objData = self.grid_data[x][y].objectiveData[index] # errors
  268.                 objData.lastUpdated = counter
  269.                 objData.effortToObjective = value
  270.                
  271.         def isUpdated(self, o, x, y, counter): # o is an objective, x, y and counter are ints
  272.                 index = self.objectives.index(o)
  273.                 objData = self.grid_data[x][y].objectiveData[index]
  274.  
  275.                 return objData.lastUpdated == counter
  276.                
  277.         def getType(self, x, y):
  278.                 return self.grid_data[x][y].mType
  279.         def setType(self, x, y, newType):
  280.                 self.grid_data[x][y].mType = newType
  281.  
  282. class Block:
  283.         def __init__(self, blockType, objectiveData):
  284.                 self.mType = blockType
  285.                 self.objectiveData = objectiveData
  286.  
  287. class ObjectiveData:
  288.         def __init__(self):
  289.                 self.effortToObjective = 0
  290.                 self.lastUpdated = 0