More room generation.
authorNeil Moore <neil@s-z.org>
Thu, 12 Jun 2008 03:28:51 +0000 (23:28 -0400)
committerNeil Moore <neil@s-z.org>
Thu, 12 Jun 2008 03:28:51 +0000 (23:28 -0400)
Split off Room class (nested in level.RoomMap).
  Move place and is_clear to Room.

level.RoomMap.tile_for (and helper Room.tile_for) to generate Tiles.

Add the first room randomly, then pick a wall and dig a corridor.
  To be done: place a room at a random corridor tip.

level.Level.make_room_map(): get tiles with tile_from; eliminate most
  of the code (moved to RoomMap).

level.py

index 57dfe01..803c539 100644 (file)
--- a/level.py
+++ b/level.py
@@ -64,7 +64,72 @@ class LocationProxy (object):
         return self.level().loc(self.y, self.x)
 
 class RoomMap (object):
-    def __init__(height, width, nrooms, nstairs):
+    class Room (object):
+        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 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."""
+            return loc.Floor(level, y, x)
+
+        def place(self):
+            "Place a room, updating tilerooms and walls."
+            for i in xrange(self.y, self.y + self.h):
+                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)
+                    if y_edge and x_edge:
+                        pass
+                    elif y_edge or x_edge:
+                        # A wall.  If there is a tip here, place a door.
+                        if (i,j) in self.pmap.tips:
+                            self.pmap.tips -= set([(i,j)])
+                            self.pmap.doors.add((i,j))
+                        else:
+                            self.pmap.walls.add((i,j))
+                    else:
+                        # Interior; make it a self, 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
+            # 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
+               containing RoomMap, to avoid circular references."""
+            self.pmap = None
+
+    def __init__(self, height, width, nrooms, nstairs):
+        self.h, self.w = height, width
         self.nrooms = nrooms
         # Tiles that are in a room
         self.tilerooms = {}
@@ -74,72 +139,157 @@ class RoomMap (object):
         self.walls = set()
         # Floor tiles that make up a corridor
         self.corridors = set()
+        # Tiles containing a stair (these are also in tilerooms).
+        self.stairs = set()
+
         self.tips = set()
-        st_rooms = set(random.sample(xrange(nrooms), nstairs))
-
-        for room in xrange(nrooms):
-            rm = self.find_room()
-            if self.is_clear(rm):
-                self.place(rno, rm)
-
-    def place(self, rno, (y, x, h, w)):
-        "Place a room, updating tilerooms and walls."
-        for i in xrange(y, y + h):
-            for j in xrange(x, x + w):
-                if (i == y or i == y+h-1) and (j == x or j == x+w-1):
-                    # Corner, do nothing
-                    pass
-                elif (i == y or i == y+h-1) or (j == x or j == x+w-1):
-                    # A wall.  If there is a corridor here, place a door.
-                    if (i,j) in self.corridors:
-                        self.tips -= set([(i,j)])
-                        self.doors.add((i,j))
-                    else:
-                        self.walls.add((i,j))
-                else:
-                    # Interior; make it a room, and make it neither a wall
-                    # nor a tip.
-                    self.tilerooms[(i,j)] = rno
-                    s = set([(i,j)])
-                    self.tips -= s
-                    self.corridors -= s
-
-
-    def is_clear(self, (y, x, h, w)):
-        "Can a room (y, x, h, w) be placed without disturbing other rooms?"
-        nontip = self.corridors - self.tip
-        walls_corrs = self.walls | self.corridors
-        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:
-                    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
+        st_rooms = set(random.sample(xrange(nrooms), nstairs - 1))
+
+        # 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):
+
+            # 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()
+
+    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:
+            return self.tilerooms[(y, x)].tile_for(level, y, x)
+        elif (y, x) in self.corridors:
+            return loc.Floor(level, y, x)
+        elif (y, x) in self.doors:
+            return loc.Door(level, y, x)
+        else:
+            return loc.Wall(level, y, x)
 
-    def find_room(self):
+    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(selfnrooms)/1.5))
+        rw = random.randint(4, self.w // (math.sqrt(self.nrooms)/1.5))
         ry = random.randint(0, self.h - rh)
         rx = random.randint(0, self.w - rw)
-        return (ry, rx, rh, rw)
+        return self.Room(self, ry, rx, rh, rw)
+
+    def place_corridor(self):
+        """Place a corridor beginning at a random wall and extending
+           a random distance in a straight line."""
+        walls = [ w for w in self.walls ]
+        random.shuffle(walls)
 
+        for w in walls:
+            if self.dig_corridor(w):
+                break
+    def is_floor(self, i, j):
+        return (i, j) in self.tilerooms or (i, j) in self.corridors
+
+    def adjacent_floor(self, y, x):
+        "Find a floor tile adjacent to (y, x)."
+
+        if y > 0 and self.is_floor(y - 1, x):
+            return (y - 1, x)
+        elif y < self.h-1 and self.is_floor(y + 1, x):
+            return (y + 1, x)
+        elif x > 0 and self.is_floor(y, x - 1):
+            return (y, x - 1)
+        elif x < self.w-1 and self.is_floor(y, x + 1):
+            return (y, x + 1)
         
+        assert False, "No floor adjacent to wall (y, x)."
+
+    def in_range(self, y, x):
+        return y >= 0 and y < self.h and x >= 0 and x < self.w
+
+    def dig_corridor(self, (y, x)):
+        "Find the maximum length for a corridor beginning at wall (y,x)."
+
+        # Figure out the direction
+        fly, flx = self.adjacent_floor(y, x)
+        dy, dx = y - fly, x - flx
+
+
+        assert (dy or dx) and not (dy and dx), (
+                "diagonal probe? (%d, %d) -> (%d, %d)" % (y, x, fly, flx))
+        
+        if dy:
+            def neighbors(y, x):
+                return [ (y, j) for j in (x-1, x+1) if self.in_range(y, j) ]
+        else:
+            def neighbors(y, x):
+                return [ (i, x) for i in (y-1, y+1) if self.in_range(i, x) ]
+
+        
+        i, j = y + dy, x + dx
+        length = 0
+        while self.in_range(i, j):
+            if self.is_floor(i, j):
+                i -= dy
+                j -= dx
+                break
+            done = False
+            for (ny, nx) in neighbors(i, j):
+                if self.is_floor(ny, nx):
+                    i -= dy
+                    j -= dx
+                    done = True
+                    break
+            if done:
+                break
+
+            length += 1
+            if (i, j) in self.walls:
+                break
+
+            i += dy
+            j += dx
+
+        if length < 2:
+            return False
+
+        length = random.randint(2, length)
+
+        self.walls -= set(neighbors(y, x))
+        self.walls.remove((y, x))
+        self.doors.add((y, x))
+
+        for d in xrange (1, length):
+            cy, cx = y + d*dy, x + d*dx
+            self.walls ^= set(neighbors(cy, cx))
+            self.corridors.add((cy, cx))
+
+        fy, fx = y + length*dy, x + length*dx
+
+        self.walls -= set(neighbors(fy, fx))
+
+        if (fy, fx) in self.walls:
+            self.walls.remove((fy, fx))
+            self.doors.add((fy, fx))
+        else:
+            self.tips.add((fy, fx))
+
+        return True
 
 class Level (object):
     """Represents an area of the map comprising a contiguous rectangular
-    region of Tiles surrounded by an impassable boundary.  Levels may
-    be travelled between via transport points.
-    """
+       region of Tiles surrounded by an impassable boundary.  Levels may
+       be travelled between via transport points."""
     __metaclass__ = cacher.FirstArg
 
     gen_count = 0
@@ -263,48 +413,13 @@ class Level (object):
 
     def make_room_map(self, nrooms = 10, nstairs = 2):
         """Make a nice map containing nrooms rooms, with two of those
-        rooms containing stairs.."""
+           rooms containing stairs."""
 
         rm = RoomMap(self.h, self.w, nrooms, nstairs)
-        st_rooms = set(random.sample(xrange(nrooms), nstairs))
-
-        for rno in xrange(nrooms):
-            rm = None
-
-            while not rm or any(orm & rm for orm in rooms):
-                rh = random.randint(4, self.h // (math.sqrt(nrooms)/1.5))
-                rw = random.randint(4, self.w // (math.sqrt(nrooms)/1.5))
-                ry = random.randint(0, self.h - rh)
-                rx = random.randint(0, self.w - rw)
-                rm = Room(ry, rx, rh, rw)
-
-            wet = random.random() < 0.1
-
-            rooms.append(rm)
-            for i in xrange(rm.y+1, rm.ymax):
-                for j in xrange(rm.x+1, rm.xmax):
-                    if rno in st_rooms and i == ry + rh//2 and j == rx + rw//2:
-                        self.grid[i][j] = loc.Stair(self, i, j)
-                    elif wet:
-                        self.grid[i][j] = loc.Water(self, i, j)
-                    else:
-                        self.grid[i][j] = loc.Floor(self, i, j)
-
-        for rno in xrange(1,nrooms):
-            if rno == 1 or random.random() < 0.8 :
-                nct = 1
-            else:
-                nct = 2
-            for tgt in random.sample(range(0, rno), nct):
-                self.connect(rooms[rno], rooms[tgt])
-        
-        self.grid = [ [ loc.Wall(self,i,j)
-            for j in xrange(self.w) ]
-            for i in xrange(self.h) ]
 
-        for row in self.grid:
-            for tile in row:
-                self.activate(tile)
+        self.grid = [ [ self.activate(rm.tile_for(self, y, x))
+            for x in xrange(0, self.w) ]
+            for y in xrange(0, self.h) ]
     
     def activate(self, tile):
         (y, x) = (tile.y, tile.x)
@@ -491,7 +606,7 @@ class Level (object):
 
     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)."""
+           looking at (oy,ox)."""
         (dy, dx) = (oy-py, ox-px)
         if abs(dy) < 1 and abs(dx) < 1:
             return (py, px)