Initial AI implementation.
[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 copy(self):
73             return Room(pmap, y, x, h, w)
74
75         def tile_for(self, level, y, x):
76             """Return a new tile for location (y, x) on level.  Will be
77                called only on the room's interior, not its walls."""
78             return loc.Floor(level, y, x)
79
80         def place(self):
81             "Place a room, updating tilerooms and walls."
82             for i in xrange(self.y, self.y + self.h):
83                 for j in xrange(self.x, self.x + self.w):
84                     y_edge = (i == self.y or i == self.ymax)
85                     x_edge = (j == self.x or j == self.xmax)
86                     thistile = set([(i,j)])
87                     if y_edge and x_edge:
88                         # Remove any tip
89                         self.pmap.tips -= thistile
90                         pass
91                     elif y_edge or x_edge:
92                         # A wall.  If there is a tip here, place a door and
93                         # remove the tip.
94                         if (i,j) in self.pmap.tips:
95                             self.pmap.tips -= thistile
96                             self.pmap.doors |= thistile
97                         else:
98                             self.pmap.walls |= thistile
99                     else:
100                         # Interior; make it belong to this room, and make it
101                         # neither a wall nor a tip.
102                         self.pmap.tilerooms[(i,j)] = self
103                         self.pmap.walls -= thistile
104                         self.pmap.tips -= thistile
105                         self.pmap.corridors -= thistile
106             # Remove the link to the parent, since we don't need it any
107             # more.  This ensures that placed rooms do not generate circular
108             # references.
109             self.pmap = None
110         
111
112         def dispose(self):
113             """This Room is not going to be used.  Break the link to the
114                containing RoomMap, to avoid circular references."""
115             self.pmap = None
116
117     def __init__(self, height, width, nrooms, nstairs):
118         self.h, self.w = height, width
119         self.nrooms = nrooms
120
121         self.maxh = min(20, int(height // math.sqrt(nrooms)))
122         self.maxw = int(width // math.sqrt(nrooms))
123
124         # Tiles that are in a room
125         self.tilerooms = {}
126         # Doors we have added to a room
127         self.doors = set()
128         # Tiles that immediately adjoin a room or a 
129         self.walls = set()
130         # Floor tiles that make up a corridor
131         self.corridors = set()
132         # Tiles containing a stair (these are also in tilerooms).
133         self.stairs = set()
134
135         self.tips = set()
136         st_rooms = set(random.sample(xrange(nrooms), nstairs - 1))
137
138         # Place the first room randomly
139         rm = self.first_room()
140         rm.place()
141
142         rno = 0
143         while self.place_room() and rno <= nrooms:
144             rno += 1
145
146         stairposs = list(set(self.tilerooms.keys()) - self.stairs)
147         for loc in random.sample(stairposs, nstairs):
148             self.stairs.add(loc)
149         
150
151     def tile_for(self, level, y, x):
152         "Generate the Tile for location (y, x), in the given level."
153
154         if (y, x) in self.stairs:
155             return loc.Stair(level, y, x)
156         if (y, x) in self.tilerooms:
157             return self.tilerooms[(y, x)].tile_for(level, y, x)
158         elif (y, x) in self.corridors:
159             return loc.Floor(level, y, x)
160         elif (y, x) in self.doors:
161             return loc.Door(level, y, x, opened = True)
162         else:
163             return loc.Wall(level, y, x)
164
165     def depict(self):
166         "Print a map to stdout; for debugging purposes only."
167
168         import sys
169         sys.stdout.write(" ")
170         for x in xrange(0, self.w, 4):
171             sys.stdout.write("%3d " % x)
172         print
173         for y in xrange(0, self.h):
174             sys.stdout.write("%3d" % y)
175             for x in xrange(0, self.w):
176                 if (y, x) in self.stairs:
177                     sys.stdout.write(">")
178                 elif (y, x) in self.tilerooms:
179                     sys.stdout.write("R")
180                 elif (y, x) in self.corridors:
181                     sys.stdout.write("=")
182                 elif (y, x) in self.doors:
183                     sys.stdout.write("+")
184                 else:
185                     sys.stdout.write(" ")
186             print
187
188
189
190     def first_room(self):
191         """Construct and return, but do not place, the first room.  Since
192            nothing is on the map yet, it can be placed anywhere."""
193         rh = random.randint(4, self.maxh)
194         rw = random.randint(4, self.maxw)
195         ry = random.randint(0, self.h - rh)
196         rx = random.randint(0, self.w - rw)
197         return self.Room(self, ry, rx, rh, rw)
198
199     def place_corridor(self):
200         """Place a corridor beginning at a random wall and extending
201            a random distance in a straight line."""
202         # Get a list in random order, and iterate over that
203         walls = [ w for w in self.walls ]
204         random.shuffle(walls)
205
206         for w in walls:
207             if self.dig_corridor(w):
208                 return True
209         return False
210
211     def place_room(self):
212         # Try adding up to twenty corridors to place the room.
213         for attempt in xrange(0,100):
214             # Try each corridor tip until we find a good location.  We iterate
215             # over a copy of self.tips so we can modify the original set.
216             for (ty, tx) in self.tips.copy():
217                 fly, flx = self.adjacent_floor(ty, tx)
218
219                 (ry, rx, rh, rw) = self.fit_room(
220                         # Pick the square across the tip from the floor
221                         (ty, tx), (fly, flx))
222
223                 if rh >= 4 and rw >= 4:
224                     # Placing the room removes the tip from self.tips.
225                     rm = self.Room(self, ry, rx, rh, rw).place()
226                     return True
227                 else:
228                     self.tips.remove((ty, tx))
229             # We went through all the tips without finding space for a room.
230             if not self.place_corridor():
231                 # No room for a corridor either---give up.
232                 return False
233         # Give up
234         return False
235
236     def fit_room(self, (ry, rx), (wy, wx)):
237         last = [ ry, rx, 0, 0 ]
238         curr = [ ry, rx, 1, 1 ]
239         Y, X, H, W = range(4)
240         
241         def south():
242             last[:] = curr
243             curr[H] += 1
244
245         def north():
246             last[:] = curr
247             curr[Y] -= 1
248             curr[H] += 1
249         
250         def east():
251             last[:] = curr
252             curr[W] += 1
253         
254         def west():
255             last[:] = curr
256             curr[X] -= 1
257             curr[W] += 1
258
259         def clear():
260             cl = self.is_clear(*curr)
261             if not cl:
262                 curr[:] = last
263             return cl
264
265
266         if ry > wy:
267             grow_away, grow_left, grow_right = south, east, west
268         elif ry < wy:
269             grow_away, grow_left, grow_right = north, west, east
270         elif rx > wx:
271             grow_away, grow_left, grow_right = east, north, south
272         elif rx < wx:
273             grow_away, grow_left, grow_right = west, south, north
274        
275         # First, make sure it's big enough to be a room.
276         grow_away()
277         grow_away()
278         grow_left()
279         grow_right()
280         if not clear():
281             return [ ry, rx, 0, 0 ]
282
283         for attempt in xrange(min(self.maxh, self.maxw)):
284             grown = False
285             grow_away()
286             grown |= clear()
287
288             grow_left()
289             grown |= clear()
290
291             grow_right()
292             grown |= clear()
293
294             if not grown:
295                 break
296
297         return curr
298
299     def is_clear(self, y, x, h, w):
300         "Can this room be placed without disturbing other rooms/corridors?"
301         # Make sure it fits on the map
302         if y < 0 or x < 0 or y+h > self.h or x+w > self.w:
303             return False
304         walls = self.walls | self.doors
305         for i in xrange(y, y+h):
306             for j in xrange(x, x+w):
307
308                 # Make sure the tile is not already part of a room.
309                 if (i,j) in self.tilerooms or (i,j) in self.corridors:
310                     return False
311
312                 # If the tile is interior to the room, make sure it is not
313                 # a room or corridor's wall (or a door)
314                 if (i > y and i < y + h and j > x and j < x + w):
315                     if (i,j) in walls:
316                         return False
317         return True
318         
319
320     def is_floor(self, i, j):
321         return (i, j) in self.tilerooms or (i, j) in self.corridors
322
323     def adjacent_floor(self, y, x):
324         "Find a floor tile adjacent to (y, x)."
325
326         if y > 0 and self.is_floor(y - 1, x):
327             return (y - 1, x)
328         elif y < self.h-1 and self.is_floor(y + 1, x):
329             return (y + 1, x)
330         elif x > 0 and self.is_floor(y, x - 1):
331             return (y, x - 1)
332         elif x < self.w-1 and self.is_floor(y, x + 1):
333             return (y, x + 1)
334         
335         assert False, "No floor adjacent to wall (y, x)."
336
337     def in_range(self, y, x):
338         return y >= 0 and y < self.h and x >= 0 and x < self.w
339
340     def dig_corridor(self, (y, x)):
341         "Find the maximum length for a corridor beginning at wall (y,x)."
342
343         # Figure out the direction
344         fly, flx = self.adjacent_floor(y, x)
345         dy, dx = y - fly, x - flx
346
347
348         assert (dy or dx) and not (dy and dx), (
349                 "adjacent_floor ? (%d, %d) -> (%d, %d)" % (y, x, fly, flx))
350         
351         if dy:
352             def neighbors(y, x):
353                 return [ (y, j) for j in (x-1, x+1) if self.in_range(y, j) ]
354         else:
355             def neighbors(y, x):
356                 return [ (i, x) for i in (y-1, y+1) if self.in_range(i, x) ]
357
358         
359         i, j = y + dy, x + dx
360         length = 0
361         while self.in_range(i, j):
362             if self.is_floor(i, j):
363                 i -= dy
364                 j -= dx
365                 break
366             done = False
367             for (ny, nx) in neighbors(i, j):
368                 if self.is_floor(ny, nx):
369                     i -= dy
370                     j -= dx
371                     done = True
372                     break
373             if done:
374                 break
375
376             length += 1
377             if (i, j) in self.walls:
378                 break
379
380             i += dy
381             j += dx
382
383         if length < 2:
384             return False
385
386         length = int(random.randint(4, length**2) ** 0.5)
387
388         self.walls -= set(neighbors(y, x))
389         self.walls.remove((y, x))
390         self.doors.add((y, x))
391
392         for d in xrange (1, length):
393             cy, cx = y + d*dy, x + d*dx
394             self.walls ^= set(neighbors(cy, cx))
395             self.corridors.add((cy, cx))
396
397         fy, fx = y + length*dy, x + length*dx
398
399         self.walls -= set(neighbors(fy, fx))
400
401         if (fy, fx) in self.walls:
402             self.walls.remove((fy, fx))
403             self.doors.add((fy, fx))
404         else:
405             self.tips.add((fy, fx))
406
407         return True
408
409 class Level (object):
410     """Represents an area of the map comprising a contiguous rectangular
411        region of Tiles surrounded by an impassable boundary.  Levels may
412        be travelled between via transport points."""
413     __metaclass__ = cacher.FirstArg
414
415     gen_count = 0
416
417     @classmethod
418     def generate_id(cls):
419         cls.gen_count = cls.gen_count + 1
420         return 'gen%d' % (cls.gen_count,)
421
422     def __init__(self, lid=None, height=None, width=None, name=None):
423         self.active_tiles = set()
424         self.invalid_tiles = set()
425         self.important_repaints = set()
426         self.unconnected_stairs = set()
427         self.unconnected_drops = []
428         self.needs_full_repaint = True
429
430         if lid:
431             self.lid = lid
432             self.filename = "levels/%s.sav" % (lid,)
433             assert height == width == name == None, \
434                     "Level constructor specified more than just the filename"
435             self.load_file(open(self.filename, "r"))
436         else:
437             self.lid = self.generate_id()
438             self.filename = None
439             assert height and width
440             self.h = height
441             self.w = width
442             self.name = name or ""
443
444             if random.random() < 0.1:
445                 self.pick_tile = random.choice(
446                         (self.pick_tile_1, self.pick_tile))
447
448                 self.grid = [ [ self.activate(self.pick_tile(i,j))
449                     for j in xrange(self.w) ]
450                     for i in xrange(self.h) ]
451             else:
452                 self.make_room_map()
453
454         random.shuffle(self.unconnected_drops)
455
456         self.boardwin = curses.newwin(self.h + 1, self.w + 1)
457
458     def stair_unavailable(self, stair):
459         if stair in self.unconnected_stairs:
460             self.unconnected_stairs.remove(stair)
461     def stair_available(self, stair):
462         self.unconnected_stairs.add(stair)
463
464
465     def connect(self, rm1, rm2):
466         # pick nearer sides of each room
467         faces = (rm1.facing(rm2), rm2.facing(rm1))
468         (y1,x1) = rm1.add_door(faces[0])
469         (y2,x2) = rm2.add_door(faces[1])
470         
471         self.grid[y1][x1] = loc.Door(self, y1, x1)
472         self.grid[y2][x2] = loc.Door(self, y2, x2)
473
474         dy = y2 - y1
475         dx = x2 - x1
476
477         if faces[0] == 'r' and faces[1] == 'l':
478             # >V> or >^>
479             if dy:
480                 ydir = dy/abs(dy)
481             else:
482                 ydir = 0
483             ty = y1
484             for tx in xrange(x1+1, x2):
485                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
486                 if tx == (x1 + x2) // 2 and dy != 0:
487                     while ty != y2:
488                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
489                         ty = ty + ydir
490                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
491         elif faces[0] == 'l' and faces[1] == 'r':
492             # >V> or >^>
493             if dy:
494                 ydir = -dy/abs(dy)
495             else:
496                 ydir = 0
497             ty = y2
498             for tx in xrange(x2+1, x1):
499                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
500                 if tx == (x1 + x2) // 2 and dy != 0:
501                     while ty != y1:
502                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
503                         ty = ty + ydir
504                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
505         elif faces[0] == 'b' and faces[1] == 't':
506             # V>V or V<V
507             if dx:
508                 xdir = dx/abs(dx)
509             else:
510                 xdir = 0
511             tx = x1
512             for ty in xrange(y1+1, y2):
513                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
514                 if ty == (y1 + y2) // 2 and dx != 0:
515                     while tx != x2:
516                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
517                         tx = tx + xdir
518                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
519         elif faces[0] == 't' and faces[1] == 'b':
520             # ^>^ or ^<^
521             if dx:
522                 xdir = -dx/abs(dx)
523             else:
524                 xdir = 0
525             tx = x2
526             for ty in xrange(y2+1, y1):
527                 self.grid[ty][tx] = loc.Floor(self, ty, tx)
528                 if ty == (y1 + y2) // 2 and dx != 0:
529                     while tx != x1:
530                         self.grid[ty][tx] = loc.Floor(self, ty, tx)
531                         tx = tx + xdir
532                     self.grid[ty][tx] = loc.Floor(self, ty,tx)
533
534     def make_room_map(self, nrooms = 10, nstairs = 2):
535         """Make a nice map containing nrooms rooms, with two of those
536            rooms containing stairs."""
537
538         rm = RoomMap(self.h, self.w, nrooms, nstairs)
539
540         self.grid = [ [ self.activate(rm.tile_for(self, y, x))
541             for x in xrange(0, self.w) ]
542             for y in xrange(0, self.h) ]
543     
544     def activate(self, tile):
545         (y, x) = (tile.y, tile.x)
546         if tile.is_active():
547             self.active_tiles.add((y, x))
548         if isinstance(tile, loc.Stair) and not tile.target() and not tile.oneway:
549             self.stair_available(tile)
550         return tile
551
552     def load_file(self, f):
553         attrs = {}
554         def parse_line(line, lno):
555             linere = r'^(\d+)\s+(\d+)\s+(\w+)\s+(\w+)\s+(.*?)\s*\n$'
556             m = re.match(linere, line)
557             (y, x, attr, typ, valstr) = m.groups()
558             y = int(y) ; x = int(x)
559             if not 0 <= y < self.h:
560                 raise Exception("extra out of bounds: y=%d" % (y))
561             if not 0 <= x < self.w:
562                 raise Exception("extra out of bounds: x=%d" % (x))
563
564             val = None
565             if typ == "float":
566                 val = float(valstr)
567             elif typ == "int":
568                 val = int(valstr)
569             elif typ == "bool":
570                 val = valstr != "False"
571             elif typ == "str":
572                 val = valstr.strip()
573             elif typ == "level":
574                 val = LevelProxy(valstr.strip())
575             elif typ == "Loc":
576                 val = LocationProxy(locstr = valstr.strip())
577             else:
578                 raise Exception("unknown type %s (val '%s')" % (typ, valstr))
579             if (y,x) not in attrs:
580                 attrs[(y,x)] = {}
581             attrs[(y,x)][attr] = val
582
583         line = f.readline() ; lno = 1
584         if line.rstrip('\n') != "#!RgLkLvL":
585             raise Exception("Bad first line: '%s'" % (line))
586
587         line = f.readline() ; lno = 2
588
589         (hs, ws, name) = re.split("\\s+", line, 2)
590         self.h = int(hs)
591         self.w = int(ws)
592         self.name = name.rstrip('\n')
593
594         self.grid = [[None] * self.w for x in xrange(self.h)]
595
596         lines = []
597
598         first_lno = lno + 1
599         for i in range(self.h):
600             lines.append(f.readline())
601             lno = lno + 1
602
603         for l in f.readlines():
604             lno = lno + 1
605             parse_line(l, lno)
606
607         for i in range(self.h):
608             line = lines[i]
609             if len(line) != self.w + 1:
610                 raise Exception("incorrect line length: line %d = %d"
611                         % (first_lno + i, len(line)))
612             for j in range(self.w):
613                 if (i,j) in attrs:
614                     attr = attrs[(i,j)]
615                 else:
616                     attr = {}
617                 t = self.decode_tile(i, j, line[j], attr)
618                 self.grid[i][j] = self.activate(t)
619             if line[self.w] != '\n':
620                 raise Exception("line %d has no newline" % (i))
621
622
623         f.close()
624
625     def pick_tile_1(self, i, j):
626         if i == 15 and j == 60:
627             return loc.Stair(self, i, j)
628         elif (i-15)**2 + ((j-60)**2)/2 <= 36:
629             flowy = (j-60) / (math.sqrt(2) * 6) - (i-15)/(math.sqrt(2)*18)
630             flowx = (15-i) * math.sqrt(2) / 6 - (j-60)*math.sqrt(2)/18
631             return loc.Water(self, i, j, flowy, flowx)
632         elif 580 < (i-5)**2 + ((j-45)**2)/2 < 900:
633             flowy = (45-j) / (math.sqrt(2) * 27)
634             flowx = (i-5) * math.sqrt(2) / 27
635             return loc.Water(self, i, j, flowy, flowx)
636         elif random.random() < .1:
637             return loc.Wall(self, i, j)
638         else:
639             return loc.Floor(self, i, j, self.randitems())
640     
641     def pick_tile(self, i, j):
642         if i==0 or j==0 or i == self.h - 1 or j == self.w - 1:
643             return loc.Wall(self, i, j)
644         if (i == 5 and j == 9) or (i == self.h-5 and j == self.w - 10):
645             return loc.Stair(self, i, j)
646         if i % 9 == 0:
647             if (j == 9 and i % 18 == 0) or (j == self.w-10 and i % 18 == 9):
648                 return loc.Door(self, i, j)
649             else:
650                 return loc.Wall(self, i, j)
651         if j % 18 == 0:
652             if i % 9 == 4:
653                 return loc.Door(self, i, j)
654             else:
655                 return loc.Wall(self, i, j)
656         else:
657             return loc.Floor(self, i, j, self.randitems())
658
659     def get_target(self, oneway):
660         if oneway:
661             return self.unconnected_drops.pop()
662         else:
663             return self.unconnected_stairs.pop()
664
665     def invalidate(self, tile=None, important=False):
666         if tile == None:
667             self.needs_full_repaint = True
668         else:
669             assert tile.level() == self
670             self.invalid_tiles.add((tile.y, tile.x))
671             if important:
672                 self.important_repaints.add((tile.y, tile.x))
673
674     def decode_tile(self, i, j, char, attrs):
675         if char == "#":
676             return loc.Wall(self, i, j, **attrs)
677         elif char == " ":
678             return loc.Floor(self, i, j, self.randitems(), **attrs)
679         elif char == "~":
680             return loc.Water(self, i, j, **attrs)
681         elif char == "+":
682             return loc.Door(self, i, j, opened = False, **attrs)
683         elif char == "-":
684             return loc.Door(self, i, j, opened = True, **attrs)
685         elif char == ">":
686             return loc.Stair(self, i, j, **attrs)
687         elif char == "<":
688             # Target for one-way stairs
689             tile = loc.Floor(self, i, j, **attrs)
690             self.unconnected_drops.append(tile)
691             return tile
692         else:
693             raise Exception
694
695     def randitems(self):
696         r = 10000*random.random()
697         if r >= 100:
698             return []
699         elif r >= 50:
700             return [ thing.ItemClass("gold piece")() ]
701         elif r >= 20:
702             return [ thing.ItemClass("gem")() ]
703         elif r >= 10:
704             return [ thing.ItemClass("sword")() ]
705         elif r >= 2:
706             return [ thing.ItemClass("shield")() ]
707         else:
708             return [ thing.ItemClass("mask of water breathing")() ]
709
710     def loc(self, i, j):
711         return self.grid[i][j]
712
713     def clip(self, y, x):
714         if y<0:
715             y = 0
716         elif y >= self.h:
717             y = self.h-1
718         if x<0:
719             x = 0
720         elif x >= self.w:
721             x = self.w-1
722         return (y, x)
723
724     def players(self):
725         return (pl for pl in __main__.AppUI.instance.players if pl.level() == self)
726
727     def visible_path(self, py, px, oy, ox):
728         """Returns a list of coordinates that can be seen by (py,px) when
729            looking at (oy,ox)."""
730         (dy, dx) = (oy-py, ox-px)
731         if abs(dy) < 1 and abs(dx) < 1:
732             return (py, px)
733
734         path = []
735
736         # Go in the direction of the longer axis
737         flipped = abs(dy) > abs(dx)
738         if flipped:
739             (dy, dx) = (dx, dy)
740             (py, px) = (px, py)
741             (oy, ox) = (ox, oy)
742
743         if dx >= 0:
744             xinc = 1
745         else:
746             xinc = -1
747
748         # For each long-axis coordinate between p and o (inclusive):
749         for x in xrange(px, ox + xinc, xinc):
750             # Find the corresponding short-axis coordinate.
751             y = int(round(py + (x - px)*(float(dy)/dx)))
752
753             # Convert to real coordinates
754             if flipped:
755                 (ly, lx) = (x, y)
756             else:
757                 (ly, lx) = (y, x)
758
759             # This cell can be seen.
760             path.append((ly, lx))
761
762             # If it is opaque, no more cells can be seen.
763             if not self.loc(ly, lx).transparent():
764                 break
765         return path
766
767     # TODO: use dynamic programming: if we can't see a near tile, there is
768     # no reason to test the tiles behind it.
769     def draw(self):
770         if self.needs_full_repaint:
771             self.invalid_tiles = set((y,x) for y in range(self.h) for x in range(self.w))
772             self.needs_full_repaint = False
773         vis = set()
774         
775         for pl in self.players():
776             vis |= pl.visibles()
777
778         vis &= (self.invalid_tiles | self.active_tiles)
779         vis |= self.important_repaints
780         for (y,x) in vis:
781             (char, unic, color) = self.grid[y][x].render()
782             if appui.hasuni:
783                 self.boardwin.addwstr(y, x, unic, color)
784             else:
785                 self.boardwin.addstr(y, x, char, color)
786         self.invalid_tiles -= vis
787         self.important_repaints.clear()
788
789     def export(self):
790         extras = {}
791         f = StringIO()
792         f.write("#!RgLkLvL\n")
793         f.write("%d %d %s\n" % (self.h, self.w, self.name))
794         for i in range(self.h):
795             for j in range(self.w):
796                 tile = self.grid[i][j]
797                 (s, extra) = tile.export()
798                 f.write(s)
799                 if len(extra) > 0:
800                     extras[(i,j)] = extra
801             f.write("\n")
802         for ((y, x), ex) in extras.iteritems():
803             for (k,v) in ex.iteritems():
804                 f.write("%d %d %s %s %s\n" % (y, x, k, type(v).__name__, v))
805         val = f.getvalue()
806         f.close()
807         return val
808
809     def level(self):
810         return self
811
812     def creatures(self):
813         return [ creat 
814                 for y in range(self.h)
815                 for x in range(self.w)
816                 for creat in self.loc(y,x)._creatures ]
817
818     def affect_all(self):
819         for (y,x) in self.active_tiles:
820             self.grid[y][x].affect_all()
821
822
823 class LevelProxy (object):
824     def __init__(self, lid):
825         self.lid = lid
826         self.lvl = None
827
828     def level(self):
829         if not self.lvl:
830             self.lvl = Level(self.lid)
831         return self.lvl
832