# Permissive Field of View in Python

From RogueBasin

(Difference between revisions)

m (I don't think category + subcategory are both needed at the same time.) |
m (Add link to Python.) |
||

Line 1: | Line 1: | ||

− | This is an implementation of the [[Precise Permissive Field of View]] algorithm in Python. | + | This is an implementation of the [[Precise Permissive Field of View]] algorithm in [[Python]]. |

The algorithm is contained in the module '''fov'''. The user calls the function '''fieldOfView()''', giving it an (x, y) coordinate, the width and height of the map, the view radius, and two functions which take (x, y) coordinates and either visits the coordinate for the user or test whether the coordinate blocks sight. | The algorithm is contained in the module '''fov'''. The user calls the function '''fieldOfView()''', giving it an (x, y) coordinate, the width and height of the map, the view radius, and two functions which take (x, y) coordinates and either visits the coordinate for the user or test whether the coordinate blocks sight. |

## Latest revision as of 18:10, 17 May 2017

This is an implementation of the Precise Permissive Field of View algorithm in Python.

The algorithm is contained in the module **fov**. The user calls the function **fieldOfView()**, giving it an (x, y) coordinate, the width and height of the map, the view radius, and two functions which take (x, y) coordinates and either visits the coordinate for the user or test whether the coordinate blocks sight.

""" Author: Aaron MacDonald Date: June 14, 2007 Description: An implementation of the precise permissive field of view algorithm for use in tile-based games. Based on the algorithm presented at http://roguebasin.roguelikedevelopment.org/ index.php?title= Precise_Permissive_Field_of_View. You are free to use or modify this code as long as this notice is included. This code is released without warranty. """ import copy def fieldOfView(startX, startY, mapWidth, mapHeight, radius, \ funcVisitTile, funcTileBlocked): """ Determines which coordinates on a 2D grid are visible from a particular coordinate. startX, startY: The (x, y) coordinate on the grid that is the centre of view. mapWidth, mapHeight: The maximum extents of the grid. The minimum extents are assumed to be both zero. radius: How far the field of view may extend in either direction along the x and y axis. funcVisitTile: User function that takes two integers representing an (x, y) coordinate. Is used to "visit" visible coordinates. funcTileBlocked: User function that takes two integers representing an (x, y) coordinate. Returns True if the coordinate blocks sight to coordinates "behind" it. """ visited = set() # Keep track of what tiles have been visited so # that no tile will be visited twice. # Will always see the centre. funcVisitTile(startX, startY) visited.add((startX, startY)) # Ge the dimensions of the actual field of view, making # sure not to go off the map or beyond the radius. if startX < radius: minExtentX = startX else: minExtentX = radius if mapWidth - startX - 1 < radius: maxExtentX = mapWidth - startX - 1 else: maxExtentX = radius if startY < radius: minExtentY = startY else: minExtentY = radius if mapHeight - startY - 1 < radius: maxExtentY = mapHeight - startY - 1 else: maxExtentY = radius # Northeast quadrant __checkQuadrant(visited, startX, startY, 1, 1, \ maxExtentX, maxExtentY, \ funcVisitTile, funcTileBlocked) # Southeast quadrant __checkQuadrant(visited, startX, startY, 1, -1, \ maxExtentX, minExtentY, \ funcVisitTile, funcTileBlocked) # Southwest quadrant __checkQuadrant(visited, startX, startY, -1, -1, \ minExtentX, minExtentY, \ funcVisitTile, funcTileBlocked) # Northwest quadrant __checkQuadrant(visited, startX, startY, -1, 1, \ minExtentX, maxExtentY, \ funcVisitTile, funcTileBlocked) #------------------------------------------------------------- class __Line(object): def __init__(self, xi, yi, xf, yf): self.xi = xi self.yi = yi self.xf = xf self.yf = yf dx = property(fget = lambda self: self.xf - self.xi) dy = property(fget = lambda self: self.yf - self.yi) def pBelow(self, x, y): return self.relativeSlope(x, y) > 0 def pBelowOrCollinear(self, x, y): return self.relativeSlope(x, y) >= 0 def pAbove(self, x, y): return self.relativeSlope(x, y) < 0 def pAboveOrCollinear(self, x, y): return self.relativeSlope(x, y) <= 0 def pCollinear(self, x, y): return self.relativeSlope(x, y) == 0 def lineCollinear(self, line): return self.pCollinear(line.xi, line.yi) \ and self.pCollinear(line.xf, line.yf) def relativeSlope(self, x, y): return (self.dy * (self.xf - x)) \ - (self.dx * (self.yf - y)) class __ViewBump: def __init__(self, x, y, parent): self.x = x self.y = y self.parent = parent class __View: def __init__(self, shallowLine, steepLine): self.shallowLine = shallowLine self.steepLine = steepLine self.shallowBump = None self.steepBump = None def __checkQuadrant(visited, startX, startY, dx, dy, \ extentX, extentY, funcVisitTile, funcTileBlocked): activeViews = [] shallowLine = __Line(0, 1, extentX, 0) steepLine = __Line(1, 0, 0, extentY) activeViews.append( __View(shallowLine, steepLine) ) viewIndex = 0 # Visit the tiles diagonally and going outwards # # . # . # . . # 9 . # 5 8 . # 2 4 7 # @ 1 3 6 . . . maxI = extentX + extentY i = 1 while i != maxI + 1 and len(activeViews) > 0: if 0 > i - extentX: startJ = 0 else: startJ = i - extentX if i < extentY: maxJ = i else: maxJ = extentY j = startJ while j != maxJ + 1 and viewIndex < len(activeViews): x = i - j y = j __visitCoord(visited, startX, startY, x, y, dx, dy, \ viewIndex, activeViews, \ funcVisitTile, funcTileBlocked) j += 1 i += 1 def __visitCoord(visited, startX, startY, x, y, dx, dy, viewIndex, \ activeViews, funcVisitTile, funcTileBlocked): # The top left and bottom right corners of the current coordinate. topLeft = (x, y + 1) bottomRight = (x + 1, y) while viewIndex < len(activeViews) \ and activeViews[viewIndex].steepLine.pBelowOrCollinear( \ bottomRight[0], bottomRight[1]): # The current coordinate is above the current view and is # ignored. The steeper fields may need it though. viewIndex += 1 if viewIndex == len(activeViews) \ or activeViews[viewIndex].shallowLine.pAboveOrCollinear( \ topLeft[0], topLeft[1]): # Either the current coordinate is above all of the fields # or it is below all of the fields. return # It is now known that the current coordinate is between the steep # and shallow lines of the current view. isBlocked = False # The real quadrant coordinates realX = x * dx realY = y * dy if (startX + realX, startY + realY) not in visited: visited.add((startX + realX, startY + realY)) funcVisitTile(startX + realX, startY + realY) """else: # Debugging print (startX + realX, startY + realY)""" isBlocked = funcTileBlocked(startX + realX, startY + realY) if not isBlocked: # The current coordinate does not block sight and therefore # has no effect on the view. return if activeViews[viewIndex].shallowLine.pAbove( \ bottomRight[0], bottomRight[1]) \ and activeViews[viewIndex].steepLine.pBelow( \ topLeft[0], topLeft[1]): # The current coordinate is intersected by both lines in the # current view. The view is completely blocked. del activeViews[viewIndex] elif activeViews[viewIndex].shallowLine.pAbove( \ bottomRight[0], bottomRight[1]): # The current coordinate is intersected by the shallow line of # the current view. The shallow line needs to be raised. __addShallowBump(topLeft[0], topLeft[1], \ activeViews, viewIndex) __checkView(activeViews, viewIndex) elif activeViews[viewIndex].steepLine.pBelow( \ topLeft[0], topLeft[1]): # The current coordinate is intersected by the steep line of # the current view. The steep line needs to be lowered. __addSteepBump(bottomRight[0], bottomRight[1], activeViews, \ viewIndex) __checkView(activeViews, viewIndex) else: # The current coordinate is completely between the two lines # of the current view. Split the current view into two views # above and below the current coordinate. shallowViewIndex = viewIndex viewIndex += 1 steepViewIndex = viewIndex activeViews.insert(shallowViewIndex, \ copy.deepcopy(activeViews[shallowViewIndex])) __addSteepBump(bottomRight[0], bottomRight[1], \ activeViews, shallowViewIndex) if not __checkView(activeViews, shallowViewIndex): viewIndex -= 1 steepViewIndex -= 1 __addShallowBump(topLeft[0], topLeft[1], activeViews, \ steepViewIndex) __checkView(activeViews, steepViewIndex) def __addShallowBump(x, y, activeViews, viewIndex): activeViews[viewIndex].shallowLine.xf = x activeViews[viewIndex].shallowLine.yf = y activeViews[viewIndex].shallowBump = __ViewBump(x, y, \ activeViews[viewIndex].shallowBump) curBump = activeViews[viewIndex].steepBump while curBump is not None: if activeViews[viewIndex].shallowLine.pAbove( \ curBump.x, curBump.y): activeViews[viewIndex].shallowLine.xi = curBump.x activeViews[viewIndex].shallowLine.yi = curBump.y curBump = curBump.parent def __addSteepBump(x, y, activeViews, viewIndex): activeViews[viewIndex].steepLine.xf = x activeViews[viewIndex].steepLine.yf = y activeViews[viewIndex].steepBump = __ViewBump(x, y, \ activeViews[viewIndex].steepBump) curBump = activeViews[viewIndex].shallowBump while curBump is not None: if activeViews[viewIndex].steepLine.pBelow( \ curBump.x, curBump.y): activeViews[viewIndex].steepLine.xi = curBump.x activeViews[viewIndex].steepLine.yi = curBump.y curBump = curBump.parent def __checkView(activeViews, viewIndex): """ Removes the view in activeViews at index viewIndex if - The two lines are coolinear - The lines pass through either extremity """ shallowLine = activeViews[viewIndex].shallowLine steepLine = activeViews[viewIndex].steepLine if shallowLine.lineCollinear(steepLine) \ and ( shallowLine.pCollinear(0, 1) \ or shallowLine.pCollinear(1, 0) ): del activeViews[viewIndex] return False else: return True