803c5393eb9bbebf19d8be7794d02cf5fc29ae1e
[roguelike.git] / level.py
1 #! /usr/bin/env python
2 # -*- coding: utf-8 -*-
3
4 # Copyright © 2008 Neil Moore <neil@s-z.org>.
5 #
6 # This program is free software; you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation; either version 2 of the License, or
9 # (at your option) any later version.
10 #
11 # This program is distributed in the hope that it will be useful,
12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 # GNU General Public License for more details.
15 #  
16 # You should have received a copy of the GNU General Public License
17 # along with this program; if not, write to the Free Software
18 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19
20 import curses
21 import random
22 import math
23 import re
24 from cStringIO import StringIO
25
26 import appui
27 import loc
28 import thing
29 import cacher
30 import __main__
31
32 class Loc (object):
33     def __init__(self, lid, y, x):
34
35         self.level = lid
36         self.y = y
37         self.x = x
38
39     def __str__(self):
40         return "%s %d %d" % (self.level, self.y, self.x)
41
42
43 class LocationProxy (object):
44     def __init__(self, level=None, y=None, x=None, locstr=None):
45         if locstr:
46             (lstr, ystr, xstr) = locstr.split(None, 2)
47             level = LevelProxy(lstr)
48             y = int(ystr)
49             x = int(xstr)
50         assert (level and y is not None and x is not None)
51         self.lvl = level
52         self.y = y
53         self.x = x
54
55     def as_loc(self):
56         return Loc(self.lvl.lid, self.y, self.x)
57
58     def level(self):
59         if isinstance(self.lvl, LevelProxy):
60             self.lvl = self.lvl.level()
61         return self.lvl
62
63     def location(self):
64         return self.level().loc(self.y, self.x)
65
66 class RoomMap (object):
67     class Room (object):
68         def __init__(self, pmap, y, x, h ,w):
69             self.pmap, self.y, self.x, self.h, self.w = pmap, y, x, h, w
70             self.ymax, self.xmax = y + h - 1, x + w - 1
71
72         def tile_for(self, level, y, x):
73             """Return a new tile for location (y, x) on level.  Will be
74                called only on the room's interior, not its walls."""
75             return loc.Floor(level, y, x)
76
77         def place(self):
78             "Place a room, updating tilerooms and walls."
79             for i in xrange(self.y, self.y + self.h):
80                 for j in xrange(self.x, self.x + self.w):
81                     y_edge = (i == self.y or i == self.ymax)
82                     x_edge = (j == self.x or j == self.xmax)
83                     if y_edge and x_edge:
84                         pass
85                     elif y_edge or x_edge:
86                         # A wall.  If there is a tip here, place a door.
87                         if (i,j) in self.pmap.tips:
88                             self.pmap.tips -= set([(i,j)])
89                             self.pmap.doors.add((i,j))
90                         else:
91                             self.pmap.walls.add((i,j))
92                     else:
93                         # Interior; make it a self, and make it neither a wall
94                         # nor a tip.
95                         self.pmap.tilerooms[(i,j)] = self
96                         s = set([(i,j)])
97                         self.pmap.tips -= s
98                         self.pmap.corridors -= s
99             # Remove the link to the parent, since we don't need it any
100             # more.  This ensures that placed rooms do not generate circular
101             # references.
102             self.pmap = None
103         
104         def is_clear(self):
105             "Can this room be placed without disturbing other rooms/corridors?"
106             nontip = self.pmap.corridors - self.pmap.tip
107             walls_corrs = self.pmap.walls | self.pmap.corridors
108             for i in xrange(self.y, self.ymax + 1):
109                 for j in xrange(self.x, self.xmax + 1):
110
111                     # Make sure the tile is not already part of a room.
112                     if (i,j) in self.pmap.tilerooms:
113                         return False
114
115                     # If the tile is interior to the room, make sure it is not
116                     # a wall or a corridor.
117                     if (i > y and i < y + h and j > x and j < x + w):
118                         if (i,j) in walls_corrs:
119                             return False
120                     else:
121                         # Make sure it's not a non-tip corridor
122                         if (i,j) in nontip:
123                             return False
124             return True
125
126         def dispose(self):
127             """This Room is not going to be used.  Break the link to the
128                containing RoomMap, to avoid circular references."""
129             self.pmap = None
130
131     def __init__(self, height, width, nrooms, nstairs):
132         self.h, self.w = height, width
133         self.nrooms = nrooms
134         # Tiles that are in a room
135         self.tilerooms = {}
136         # Doors we have added to a room
137         self.doors = set()
138         # Tiles that immediately adjoin a room or a 
139         self.walls = set()
140         # Floor tiles that make up a corridor
141         self.corridors = set()
142         # Tiles containing a stair (these are also in tilerooms).
143         self.stairs = set()
144
145         self.tips = set()
146         st_rooms = set(random.sample(xrange(nrooms), nstairs - 1))
147
148         # Place the first room randomly
149         rm = self.first_room()
150         rm.place()
151         sty = random.randint(rm.y+1, rm.ymax-1)
152         stx = random.randint(rm.x+1, rm.xmax-1)
153         self.stairs.add((sty, stx))
154
155         # For each room
156         for rno in xrange(1, nrooms):
157
158             # Approximately a 49% chance of one corridor, a 42% chance of
159             # two corridors, and a 8% chance of three.
160             self.place_corridor()
161             if random.random() < 0.3:
162                 self.place_corridor()
163             if random.random() < 0.3:
164                 self.place_corridor()
165
166             # Place a room at one of the tips
167             # rm = self.place_room()
168
169     def tile_for(self, level, y, x):
170         "Generate the Tile for location (y, x), in the given level."
171         if (y, x) in self.stairs:
172             return loc.Stair(level, y, x)
173         if (y, x) in self.tilerooms:
174             return self.tilerooms[(y, x)].tile_for(level, y, x)
175         elif (y, x) in self.corridors:
176             return loc.Floor(level, y, x)
177         elif (y, x) in self.doors:
178             return loc.Door(level, y, x)
179         else:
180             return loc.Wall(level, y, x)
181
182     def first_room(self):
183         """Construct and return, but do not place, the first room.  Since
184            nothing is on the map yet, it can be placed anywhere."""
185         rh = random.randint(4, self.h // (math.sqrt(self.nrooms)/1.5))
186         rw = random.randint(4, self.w // (math.sqrt(self.nrooms)/1.5))
187         ry = random.randint(0, self.h - rh)
188         rx = random.randint(0, self.w - rw)
189         return self.Room(self, ry, rx, rh, rw)
190
191     def place_corridor(self):
192         """Place a corridor beginning at a random wall and extending
193            a random distance in a straight line."""
194         walls = [ w for w in self.walls ]
195         random.shuffle(walls)
196
197         for w in walls:
198             if self.dig_corridor(w):
199                 break
200     def is_floor(self, i, j):
201         return (i, j) in self.tilerooms or (i, j) in self.corridors
202
203     def adjacent_floor(self, y, x):
204         "Find a floor tile adjacent to (y, x)."
205
206         if y > 0 and self.is_floor(y - 1, x):
207             return (y - 1, x)
208         elif y < self.h-1 and self.is_floor(y + 1, x):
209             return (y + 1, x)
210         elif x > 0 and self.is_floor(y, x - 1):
211             return (y, x - 1)
212         elif x < self.w-1 and self.is_floor(y, x + 1):
213             return (y, x + 1)
214         
215         assert False, "No floor adjacent to wall (y, x)."
216
217     def in_range(self, y, x):
218         return y >= 0 and y < self.h and x >= 0 and x < self.w
219
220     def dig_corridor(self, (y, x)):
221         "Find the maximum length for a corridor beginning at wall (y,x)."
222
223         # Figure out the direction
224         fly, flx = self.adjacent_floor(y, x)
225         dy, dx = y - fly, x - flx
226
227
228         assert (dy or dx) and not (dy and dx), (
229                 "diagonal probe? (%d, %d) -> (%d, %d)" % (y, x, fly, flx))
230         
231         if dy:
232             def neighbors(y, x):
233                 return [ (y, j) for j in (x-1, x+1) if self.in_range(y, j) ]
234         else:
235             def neighbors(y, x):
236                 return [ (i, x) for i in (y-1, y+1) if self.in_range(i, x) ]
237
238         
239         i, j = y + dy, x + dx
240         length = 0
241         while self.in_range(i, j):
242             if self.is_floor(i, j):
243                 i -= dy
244                 j -= dx
245                 break
246             done = False
247             for (ny, nx) in neighbors(i, j):
248                 if self.is_floor(ny, nx):
249                     i -= dy
250                     j -= dx
251                     done = True
252                     break
253             if done:
254                 break
255
256             length += 1
257             if (i, j) in self.walls:
258                 break
259
260             i += dy
261             j += dx
262
263         if length < 2:
264             return False
265
266         length = random.randint(2, length)
267
268         self.walls -= set(neighbors(y, x))
269         self.walls.remove((y, x))
270         self.doors.add((y, x))
271
272         for d in xrange (1, length):
273             cy, cx = y + d*dy, x + d*dx
274             self.walls ^= set(neighbors(cy, cx))
275             self.corridors.add((cy, cx))
276
277         fy, fx = y + length*dy, x + length*dx
278
279         self.walls -= set(neighbors(fy, fx))
280
281         if (fy, fx) in self.walls:
282             self.walls.remove((fy, fx))
283             self.doors.add((fy, fx))
284         else:
285             self.tips.add((fy, fx))
286
287         return True
288
289 class Level (object):
290     """Represents an area of the map comprising a contiguous rectangular
291        region of Tiles surrounded by an impassable boundary.  Levels may
292        be travelled between via transport points."""
293     __metaclass__ = cacher.FirstArg
294
295     gen_count = 0
296
297     @classmethod
298     def generate_id(cls):
299         cls.gen_count = cls.gen_count + 1
300         return 'gen%d' % (cls.gen_count,)
301
302     def __init__(self, lid=None, height=None, width=None, name=None):
303         self.active_tiles = set()
304         self.invalid_tiles = set()
305         self.important_repaints = set()
306         self.unconnected_stairs = set()
307         self.unconnected_drops = []
308         self.needs_full_repaint = True
309
310         if lid:
311             self.lid = lid
312             self.filename = "levels/%s.sav" % (lid,)
313             assert height == width == name == None, \
314                     "Level constructor specified more than just the filename"
315             self.load_file(open(self.filename, "r"))
316         else:
317             self.lid = self.generate_id()
318             self.filename = None
319             assert height and width
320             self.h = height
321             self.w = width
322             self.name = name or ""
323
324             if random.random() < 0.1:
325                 self.pick_tile = random.choice(
326                         (self.pick_tile_1, self.pick_tile))
327
328                 self.grid = [ [ self.activate(self.pick_tile(i,j))
329                     for j in xrange(self.w) ]
330                     for i in xrange(self.h) ]
331             else:
332                 self.make_room_map()
333
334         random.shuffle(self.unconnected_drops)
335
336         self.boardwin = curses.newwin(self.h + 1, self.w + 1)
337
338     def stair_unavailable(self, stair):
339         if stair in self.unconnected_stairs:
340             self.unconnected_stairs.remove(stair)
341     def stair_available(self, stair):
342         self.unconnected_stairs.add(stair)
343
344
345     def connect(self, rm1, rm2):
346         # pick nearer sides of each room
347         faces = (rm1.facing(rm2), rm2.facing(rm1))
348         (y1,x1) = rm1.add_door(faces[0])
349         (y2,x2) = rm2.add_door(faces[1])
350         
351         self.grid[y1][x1] = loc.Door(self, y1, x1)
352         self.grid[y2][x2] = loc.Door(self, y2, x2)
353
354         dy = y2 - y1
355         dx = x2 - x1
356
357         if faces[0] == 'r' and faces[1] == 'l':
358             # >V> or >^>
359             if dy:
360                 ydir = dy/abs(dy)
361             else:
362                 ydir = 0
363             ty = y1
364             for tx in xrange(x1+1, x2):
365                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
366                 if tx == (x1 + x2) // 2 and dy != 0:
367                     while ty != y2:
368                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
369                         ty = ty + ydir
370                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
371         elif faces[0] == 'l' and faces[1] == 'r':
372             # >V> or >^>
373             if dy:
374                 ydir = -dy/abs(dy)
375             else:
376                 ydir = 0
377             ty = y2
378             for tx in xrange(x2+1, x1):
379                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
380                 if tx == (x1 + x2) // 2 and dy != 0:
381                     while ty != y1:
382                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
383                         ty = ty + ydir
384                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
385         elif faces[0] == 'b' and faces[1] == 't':
386             # V>V or V<V
387             if dx:
388                 xdir = dx/abs(dx)
389             else:
390                 xdir = 0
391             tx = x1
392             for ty in xrange(y1+1, y2):
393                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
394                 if ty == (y1 + y2) // 2 and dx != 0:
395                     while tx != x2:
396                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
397                         tx = tx + xdir
398                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
399         elif faces[0] == 't' and faces[1] == 'b':
400             # ^>^ or ^<^
401             if dx:
402                 xdir = -dx/abs(dx)
403             else:
404                 xdir = 0
405             tx = x2
406             for ty in xrange(y2+1, y1):
407                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
408                 if ty == (y1 + y2) // 2 and dx != 0:
409                     while tx != x1:
410                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
411                         tx = tx + xdir
412                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
413
414     def make_room_map(self, nrooms = 10, nstairs = 2):
415         """Make a nice map containing nrooms rooms, with two of those
416            rooms containing stairs."""
417
418         rm = RoomMap(self.h, self.w, nrooms, nstairs)
419
420         self.grid = [ [ self.activate(rm.tile_for(self, y, x))
421             for x in xrange(0, self.w) ]
422             for y in xrange(0, self.h) ]
423     
424     def activate(self, tile):
425         (y, x) = (tile.y, tile.x)
426         if tile.is_active():
427             self.active_tiles.add((y, x))
428         if isinstance(tile, loc.Stair) and not tile.target() and not tile.oneway:
429             self.stair_available(tile)
430         return tile
431
432     def load_file(self, f):
433         attrs = {}
434         def parse_line(line, lno):
435             linere = r'^(\d+)\s+(\d+)\s+(\w+)\s+(\w+)\s+(.*?)\s*\n$'
436             m = re.match(linere, line)
437             (y, x, attr, typ, valstr) = m.groups()
438             y = int(y) ; x = int(x)
439             if not 0 <= y < self.h:
440                 raise Exception("extra out of bounds: y=%d" % (y))
441             if not 0 <= x < self.w:
442                 raise Exception("extra out of bounds: x=%d" % (x))
443
444             val = None
445             if typ == "float":
446                 val = float(valstr)
447             elif typ == "int":
448                 val = int(valstr)
449             elif typ == "bool":
450                 val = valstr != "False"
451             elif typ == "str":
452                 val = valstr.strip()
453             elif typ == "level":
454                 val = LevelProxy(valstr.strip())
455             elif typ == "Loc":
456                 val = LocationProxy(locstr = valstr.strip())
457             else:
458                 raise Exception("unknown type %s (val '%s')" % (typ, valstr))
459             if (y,x) not in attrs:
460                 attrs[(y,x)] = {}
461             attrs[(y,x)][attr] = val
462
463         line = f.readline() ; lno = 1
464         if line.rstrip('\n') != "#!RgLkLvL":
465             raise Exception("Bad first line: '%s'" % (line))
466
467         line = f.readline() ; lno = 2
468
469         (hs, ws, name) = re.split("\\s+", line, 2)
470         self.h = int(hs)
471         self.w = int(ws)
472         self.name = name.rstrip('\n')
473
474         self.grid = [[None] * self.w for x in xrange(self.h)]
475
476         lines = []
477
478         first_lno = lno + 1
479         for i in range(self.h):
480             lines.append(f.readline())
481             lno = lno + 1
482
483         for l in f.readlines():
484             lno = lno + 1
485             parse_line(l, lno)
486
487         for i in range(self.h):
488             line = lines[i]
489             if len(line) != self.w + 1:
490                 raise Exception("incorrect line length: line %d = %d"
491                         % (first_lno + i, len(line)))
492             for j in range(self.w):
493                 if (i,j) in attrs:
494                     attr = attrs[(i,j)]
495                 else:
496                     attr = {}
497                 t = self.decode_tile(i, j, line[j], attr)
498                 self.grid[i][j] = self.activate(t)
499             if line[self.w] != '\n':
500                 raise Exception("line %d has no newline" % (i))
501
502
503         f.close()
504
505     def pick_tile_1(self, i, j):
506         if i == 15 and j == 60:
507             return loc.Stair(self, i, j)
508         elif (i-15)**2 + ((j-60)**2)/2 <= 36:
509             flowy = (j-60) / (math.sqrt(2) * 6) - (i-15)/(math.sqrt(2)*18)
510             flowx = (15-i) * math.sqrt(2) / 6 - (j-60)*math.sqrt(2)/18
511             return loc.Water(self, i, j, flowy, flowx)
512         elif 580 < (i-5)**2 + ((j-45)**2)/2 < 900:
513             flowy = (45-j) / (math.sqrt(2) * 27)
514             flowx = (i-5) * math.sqrt(2) / 27
515             return loc.Water(self, i, j, flowy, flowx)
516         elif random.random() < .1:
517             return loc.Wall(self, i, j)
518         else:
519             return loc.Floor(self, i, j, self.randitems())
520     
521     def pick_tile(self, i, j):
522         if i==0 or j==0 or i == self.h - 1 or j == self.w - 1:
523             return loc.Wall(self, i, j)
524         if (i == 5 and j == 9) or (i == self.h-5 and j == self.w - 10):
525             return loc.Stair(self, i, j)
526         if i % 9 == 0:
527             if (j == 9 and i % 18 == 0) or (j == self.w-10 and i % 18 == 9):
528                 return loc.Door(self, i, j)
529             else:
530                 return loc.Wall(self, i, j)
531         if j % 18 == 0:
532             if i % 9 == 4:
533                 return loc.Door(self, i, j)
534             else:
535                 return loc.Wall(self, i, j)
536         else:
537             return loc.Floor(self, i, j, self.randitems())
538
539     def get_target(self, oneway):
540         if oneway:
541             return self.unconnected_drops.pop()
542         else:
543             return self.unconnected_stairs.pop()
544
545     def invalidate(self, tile=None, important=False):
546         if tile == None:
547             self.needs_full_repaint = True
548         else:
549             assert tile.level() == self
550             self.invalid_tiles.add((tile.y, tile.x))
551             if important:
552                 self.important_repaints.add((tile.y, tile.x))
553
554     def decode_tile(self, i, j, char, attrs):
555         if char == "#":
556             return loc.Wall(self, i, j, **attrs)
557         elif char == " ":
558             return loc.Floor(self, i, j, self.randitems(), **attrs)
559         elif char == "~":
560             return loc.Water(self, i, j, **attrs)
561         elif char == "+":
562             return loc.Door(self, i, j, opened = False, **attrs)
563         elif char == "-":
564             return loc.Door(self, i, j, opened = True, **attrs)
565         elif char == ">":
566             return loc.Stair(self, i, j, **attrs)
567         elif char == "<":
568             # Target for one-way stairs
569             tile = loc.Floor(self, i, j, **attrs)
570             self.unconnected_drops.append(tile)
571             return tile
572         else:
573             raise Exception
574
575     def randitems(self):
576         r = 10000*random.random()
577         if r >= 100:
578             return []
579         elif r >= 50:
580             return [ thing.ItemClass("gold piece")() ]
581         elif r >= 20:
582             return [ thing.ItemClass("gem")() ]
583         elif r >= 10:
584             return [ thing.ItemClass("sword")() ]
585         elif r >= 2:
586             return [ thing.ItemClass("shield")() ]
587         else:
588             return [ thing.ItemClass("mask of water breathing")() ]
589
590     def loc(self, i, j):
591         return self.grid[i][j]
592
593     def clip(self, y, x):
594         if y<0:
595             y = 0
596         elif y >= self.h:
597             y = self.h-1
598         if x<0:
599             x = 0
600         elif x >= self.w:
601             x = self.w-1
602         return (y, x)
603
604     def players(self):
605         return (pl for pl in __main__.AppUI.instance.players if pl.level() == self)
606
607     def visible_path(self, py, px, oy, ox):
608         """Returns a list of coordinates that can be seen by (py,px) when
609            looking at (oy,ox)."""
610         (dy, dx) = (oy-py, ox-px)
611         if abs(dy) < 1 and abs(dx) < 1:
612             return (py, px)
613
614         path = []
615
616         # Go in the direction of the longer axis
617         flipped = abs(dy) > abs(dx)
618         if flipped:
619             (dy, dx) = (dx, dy)
620             (py, px) = (px, py)
621             (oy, ox) = (ox, oy)
622
623         if dx >= 0:
624             xinc = 1
625         else:
626             xinc = -1
627
628         # For each long-axis coordinate between p and o (inclusive):
629         for x in xrange(px, ox + xinc, xinc):
630             # Find the corresponding short-axis coordinate.
631             y = int(round(py + (x - px)*(float(dy)/dx)))
632
633             # Convert to real coordinates
634             if flipped:
635                 (ly, lx) = (x, y)
636             else:
637                 (ly, lx) = (y, x)
638
639             # This cell can be seen.
640             path.append((ly, lx))
641
642             # If it is opaque, no more cells can be seen.
643             if not self.loc(ly, lx).transparent():
644                 break
645         return path
646
647     # TODO: use dynamic programming: if we can't see a near tile, there is
648     # no reason to test the tiles behind it.
649     def draw(self):
650         if self.needs_full_repaint:
651             self.invalid_tiles = set((y,x) for y in range(self.h) for x in range(self.w))
652             self.needs_full_repaint = False
653         vis = set()
654         
655         for pl in self.players():
656             vis |= pl.visibles()
657
658         vis &= (self.invalid_tiles | self.active_tiles)
659         vis |= self.important_repaints
660         for (y,x) in vis:
661             (char, unic, color) = self.grid[y][x].render()
662             if appui.hasuni:
663                 self.boardwin.addwstr(y, x, unic, color)
664             else:
665                 self.boardwin.addstr(y, x, char, color)
666         self.invalid_tiles -= vis
667         self.important_repaints.clear()
668
669     def export(self):
670         extras = {}
671         f = StringIO()
672         f.write("#!RgLkLvL\n")
673         f.write("%d %d %s\n" % (self.h, self.w, self.name))
674         for i in range(self.h):
675             for j in range(self.w):
676                 tile = self.grid[i][j]
677                 (s, extra) = tile.export()
678                 f.write(s)
679                 if len(extra) > 0:
680                     extras[(i,j)] = extra
681             f.write("\n")
682         for ((y, x), ex) in extras.iteritems():
683             for (k,v) in ex.iteritems():
684                 f.write("%d %d %s %s %s\n" % (y, x, k, type(v).__name__, v))
685         val = f.getvalue()
686         f.close()
687         return val
688
689     def level(self):
690         return self
691
692     def creatures(self):
693         return [ creat 
694                 for y in range(self.h)
695                 for x in range(self.w)
696                 for creat in self.loc(y,x)._creatures ]
697
698     def affect_all(self):
699         for (y,x) in self.active_tiles:
700             self.grid[y][x].affect_all()
701
702
703 class LevelProxy (object):
704     def __init__(self, lid):
705         self.lid = lid
706         self.lvl = None
707
708     def level(self):
709         if not self.lvl:
710             self.lvl = Level(self.lid)
711         return self.lvl
712