Place multiple rooms and stairs.
authorNeil Moore <neil@s-z.org>
Sun, 15 Jun 2008 21:11:44 +0000 (17:11 -0400)
committerNeil Moore <neil@s-z.org>
Sun, 15 Jun 2008 21:11:44 +0000 (17:11 -0400)
level.py

index 803c539..41900a8 100644 (file)
--- a/level.py
+++ b/level.py
@@ -65,10 +65,13 @@ class LocationProxy (object):
 
 class RoomMap (object):
     class Room (object):
-        def __init__(self, pmap, y, x, h ,w):
+        def __init__(self, pmap, y, x, h, w):
             self.pmap, self.y, self.x, self.h, self.w = pmap, y, x, h, w
             self.ymax, self.xmax = y + h - 1, x + w - 1
 
+        def copy(self):
+            return Room(pmap, y, x, h, w)
+
         def tile_for(self, level, y, x):
             """Return a new tile for location (y, x) on level.  Will be
                called only on the room's interior, not its walls."""
@@ -80,48 +83,31 @@ class RoomMap (object):
                 for j in xrange(self.x, self.x + self.w):
                     y_edge = (i == self.y or i == self.ymax)
                     x_edge = (j == self.x or j == self.xmax)
+                    thistile = set([(i,j)])
                     if y_edge and x_edge:
+                        # Remove any tip
+                        self.pmap.tips -= thistile
                         pass
                     elif y_edge or x_edge:
-                        # A wall.  If there is a tip here, place a door.
+                        # A wall.  If there is a tip here, place a door and
+                        # remove the tip.
                         if (i,j) in self.pmap.tips:
-                            self.pmap.tips -= set([(i,j)])
-                            self.pmap.doors.add((i,j))
+                            self.pmap.tips -= thistile
+                            self.pmap.doors |= thistile
                         else:
-                            self.pmap.walls.add((i,j))
+                            self.pmap.walls |= thistile
                     else:
-                        # Interior; make it a self, and make it neither a wall
-                        # nor a tip.
+                        # Interior; make it belong to this room, and make it
+                        # neither a wall nor a tip.
                         self.pmap.tilerooms[(i,j)] = self
-                        s = set([(i,j)])
-                        self.pmap.tips -= s
-                        self.pmap.corridors -= s
+                        self.pmap.walls -= thistile
+                        self.pmap.tips -= thistile
+                        self.pmap.corridors -= thistile
             # Remove the link to the parent, since we don't need it any
             # more.  This ensures that placed rooms do not generate circular
             # references.
             self.pmap = None
         
-        def is_clear(self):
-            "Can this room be placed without disturbing other rooms/corridors?"
-            nontip = self.pmap.corridors - self.pmap.tip
-            walls_corrs = self.pmap.walls | self.pmap.corridors
-            for i in xrange(self.y, self.ymax + 1):
-                for j in xrange(self.x, self.xmax + 1):
-
-                    # Make sure the tile is not already part of a room.
-                    if (i,j) in self.pmap.tilerooms:
-                        return False
-
-                    # If the tile is interior to the room, make sure it is not
-                    # a wall or a corridor.
-                    if (i > y and i < y + h and j > x and j < x + w):
-                        if (i,j) in walls_corrs:
-                            return False
-                    else:
-                        # Make sure it's not a non-tip corridor
-                        if (i,j) in nontip:
-                            return False
-            return True
 
         def dispose(self):
             """This Room is not going to be used.  Break the link to the
@@ -131,6 +117,10 @@ class RoomMap (object):
     def __init__(self, height, width, nrooms, nstairs):
         self.h, self.w = height, width
         self.nrooms = nrooms
+
+        self.maxh = min(20, int(height // math.sqrt(nrooms)))
+        self.maxw = int(width // math.sqrt(nrooms))
+
         # Tiles that are in a room
         self.tilerooms = {}
         # Doors we have added to a room
@@ -148,26 +138,19 @@ class RoomMap (object):
         # Place the first room randomly
         rm = self.first_room()
         rm.place()
-        sty = random.randint(rm.y+1, rm.ymax-1)
-        stx = random.randint(rm.x+1, rm.xmax-1)
-        self.stairs.add((sty, stx))
 
-        # For each room
-        for rno in xrange(1, nrooms):
+        rno = 0
+        while self.place_room() and rno <= nrooms:
+            rno += 1
 
-            # Approximately a 49% chance of one corridor, a 42% chance of
-            # two corridors, and a 8% chance of three.
-            self.place_corridor()
-            if random.random() < 0.3:
-                self.place_corridor()
-            if random.random() < 0.3:
-                self.place_corridor()
-
-            # Place a room at one of the tips
-            # rm = self.place_room()
+        stairposs = list(set(self.tilerooms.keys()) - self.stairs)
+        for loc in random.sample(stairposs, nstairs):
+            self.stairs.add(loc)
+        
 
     def tile_for(self, level, y, x):
         "Generate the Tile for location (y, x), in the given level."
+
         if (y, x) in self.stairs:
             return loc.Stair(level, y, x)
         if (y, x) in self.tilerooms:
@@ -175,15 +158,40 @@ class RoomMap (object):
         elif (y, x) in self.corridors:
             return loc.Floor(level, y, x)
         elif (y, x) in self.doors:
-            return loc.Door(level, y, x)
+            return loc.Door(level, y, x, opened = True)
         else:
             return loc.Wall(level, y, x)
 
+    def depict(self):
+        "Print a map to stdout; for debugging purposes only."
+
+        import sys
+        sys.stdout.write(" ")
+        for x in xrange(0, self.w, 4):
+            sys.stdout.write("%3d " % x)
+        print
+        for y in xrange(0, self.h):
+            sys.stdout.write("%3d" % y)
+            for x in xrange(0, self.w):
+                if (y, x) in self.stairs:
+                    sys.stdout.write(">")
+                elif (y, x) in self.tilerooms:
+                    sys.stdout.write("R")
+                elif (y, x) in self.corridors:
+                    sys.stdout.write("=")
+                elif (y, x) in self.doors:
+                    sys.stdout.write("+")
+                else:
+                    sys.stdout.write(" ")
+            print
+
+
+
     def first_room(self):
         """Construct and return, but do not place, the first room.  Since
            nothing is on the map yet, it can be placed anywhere."""
-        rh = random.randint(4, self.h // (math.sqrt(self.nrooms)/1.5))
-        rw = random.randint(4, self.w // (math.sqrt(self.nrooms)/1.5))
+        rh = random.randint(4, self.maxh)
+        rw = random.randint(4, self.maxw)
         ry = random.randint(0, self.h - rh)
         rx = random.randint(0, self.w - rw)
         return self.Room(self, ry, rx, rh, rw)
@@ -191,12 +199,124 @@ class RoomMap (object):
     def place_corridor(self):
         """Place a corridor beginning at a random wall and extending
            a random distance in a straight line."""
+        # Get a list in random order, and iterate over that
         walls = [ w for w in self.walls ]
         random.shuffle(walls)
 
         for w in walls:
             if self.dig_corridor(w):
+                return True
+        return False
+
+    def place_room(self):
+        # Try adding up to twenty corridors to place the room.
+        for attempt in xrange(0,100):
+            # Try each corridor tip until we find a good location.  We iterate
+            # over a copy of self.tips so we can modify the original set.
+            for (ty, tx) in self.tips.copy():
+                fly, flx = self.adjacent_floor(ty, tx)
+
+                (ry, rx, rh, rw) = self.fit_room(
+                        # Pick the square across the tip from the floor
+                        (ty, tx), (fly, flx))
+
+                if rh >= 4 and rw >= 4:
+                    # Placing the room removes the tip from self.tips.
+                    rm = self.Room(self, ry, rx, rh, rw).place()
+                    return True
+                else:
+                    self.tips.remove((ty, tx))
+            # We went through all the tips without finding space for a room.
+            if not self.place_corridor():
+                # No room for a corridor either---give up.
+                return False
+        # Give up
+        return False
+
+    def fit_room(self, (ry, rx), (wy, wx)):
+        last = [ ry, rx, 0, 0 ]
+        curr = [ ry, rx, 1, 1 ]
+        Y, X, H, W = range(4)
+        
+        def south():
+            last[:] = curr
+            curr[H] += 1
+
+        def north():
+            last[:] = curr
+            curr[Y] -= 1
+            curr[H] += 1
+        
+        def east():
+            last[:] = curr
+            curr[W] += 1
+        
+        def west():
+            last[:] = curr
+            curr[X] -= 1
+            curr[W] += 1
+
+        def clear():
+            cl = self.is_clear(*curr)
+            if not cl:
+                curr[:] = last
+            return cl
+
+
+        if ry > wy:
+            grow_away, grow_left, grow_right = south, east, west
+        elif ry < wy:
+            grow_away, grow_left, grow_right = north, west, east
+        elif rx > wx:
+            grow_away, grow_left, grow_right = east, north, south
+        elif rx < wx:
+            grow_away, grow_left, grow_right = west, south, north
+       
+        # First, make sure it's big enough to be a room.
+        grow_away()
+        grow_away()
+        grow_left()
+        grow_right()
+        if not clear():
+            return [ ry, rx, 0, 0 ]
+
+        for attempt in xrange(min(self.maxh, self.maxw)):
+            grown = False
+            grow_away()
+            grown |= clear()
+
+            grow_left()
+            grown |= clear()
+
+            grow_right()
+            grown |= clear()
+
+            if not grown:
                 break
+
+        return curr
+
+    def is_clear(self, y, x, h, w):
+        "Can this room be placed without disturbing other rooms/corridors?"
+        # Make sure it fits on the map
+        if y < 0 or x < 0 or y+h > self.h or x+w > self.w:
+            return False
+        walls = self.walls | self.doors
+        for i in xrange(y, y+h):
+            for j in xrange(x, x+w):
+
+                # Make sure the tile is not already part of a room.
+                if (i,j) in self.tilerooms or (i,j) in self.corridors:
+                    return False
+
+                # If the tile is interior to the room, make sure it is not
+                # a room or corridor's wall (or a door)
+                if (i > y and i < y + h and j > x and j < x + w):
+                    if (i,j) in walls:
+                        return False
+        return True
+        
+
     def is_floor(self, i, j):
         return (i, j) in self.tilerooms or (i, j) in self.corridors
 
@@ -226,7 +346,7 @@ class RoomMap (object):
 
 
         assert (dy or dx) and not (dy and dx), (
-                "diagonal probe? (%d, %d) -> (%d, %d)" % (y, x, fly, flx))
+                "adjacent_floor ? (%d, %d) -> (%d, %d)" % (y, x, fly, flx))
         
         if dy:
             def neighbors(y, x):
@@ -263,7 +383,7 @@ class RoomMap (object):
         if length < 2:
             return False
 
-        length = random.randint(2, length)
+        length = int(random.randint(4, length**2) ** 0.5)
 
         self.walls -= set(neighbors(y, x))
         self.walls.remove((y, x))