Perimeter-based visibility.
authorNeil Moore <neil@s-z.org>
Thu, 5 Jun 2008 07:54:18 +0000 (03:54 -0400)
committerNeil Moore <neil@s-z.org>
Fri, 6 Jun 2008 08:13:51 +0000 (04:13 -0400)
Level.visible_path():
  Use a simpler loop with floating-point math, rather than Bresenham.
  Return the list of all visible coordinates along the path.

Creature.can_see():
  Adjust for change to visible_path.

Creature.visibles(): implement perimeter-based visibility testing
  Find the coordinates in the perimeter of the visibility radius (using
    Bresenham's circle algorithm).
  For each of these coordinates, compute the visible_path from me to
    there, and union it into the set of visible tiles.

creature.py
level.py

index e3c1bbb..52fb782 100644 (file)
@@ -55,19 +55,53 @@ class Creature(thing.Thing):
     def can_see(self, y, x):
         loc = self.location
         if (y - loc.y)**2 + (x - loc.x)**2 <= self.vis_radius()**2:
-            return self.level().visible_path(loc.y, loc.x, y, x)
+            return ((y, x) in self.level().visible_path(loc.y, loc.x, y, x))
         return False
+
     def visibles(self):
-        vis = []
+        "Return the set of coordinates I can see."
+        vis = set()
         py = self.location.y
         px = self.location.x
         rad = self.vis_radius()
-        (ymin,xmin) = self.level().clip(py - rad, px - rad)
-        (ymax,xmax) = self.level().clip(py + rad, px + rad)
-        for y in range(ymin, ymax+1):
-            for x in range(xmin, xmax+1):
-                if self.can_see(y,x):
-                    vis.append((y,x))
+        
+        
+        # Use Bresenham's circle-drawing algorithm to find the perimeter
+        # of the visibility circle.
+        
+        perimeter = set()
+
+        # Position of the current point relative to (py, px)
+        (ry, rx) = (rad, 0)
+        d = 3 - (2*rad)
+
+        path = self.level().visible_path
+        while rx <= ry:
+            # Map into all 8 octants: SSE, SSW, NNE, NNW, ESE, WSW, ENE, ENW
+            perimeter.add((py + ry, px + rx))
+            perimeter.add((py + ry, px - rx))
+            perimeter.add((py - ry, px + rx))
+            perimeter.add((py - ry, px - rx))
+            perimeter.add((py + rx, px + ry))
+            perimeter.add((py + rx, px - ry))
+            perimeter.add((py - rx, px + ry))
+            perimeter.add((py - rx, px - ry))
+
+            if d < 0:
+                d += (4*rx) + 6
+            else:
+                d += 4 * (rx - ry) + 10
+                ry -= 1
+            rx += 1
+
+        # Now raycast to each tile in the perimeter.  Each ray has max
+        # length ~(rad + 1), and there are ~(2 * PI * rad) coordinates in
+        # the perimeter.  Hence we will make a total of  ~(2 * PI* rad**2)
+        # visits (an average of two per in-radius tile).
+        clip = self.level().clip
+        for (y, x) in perimeter:
+            vis |= set(path(py, px, *clip(y, x)))
+
         return vis
 
     def is_creature(self):
index e6ec9ff..66259ea 100644 (file)
--- a/level.py
+++ b/level.py
@@ -452,37 +452,38 @@ class Level (object):
         return (pl for pl in __main__.AppUI.instance.players if pl.level() == self)
 
     def visible_path(self, py, px, oy, ox):
+        """Returns a list of coordinates that can be seen by (py,px) when
+        looking at (oy,ox)."""
         (dy, dx) = (oy-py, ox-px)
-        if abs(dy) <= 1 and abs(dx) <= 1:
-            return True
-        flipped = False
+        if abs(dy) < 1 and abs(dx) < 1:
+            return (py, px)
+
+        path = []
+
         # Go in the direction of the longer axis
-        if abs(dy) > abs(dx):
-            flipped = True
+        flipped = abs(dy) > abs(dx)
+        if flipped:
             (dy, dx) = (dx, dy)
             (py, px) = (px, py)
             (oy, ox) = (ox, oy)
 
         xinc = 1 if dx >= 0 else -1
-        yinc = 1 if dy >= 0 else -1
-        
-        einc = abs(float(dy)/dx)
-        err = einc - 1.0
 
-        y = py + (yinc if einc >= 0.5 else 0)
+        # For each long-axis coordinate between p and o (inclusive):
+        for x in xrange(px, ox + xinc, xinc):
+            # Find the corresponding short-axis coordinate.
+            y = int(round(py + (x - px)*(float(dy)/dx)))
 
-        for x in xrange(px + xinc, ox, xinc):
+            # Convert to real coordinates
             (ly, lx) = (x, y) if flipped else (y, x)
 
-            if not self.loc(ly, lx).transparent():
-                return False
-
-            err += einc
-            if err >= 0.5:
-                y += yinc
-                err -= 1.0
+            # This cell can be seen.
+            path.append((ly, lx))
 
-        return True
+            # If it is opaque, no more cells can be seen.
+            if not self.loc(ly, lx).transparent():
+                break
+        return path
 
     # TODO: use dynamic programming: if we can't see a near tile, there is
     # no reason to test the tiles behind it.
@@ -493,7 +494,7 @@ class Level (object):
         vis = set()
         
         for pl in self.players():
-            vis |= set(pl.visibles())
+            vis |= pl.visibles()
 
         vis &= (self.invalid_tiles | self.active_tiles)
         vis |= self.important_repaints