Package tdl :: Module map |
[frames] | no frames]

# Source Code for Module tdl.map

      1  """
      2      Rogue-like map utilitys such as line-of-sight, field-of-view, and path-finding.
      3
      4  """
      5
      6  import itertools as _itertools
      7  import math as _math
      8
      9  from tcod import ffi as _ffi
     10  from tcod import lib as _lib
     11
     12  import tdl as _tdl
     13  from . import style as _style
     14
     15  _FOVTYPES = {'BASIC' : 0, 'DIAMOND': 1, 'SHADOW': 2, 'RESTRICTIVE': 12, 'PERMISSIVE': 11}
     16
     17 -def _get_fov_type(fov):
     18      "Return a FOV from a string"
     19      oldFOV = fov
     20      fov = str(fov).upper()
     21      if fov in _FOVTYPES:
     22          return _FOVTYPES[fov]
     23      if fov[:10] == 'PERMISSIVE' and fov[10].isdigit() and fov[10] != '9':
     24          return 4 + int(fov[10])
     25      raise _tdl.TDLError('No such fov option as %s' % oldFOV)
     26
     27 -class Map(object):
     28      """Fast field-of-view and path-finding on stored data.
     29
     30      Set map conditions with the walkable and transparency attributes, this
     31      object can be iterated and checked for containment similar to consoles.
     32
     33      For example, you can set all tiles and transparent and walkable with the
     34      following code::
     35
     36          map = tdl.map.Map(80, 60)
     37          for x,y in map:
     38              map.transparent[x,y] = true
     39              map.walkable[x,y] = true
     40
     41      @ivar transparent: Map transparency, access this attribute with
     42                         map.transparent[x,y]
     43
     44                         Set to True to allow field-of-view rays, False will
     45                         block field-of-view.
     46
     47                         Transparent tiles only affect field-of-view.
     48
     49      @ivar walkable: Map accessibility, access this attribute with
     50                      map.walkable[x,y]
     51
     52                      Set to True to allow path-finding through that tile,
     53                      False will block passage to that tile.
     54
     55                      Walkable tiles only affect path-finding.
     56
     57      @ivar fov: Map tiles touched by a field-of-view computation,
     58                 access this attribute with map.fov[x,y]
     59
     60                 Is True if a the tile is if view, otherwise False.
     61
     62                 You can set to this attribute if you want, but you'll typically
     63                 be using it to read the field-of-view of a L{compute_fov} call.
     64
     65      @since: 1.5.0
     66      """
     67
     68 -    class _MapAttribute(object):
     69 -        def __init__(self, map, bit_index):
     70              self.map = map
     71              self.bit_index = bit_index
     72              self.bit = 1 << bit_index
     73              self.bit_inverse = 0xFF ^ self.bit
     74
     75 -        def __getitem__(self, key):
     76              return bool(self.map._array_cdata[key[1]][key[0]] & self.bit)
     77
     78 -        def __setitem__(self, key, value):
     79              self.map._array_cdata[key[1]][key[0]] = (
     80                  (self.map._array_cdata[key[1]][key[0]] & self.bit_inverse) |
     81                  (self.bit * bool(value))
     82                  )
     83
     84 -    def __init__(self, width, height):
     85          """Create a new Map with width and height.
     86
     87          @type width: int
     88          @type height: int
     89          @param width: Width of the new Map instance, in tiles.
     90          @param width: Height of the new Map instance, in tiles.
     91          """
     92          self.width = width
     93          self.height = height
     94          self._map_cdata = _lib.TCOD_map_new(width, height)
     95          # cast array into cdata format: uint8[y][x]
     96          # for quick Python access
     97          self._array_cdata = _ffi.new('uint8[%i][%i]' % (height, width))
     98          # flat array to pass to TDL's C helpers
     99          self._array_cdata_flat = _ffi.cast('uint8 *', self._array_cdata)
    100          self.transparent = self._MapAttribute(self, 0)
    101          self.walkable = self._MapAttribute(self, 1)
    102          self.fov = self._MapAttribute(self, 2)
    103
    104 -    def __del__(self):
    105          if self._map_cdata:
    106              _lib.TCOD_map_delete(self._map_cdata)
    107              self._map_cdata = None
    108
    109 -    def compute_fov(self, x, y, fov='PERMISSIVE', radius=None, light_walls=True,
    110                      sphere=True, cumulative=False):
    111          """Compute the field-of-view of this Map and return an iterator of the
    112          points touched.
    113
    114          @type x: int
    115          @type y: int
    116
    117          @param x: x center of the field-of-view
    118          @param y: y center of the field-of-view
    119          @type fov: string
    120          @param fov: The type of field-of-view to be used.  Available types are:
    121
    122                      'BASIC', 'DIAMOND', 'SHADOW', 'RESTRICTIVE', 'PERMISSIVE',
    123                      'PERMISSIVE0', 'PERMISSIVE1', ..., 'PERMISSIVE8'
    124          @type radius: int
    125          @param radius: Raduis of the field-of-view.
    126          @type light_walls: boolean
    127          @param light_walls: Include or exclude wall tiles in the field-of-view.
    128          @type sphere: boolean
    129          @param sphere: True for a spherical field-of-view.
    130                         False for a square one.
    131          @type cumulative: boolean
    132          @param cumulative:
    133
    134          @rtype: iter((x, y), ...)
    135          @return: An iterator of (x, y) points of tiles touched by the
    136                   field-of-view.
    137
    138                   Unexpected behaviour can happen if you modify the Map while
    139                   using the iterator.
    140
    141                   You can use the Map's fov attribute as an alternative to this
    142                   iterator.
    143          """
    144          # refresh cdata
    145          _lib.TDL_map_data_from_buffer(self._map_cdata,
    146                                        self._array_cdata_flat)
    147          if radius is None: # infinite radius
    148              radius = max(self.width, self.height)
    149          _lib.TCOD_map_compute_fov(self._map_cdata, x, y, radius, light_walls,
    150                                    _get_fov_type(fov))
    151          _lib.TDL_map_fov_to_buffer(self._map_cdata,
    152                                     self._array_cdata_flat, cumulative)
    153          def iterate_fov():
    154              _array_cdata = self._array_cdata
    155              for y in range(self.height):
    156                  for x in range(self.width):
    157                      if(_array_cdata[y][x] & 4):
    158                          yield (x, y)
    159          return iterate_fov()
    160
    161
    162
    163 -    def compute_path(self, start_x, start_y, dest_x, dest_y,
    164                       diagonal_cost=_math.sqrt(2)):
    165          """Get the shortest path between two points.
    166
    167          The start position is not included in the list.
    168
    169          @type diagnalCost: float
    170          @param diagnalCost: Multiplier for diagonal movement.
    171
    172                              Can be set to zero to disable diagonal movement
    173                              entirely.
    174          @rtype: [(x, y), ...]
    175          @return: Returns a the shortest list of points to get to the destination
    176                   position from the starting position
    177          """
    178          # refresh cdata
    179          _lib.TDL_map_data_from_buffer(self._map_cdata,
    180                                        self._array_cdata_flat)
    181          path_cdata = _lib.TCOD_path_new_using_map(self._map_cdata, diagonal_cost)
    182          try:
    183              _lib.TCOD_path_compute(path_cdata, start_x, start_y, dest_x, dest_y)
    184              x = _ffi.new('int *')
    185              y = _ffi.new('int *')
    186              length = _lib.TCOD_path_size(path_cdata)
    187              path = [None] * length
    188              for i in range(length):
    189                  _lib.TCOD_path_get(path_cdata, i, x, y)
    190                  path[i] = ((x[0], y[0]))
    191          finally:
    192              _lib.TCOD_path_delete(path_cdata)
    193          return path
    194
    195 -    def __iter__(self):
    196          return _itertools.product(range(self.width), range(self.height))
    197
    198 -    def __contains__(self, position):
    199          x, y = position
    200          return (0 <= x < self.width) and (0 <= y < self.height)
    201
    202
    203
    204 -class AStar(object):
    205      """A* pathfinder
    206
    207      Using this class requires a callback detailed in L{AStar.__init__}
    208
    209      @undocumented: getPath
    210      """
    211
    212      __slots__ = ('_as_parameter_', '_callback', '__weakref__')
    213
    214
    215
    216 -    def __init__(self, width, height, callback,
    217                   diagnalCost=_math.sqrt(2), advanced=False):
    218          """Create an A* pathfinder using a callback.
    219
    220          Before crating this instance you should make one of two types of
    221          callbacks:
    222           - A function that returns the cost to move to (x, y)
    223          or
    224           - A function that returns the cost to move between
    225             (destX, destY, sourceX, sourceY)
    226          If path is blocked the function should return zero or None.
    227          When using the second type of callback be sure to set advanced=True
    228
    229          @type width: int
    230          @param width: width of the pathfinding area in tiles
    231          @type height: int
    232          @param height: height of the pathfinding area in tiles
    233
    234          @type callback: function
    235          @param callback: A callback taking parameters depending on the setting
    236                           of 'advanced' and returning the cost of
    237                           movement for an open tile or zero for a
    238                           blocked tile.
    239
    240          @type diagnalCost: float
    241          @param diagnalCost: Multiplier for diagonal movement.
    242
    243                              Can be set to zero to disable diagonal movement
    244                              entirely.
    245
    246          @type advanced: boolean
    247          @param advanced: A simple callback with 2 positional parameters may not
    248                           provide enough information.  Setting this to True will
    249                           call the callback with 2 additional parameters giving
    250                           you both the destination and the source of movement.
    251
    252                           When True the callback will need to accept
    253                           (destX, destY, sourceX, sourceY) as parameters.
    254                           Instead of just (destX, destY).
    255
    256          """
    257          if not diagnalCost: # set None or False to zero
    258              diagnalCost = 0.0
    259          if advanced:
    260              def newCallback(sourceX, sourceY, destX, destY, null):
    261                  pathCost = callback(destX, destY, sourceX, sourceY)
    262                  if pathCost:
    263                      return pathCost
    264                  return 0.0
    265          else:
    266              def newCallback(sourceX, sourceY, destX, destY, null):
    267                  pathCost = callback(destX, destY) # expecting a float or 0
    268                  if pathCost:
    269                      return pathCost
    270                  return 0.0
    271          # float(int, int, int, int, void*)
    272          self._callback = _ffi.callback('TCOD_path_func_t')(newCallback)
    273
    274          self._as_parameter_ = _lib.TCOD_path_new_using_function(width, height,
    275                                       self._callback, _ffi.NULL, diagnalCost)
    276
    277 -    def __del__(self):
    278          if self._as_parameter_:
    279              _lib.TCOD_path_delete(self._as_parameter_)
    280              self._as_parameter_ = None
    281
    282 -    def get_path(self, origX, origY, destX, destY):
    283          """
    284          Get the shortest path from origXY to destXY.
    285
    286          @rtype: [(x, y), ...]
    287          @return: Returns a list walking the path from origXY to destXY.
    288                   This excludes the starting point and includes the destination.
    289
    290                   If no path is found then an empty list is returned.
    291          """
    292          found = _lib.TCOD_path_compute(self._as_parameter_, origX, origY, destX, destY)
    293          if not found:
    294              return [] # path not found
    295          x, y = _ffi.new('int *'), _ffi.new('int *')
    296          recalculate = True
    297          path = []
    298          while _lib.TCOD_path_walk(self._as_parameter_, x, y, recalculate):
    299              path.append((x[0], y[0]))
    300          return path
    301
    302 -def quick_fov(x, y, callback, fov='PERMISSIVE', radius=7.5, lightWalls=True, sphere=True):
    303      """All field-of-view functionality in one call.
    304
    305      Before using this call be sure to make a function, lambda, or method that takes 2
    306      positional parameters and returns True if light can pass through the tile or False
    307      for light-blocking tiles and for indexes that are out of bounds of the
    308      dungeon.
    309
    310      This function is 'quick' as in no hassle but can quickly become a very slow
    311      function call if a large radius is used or the callback provided itself
    312      isn't optimized.
    313
    314      Always check if the index is in bounds both in the callback and in the
    315      returned values.  These values can go into the negatives as well.
    316
    317      @type x: int
    318      @param x: x center of the field-of-view
    319      @type y: int
    320      @param y: y center of the field-of-view
    321      @type callback: function
    322      @param callback: This should be a function that takes two positional arguments x,y
    323                       and returns True if the tile at that position is transparent
    324                       or False if the tile blocks light or is out of bounds.
    325      @type fov: string
    326      @param fov: The type of field-of-view to be used.  Available types are:
    327
    328                  'BASIC', 'DIAMOND', 'SHADOW', 'RESTRICTIVE', 'PERMISSIVE',
    329                  'PERMISSIVE0', 'PERMISSIVE1', ..., 'PERMISSIVE8'
    330      @type radius: float
    331      @param radius: Raduis of the field-of-view.
    332
    333                     When sphere is True a floating point can be used to fine-tune
    334                     the range.  Otherwise the radius is just rounded up.
    335
    336                     Be careful as a large radius has an exponential affect on
    337                     how long this function takes.
    338      @type lightWalls: boolean
    339      @param lightWalls: Include or exclude wall tiles in the field-of-view.
    340      @type sphere: boolean
    341      @param sphere: True for a spherical field-of-view.  False for a square one.
    342
    343      @rtype: set((x, y), ...)
    344      @return: Returns a set of (x, y) points that are within the field-of-view.
    345      """
    346      trueRadius = radius
    347      radius = int(_math.ceil(radius))
    348      mapSize = radius * 2 + 1
    349      fov = _get_fov_type(fov)
    350
    351      setProp = _lib.TCOD_map_set_properties # make local
    352      inFOV = _lib.TCOD_map_is_in_fov
    353
    354      tcodMap = _lib.TCOD_map_new(mapSize, mapSize)
    355      try:
    356          # pass no.1, write callback data to the tcodMap
    357          for x_, y_ in _itertools.product(range(mapSize), range(mapSize)):
    358              pos = (x_ + x - radius,
    359                     y_ + y - radius)
    360              transparent = bool(callback(*pos))
    361              setProp(tcodMap, x_, y_, transparent, False)
    362
    363          # pass no.2, compute fov and build a list of points
    364          _lib.TCOD_map_compute_fov(tcodMap, radius, radius, radius, lightWalls, fov)
    365          touched = set() # points touched by field of view
    366          for x_, y_ in _itertools.product(range(mapSize), range(mapSize)):
    367              if sphere and _math.hypot(x_ - radius, y_ - radius) > trueRadius:
    368                  continue
    369              if inFOV(tcodMap, x_, y_):
    370                  touched.add((x_ + x - radius, y_ + y - radius))
    371      finally:
    372          _lib.TCOD_map_delete(tcodMap)
    373      return touched
    374
    375 -def bresenham(x1, y1, x2, y2):
    376      """
    377      Return a list of points in a bresenham line.
    378
    379      Implementation hastily copied from RogueBasin.
    380
    381      @return: Returns a list of (x, y) points, including both the start and
    382               endpoints.
    383      """
    384      points = []
    385      issteep = abs(y2-y1) > abs(x2-x1)
    386      if issteep:
    387          x1, y1 = y1, x1
    388          x2, y2 = y2, x2
    389      rev = False
    390      if x1 > x2:
    391          x1, x2 = x2, x1
    392          y1, y2 = y2, y1
    393          rev = True
    394      deltax = x2 - x1
    395      deltay = abs(y2-y1)
    396      error = int(deltax / 2)
    397      y = y1
    398      ystep = None
    399      if y1 < y2:
    400          ystep = 1
    401      else:
    402          ystep = -1
    403      for x in range(x1, x2 + 1):
    404          if issteep:
    405              points.append((y, x))
    406          else:
    407              points.append((x, y))
    408          error -= deltay
    409          if error < 0:
    410              y += ystep
    411              error += deltax
    412      # Reverse the list if the coordinates were reversed
    413      if rev:
    414          points.reverse()
    415      return points
    416
    417
    418  __all__ = [_var for _var in locals().keys() if _var[0] != '_']
    419
    420  quickFOV = _style.backport(quick_fov)
    421  AStar.getPath = _style.backport(AStar.get_path)
    422