Perimeter-based visibility.
[roguelike.git] / creature.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):