pyrisk/graphics.py

   1 # Copyright (C) 2010 W. Trevor King <wking@drexel.edu>
   2 #
   3 # This program is free software; you can redistribute it and/or modify
   4 # it under the terms of the GNU General Public License as published by
   5 # the Free Software Foundation; either version 2 of the License, or
   6 # (at your option) any later version.
   7 #
   8 # This program is distributed in the hope that it will be useful,
   9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 # GNU General Public License for more details.
  12 #
  13 # You should have received a copy of the GNU General Public License along
  14 # with this program; if not, write to the Free Software Foundation, Inc.,
  15 # 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  16
  17 """Various PyRisk class -> graphic renderers.
  18
  19 Creates SVG files by hand.  See the TemplateLibrary class for a
  20 description of map specification format.
  21 """
  22
  23 import math
  24 import operator
  25 import os
  26 import os.path
  27
  28 from .base import NameMixin, ID_CmpMixin
  29
  30
  31 TEMPLATE_DIRS = [
  32     './templates',
  33     '~/share/pyrisk/templates',
  34     '/usr/share/pyrisk/templates/',
  35     ]
  36
  37 class Template (NameMixin):
  38     """Setup regions for a particular world.
  39     """
  40     def __init__(self, name, regions, continent_colors={},
  41                  line_colors={}, player_colors=[]):
  42         NameMixin.__init__(self, name)
  43         self.regions = regions
  44         self.continent_colors = continent_colors
  45         self.line_colors = line_colors
  46         self.player_colors = player_colors
  47
  48 class TemplateLibrary (object):
  49     """Create Templates on demand from a directory of template data.
  50
  51     TODO: explain template data format.
  52     """
  53     def __init__(self, template_dirs=None):
  54         if template_dirs == None:
  55             template_dirs = TEMPLATE_DIRS
  56         self.template_dirs = [os.path.abspath(os.path.expanduser(d))
  57                               for d in template_dirs]
  58     def get(self, name):
  59         region_pointlists,route_pointlists,continent_colors,line_colors, \
  60             player_colors = \
  61             self._get_data(name)
  62         regions = self._generate_regions(region_pointlists, route_pointlists)
  63         return Template(name, regions, continent_colors, line_colors,
  64                         player_colors)
  65     def _get_data(self, name):
  66         files = None
  67         for d in self.template_dirs:
  68             dirname = os.path.join(d, name.lower())
  69             try:
  70                 files = os.listdir(dirname)
  71                 break
  72             except IOError:
  73                 pass
  74         if files == None:
  75             return None
  76         region_pointlists = {}
  77         route_pointlists = {}
  78         for filename in files:
  79             path = os.path.join(dirname, filename)
  80             name,extension = filename.rsplit('.', 1)
  81             if extension == 'reg':
  82                 region_pointlists[name] = self._read_pointlist(path)
  83             elif extension in ['rt', 'vrt']:
  84                 route_pointlists[name] = (self._read_pointlist(path),
  85                                           extension == 'vrt')
  86             elif extension == 'col':
  87                 c = self._read_colors(path)
  88                 if name == 'continent':
  89                     continent_colors = c
  90                 elif name == 'line':
  91                     line_colors = c
  92                 else:
  93                     assert name == 'player', name
  94                     player_colors = []
  95                     for k,v in sorted(c.items()):
  96                         player_colors.append(v)
  97         return (region_pointlists, route_pointlists,
  98                 continent_colors, line_colors, player_colors)
  99     def _read_pointlist(self, filename):
 100         pointlist = []
 101         for line in open(filename, 'r'):
 102             line = line.strip()
 103             if len(line) == 0:
 104                 pointlist.append(None)
 105                 continue
 106             fields = line.split('\t')
 107             x = int(fields[0])
 108             y = -int(fields[1])
 109             if len(fields) == 3:
 110                 label = fields[2].strip()
 111             else:
 112                 label = None
 113             pointlist.append((x,y,label))
 114         return pointlist
 115     def _read_colors(self, filename):
 116         colors = {'_attributes': {}}
 117         for line in open(filename, 'r'):
 118             line = line.strip()
 119             if len(line) == 0:
 120                 continue
 121             fields = line.split('\t')
 122             name,value = [x.strip() for x in fields]
 123             if value == '-':
 124                 value = None
 125             if name.startswith('_'): # attribute setting
 126                 colors['_attributes'][name[1:]] = value
 127             else: # continent color
 128                 colors[name] = value
 129         return colors
 130     def _generate_regions(self, region_pointlists, route_pointlists):
 131         regions = []
 132         all_boundaries = []
 133         for name,pointlist in region_pointlists.items():
 134             boundaries,head_to_tail = self._pointlist_to_array_of_boundaries(
 135                 all_boundaries, pointlist)
 136             regions.append(Region(name, boundaries, head_to_tail))
 137             r = regions[-1]
 138         for name,v_pointlist in route_pointlists.items():
 139             pointlist,virtual = v_pointlist
 140             boundaries,head_to_tail = self._pointlist_to_array_of_boundaries(
 141                 all_boundaries, pointlist)
 142             assert len(boundaries) == 1, boundaries
 143             route = boundaries[0]
 144             route.virtual = virtual
 145             for terminal in [route[0], route[-1]]:
 146                 for r in regions:
 147                     for point in r.outline:
 148                         if hasattr(point, 'name') \
 149                                 and point.name == terminal.name:
 150                             r.routes.append(route)
 151                             r.route_head_to_tail.append(
 152                                 terminal == route[0])
 153                             route.regions.append(r)
 154         for r in regions:
 155             r.locate_routes()
 156         match_counts = [b.match_count for b in all_boundaries]
 157         assert min(match_counts) in [0, 1], set(match_counts)
 158         assert max(match_counts) == 1, set(match_counts)
 159         return regions
 160     def _pointlist_to_array_of_boundaries(self, all_boundaries, pointlist):
 161         boundaries = []
 162         head_to_tail = []
 163         b_points = []
 164         for i,point in enumerate(pointlist):
 165             if point == None:
 166                 boundary,reverse = self._analyze(b_points)
 167                 boundary = self._insert_boundary(all_boundaries, boundary)
 168                 boundaries.append(boundary)
 169                 head_to_tail.append(not reverse)
 170                 b_points = []
 171                 continue
 172             b_points.append(point)
 173         if len(b_points) > 0:
 174             boundary,reverse = self._analyze(b_points)
 175             boundary = self._insert_boundary(all_boundaries, boundary)
 176             boundaries.append(boundary)
 177             head_to_tail.append(not reverse)
 178         return boundaries, head_to_tail
 179     def _analyze(self, boundary_points):
 180         start = self._vbp(boundary_points[0])
 181         stop = self._vbp(boundary_points[-1])
 182         if stop < start:
 183             reverse = True
 184         points = [self._vbp(b) for b in boundary_points]
 185         reverse = start > stop
 186         if reverse == True:
 187             points.reverse()
 188             start,stop = (stop, start)
 189         boundary = Boundary([p-start for p in points])
 190         for bp,p in zip(boundary, points):
 191             bp.name = p.name # preserve point names
 192         boundary.name = '(%s) -> (%s)' % (start.name, stop.name)
 193         boundary.real_pos = start
 194         return (boundary, reverse)
 195     def _vbp(self, boundary_point):
 196         v = Vector((boundary_point[0], boundary_point[1]))
 197         v.name = boundary_point[2]
 198         return v
 199     def _insert_boundary(self, all_boundaries, new):
 200         if new in all_boundaries:
 201             return new
 202         for b in all_boundaries:
 203             if len(b) == len(new) and b.real_pos == new.real_pos:
 204                 match = True
 205                 for bp,np in zip(b, new):
 206                     if bp != np:
 207                         match = False
 208                         break
 209                 if match == True:
 210                     b.match_count += 1
 211                     return b
 212         all_boundaries.append(new)
 213         new.match_count = 0
 214         return new
 215
 216 TEMPLATE_LIBRARY = TemplateLibrary()
 217
 218
 219 class Vector (tuple):
 220     """Simple cartesian vector operations.
 221
 222     >>> v = Vector
 223     >>> a = v((0, 0))
 224     >>> b = v((1, 1))
 225     >>> c = v((2, 3))
 226     >>> a+b
 227     (1, 1)
 228     >>> a+b+c
 229     (3, 4)
 230     >>> b-c
 231     (-1, -2)
 232     >>> -c
 233     (-2, -3)
 234     >>> b*0.5
 235     (0.5, 0.5)
 236     >>> c*(1, -1)
 237     (2, -3)
 238     >>> a < b
 239     True
 240     >>> c > b
 241     True
 242     """
 243     def _set_name(self, new, other=None):
 244         if hasattr(self, 'name'):
 245             if self.name == None:
 246                 if hasattr(other, 'name'):
 247                     new.name = other.name
 248                     return
 249             new.name = self.name
 250         elif hasattr(other, 'name'):
 251             new.name = other.name
 252     def __neg__(self):
 253         new = self.__class__(map(operator.neg, self))
 254         self._set_name(new)
 255         return new
 256     def mag(self):
 257         """Return the magnitude.
 258         """
 259         return math.sqrt(sum([x**2 for x in self]))
 260     def angle(self):
 261         """Return the direction (must be in 2D).
 262         """
 263         if len(self) != 2:
 264             raise ValueError('length != 2, %s' % (self))
 265         return math.atan2(self[1], self[0])
 266     def __add__(self, other):
 267         if len(self) != len(other):
 268             raise ValueError('length missmatch %s, %s' % (self, other))
 269         new = self.__class__(map(operator.add, self, other))
 270         self._set_name(new, other)
 271         return new
 272     def __sub__(self, other):
 273         if len(self) != len(other):
 274             raise ValueError('length missmatch %s, %s' % (self, other))
 275         new = self.__class__(map(operator.sub, self, other))
 276         self._set_name(new, other)
 277         return new
 278     def __mul__(self, other):
 279         """Return the elementwise product (with vectors) or scalar
 280         product (with numbers).
 281         """
 282         if hasattr(other, '__iter__'): # dot product
 283             if len(self) != len(other):
 284                 raise ValueError('length missmatch %s, %s' % (self, other))
 285             new = self.__class__([s*o for s,o in zip(self, other)])
 286             #map(operator.mul, self, other))
 287         else: # scalar product
 288             new = self.__class__([x*other for x in self])
 289         self._set_name(new, other)
 290         return new
 291     def triple_angle(self, previous, next):
 292         """Return the angle between (previous->self) and (self->next)
 293         in radians.
 294         """
 295         angle = (next-self).angle() - (self-previous).angle()
 296         while angle > math.pi:
 297             angle -= 2*math.pi
 298         while angle < -math.pi:
 299             angle += 2*math.pi
 300         return angle
 301     def cross(self, other):
 302         """Return the cross product.
 303
 304         In 2D, just return the z component of the result.
 305         """
 306         if len(self) != len(other):
 307             raise ValueError('length missmatch %s, %s' % (self, other))
 308         if len(self) not in [2,3]:
 309             raise ValueError('cross product not defined in %dD, %s, %s'
 310                              % (len(self), self, other))
 311         if len(self) == 2:
 312             s = self.__class__((self[0], self[1], 0))
 313             o = self.__class__((other[0], other[1], 0))
 314         else:
 315             s = self; o = other
 316         new = self.__class__((s[1]*o[2]-s[2]*o[1],
 317                               -s[0]*o[2]-s[2]*o[0],
 318                               s[0]*o[1]-s[1]*o[0]))
 319         if len(self) == 2:
 320             return new[2]
 321         return new
 322
 323 def nameless(vector):
 324     """Return a nameless version of a given Vector.
 325
 326     Useful for ensuring the result of a sum / etc. has the name of the
 327     *other* vector.
 328     """
 329     return Vector(vector)
 330
 331 class Boundary (ID_CmpMixin, list):
 332     """Contains a list of points along the boundary.
 333
 334     All positions are relative to the location of the first point,
 335     which should therefore always be (0,0).
 336     """
 337     def __init__(self, points):
 338         list.__init__(self)
 339         ID_CmpMixin.__init__(self)
 340         for p in points:
 341             self.append(Vector(p))
 342         self.regions = []
 343         assert self[0] == (0,0), self
 344         self.x_min = min([p[0] for p in self])
 345         self.x_max = max([p[0] for p in self])
 346         self.y_min = min([p[1] for p in self])
 347         self.y_max = max([p[1] for p in self])
 348
 349 class Route (ID_CmpMixin):
 350     """Connect non-adjacent Regions.
 351     """
 352     def __init__(self, boundary):
 353         ID_CmpMixin.__init__(self)
 354         self.boundary = boundary
 355
 356 class Region (NameMixin, ID_CmpMixin, list):
 357     """Contains a list of boundaries and a label.
 358
 359     Regions can be Territories or pieces of Territories (e.g separate
 360     islands, such as in Indonesia).
 361
 362     Boundaries must be entered counter clockwise (otherwise you
 363     will get an error).
 364
 365     >>> r = Region('Earth',
 366     ...            [Boundary([(0,0), (10,0)]),
 367     ...             Boundary([(0,0), (0,10)]),
 368     ...             Boundary([(0,0), (10,0)]),
 369     ...             Boundary([(0,0), (0,10)])],
 370     ...            [True, True, False, False])
 371     >>> r.outline
 372     [(0, 0), (10, 0), (10, 10), (0, 10), (0, 0)]
 373     >>> r.area()
 374     100.0
 375     >>> r.center_of_mass()
 376     (5, 5)
 377     """
 378     def __init__(self, name, boundaries, head_to_tail, routes=None,
 379                  route_head_to_tail=None):
 380         NameMixin.__init__(self, name)
 381         list.__init__(self, boundaries)
 382         ID_CmpMixin.__init__(self)
 383         for boundary in self:
 384             boundary.regions.append(self)
 385         self.head_to_tail = head_to_tail
 386         self.routes = routes
 387         self.route_head_to_tail = route_head_to_tail
 388         if routes == None:
 389             assert route_head_to_tail == None
 390             self.routes = []
 391             self.route_head_to_tail = []
 392         self.route_starts = [] # set by .locate_routes
 393         self.generate_outline() # sets .outline, .starts
 394         self.x_min = min([b.x_min+s[0] for b,s in zip(self, self.starts)])
 395         self.x_max = max([b.x_max+s[0] for b,s in zip(self, self.starts)])
 396         self.y_min = min([b.y_min+s[1] for b,s in zip(self, self.starts)])
 397         self.y_max = max([b.y_max+s[1] for b,s in zip(self, self.starts)])
 398     def generate_outline(self):
 399         """Return a list of boundary points surrounding the region.
 400
 401         The main issue here is determining the proper border
 402         orientation for a CCW outline, which we do via a user-supplied
 403         list head_to_tail.
 404         """
 405         self.starts = []
 406         points = [Vector((0,0))]
 407         for boundary,htt in zip(self, self.head_to_tail):
 408             pos = points[-1]
 409             if htt == True:
 410                 assert boundary[0] == (0,0), boundary
 411                 new = boundary[1:]
 412             else:
 413                 pos -= nameless(boundary[-1])
 414                 new = reversed(boundary[:-1])
 415             pos = nameless(pos)
 416             self.starts.append(pos)
 417             for p in new:
 418                 points.append(pos+p)
 419         assert points[-1] == points[0], '%s: %s (not closed)' % (self, points)
 420         self.outline = points
 421         total_angle = 0
 422         for prev,p,next in self._unique_triples():
 423             total_angle += p.triple_angle(prev, next)
 424         assert abs(total_angle-2*math.pi) < 0.1, \
 425             "%s: %s (not CCW: %.2f)" % (self, points, total_angle)
 426     def locate_routes(self):
 427         self.route_starts = []
 428         for route,htt in zip(self.routes, self.route_head_to_tail):
 429             if htt:
 430                 anchor = route[0]
 431             else:
 432                 anchor = route[-1]
 433             for point in self.outline:
 434                 if hasattr(point, 'name') and point.name == anchor.name:
 435                     self.route_starts.append(point-nameless(anchor))
 436                     break
 437     def area(self):
 438         """Return the region's enclosed area as a float.
 439         """
 440         return sum([self._triangle_area(a,b,c) for a,b,c in self._triangles()])
 441     def center_of_mass(self):
 442         """Return a vector locating the region's center of mass.
 443
 444         Truncated to the lower-left pixel.
 445         """
 446         cas = []
 447         for a,b,c in self._triangles():
 448             cas.append((self._triangle_center_of_mass(a,b,c),
 449                         self._triangle_area(a,b,c)))
 450         m = sum([a for c,a in cas])
 451         average = Vector((int(sum([c[0]*a for c,a in cas])/m),
 452                           int(sum([c[1]*a for c,a in cas])/m)))
 453         return average
 454     def _unique_triples(self):
 455         """Iterate through consecutive triples (prev, p, next)
 456         for every unique point in self.outline.
 457         """
 458         unique = self.outline[:-1]
 459         assert len(unique) >= 3, \
 460             '%s: %s (< 3 unique points)' % (self, self.outline)
 461         for i,p in enumerate(unique):
 462             prev = unique[i-1]
 463             next = unique[(i+1)%len(unique)]
 464             yield (prev, p, next)
 465     def _triangles(self):
 466         """Iterate through CCW triangles composing the region.
 467
 468         >>> r = Region('Earth',
 469         ...            [Boundary([(0,0),(1,-1),(0,3),(-1,0),(0,0)])],
 470         ...            [True])
 471         >>> for triangle in r._triangles():
 472         ...     print triangle
 473         ((0, 0), (1, -1), (0, 3))
 474         ((-1, 0), (0, 0), (0, 3))
 475         """
 476         points = self.outline[:-1]
 477         while len(points) >= 3:
 478             for i,p in enumerate(points):
 479                 prev = points[i-1]
 480                 next = points[(i+1)%len(points)]
 481                 if p.triple_angle(prev, next) > 0:
 482                     break # found first CCW triangle
 483             points.remove(p) # drop the outer point
 484             yield (prev, p, next)
 485     def _triangle_area(self, a, b, c):
 486         """
 487         >>> r = Region('Earth',
 488         ...            [Boundary([(0,0), (1,0), (1,1), (0,0)])],
 489         ...            [True])
 490         >>> triangle = r.outline[:3]
 491         >>> triangle
 492         [(0, 0), (1, 0), (1, 1)]
 493         >>> r._triangle_area(*triangle)
 494         0.5
 495         """
 496         return abs(0.5 * (b-a).cross(c-a))
 497     def _triangle_center_of_mass(self, a, b, c):
 498         """
 499         >>> r = Region('Earth',
 500         ...            [Boundary([(0,0), (1,0.3), (0.5,1.2), (0,0)])],
 501         ...            [True])
 502         >>> triangle = r.outline[:3]
 503         >>> ['(%.2f, %.2f)' % x for x in triangle]
 504         ['(0.00, 0.00)', '(1.00, 0.30)', '(0.50, 1.20)']
 505         >>> r._triangle_center_of_mass(*triangle)
 506         (0.5, 0.5)
 507         """
 508         return (a+b+c)*(1/3.)
 509
 510 class WorldRenderer (object):
 511     def __init__(self, template_lib=None, line_width=2, buf=10, dpcm=50):
 512         self.template_lib = template_lib
 513         if self.template_lib == None:
 514             self.template_lib = TEMPLATE_LIBRARY
 515         self.buf = buf
 516         self.line_width = line_width
 517         self.dpcm = dpcm
 518         self.army_scale = 3
 519     def filename_and_mime_image_type(self, world):
 520         """Return suggestions for emailing the rendered object.
 521
 522         Returns (filename, subtype), where the MIME type is
 523         image/<subtype>.
 524         """
 525         return ('%s.svg' % world.name, 'svg+xml')
 526     def render(self, world, players):
 527         template = self.template_lib.get(world.name)
 528         if template == None:
 529             template = self._auto_template(world)
 530         return self.render_template(world, players, template)
 531     def render_template(self, world, players, template):
 532         region_pos,width,height = self._locate(template)
 533         lines = [
 534             '<?xml version="1.0" standalone="no"?>',
 535             '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"',
 536             '  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">',
 537             '<svg width="%.1fcm" height="%.1fcm" viewBox="0 0 %d %d"'
 538             % (float(width)/self.dpcm, float(height)/self.dpcm,
 539                width, height),
 540             '     xmlns="http://www.w3.org/2000/svg" version="1.1">',
 541             '<title>%s</title>' % template,
 542             '<desc>A PyRisk world snapshot</desc>',
 543            ]
 544         terr_regions = {}
 545         drawn_rts = {}
 546         for r in template.regions:
 547             t = self._matching_territory(world, r)
 548             if t.name in terr_regions:
 549                 terr_regions[t.name].append(r)
 550             else:
 551                 terr_regions[t.name] = [r]
 552             c_col = template.continent_colors[t.continent.name]
 553             if len(template.continent_colors['_attributes']) == 0:
 554                 c_col_attr = ''
 555             else:
 556                 attrs = template.continent_colors['_attributes'].items()
 557                 c_col_attr = ''.join([' %s="%s"' % (k,v) for k,v in attrs])
 558             if template.line_colors['border'] == None:
 559                 b_col_attr = ''
 560             else:
 561                 b_col_attr = ' stroke="%s" stroke-width="%d"' \
 562                     % (template.line_colors['border'], self.line_width)
 563             lines.extend([
 564                     '<polygon title="%s / %s / %s"'
 565                     % (t, t.player, t.armies),
 566                     '         fill="%s"%s%s' % (c_col, c_col_attr, b_col_attr),
 567                     '         points="%s" />'
 568                     % ' '.join(['%d,%d' % ((region_pos[id(r)]+p)
 569                                            *(1,-1) # svg y value increases down
 570                                            +(0,height)) # shift back into bbox
 571                                 for p in r.outline[:-1]])
 572                     ])
 573             for rt,rt_start in zip(r.routes, r.route_starts):
 574                 if id(rt) in drawn_rts:
 575                     continue
 576                 drawn_rts[id(rt)] = rt
 577                 if rt.virtual == True:
 578                     color = template.line_colors['virtual route']
 579                 else:
 580                     color = template.line_colors['route']
 581                 if color == None:
 582                     continue
 583                 lines.extend([
 584                         '<polyline stroke="%s" stroke-width="%d"'
 585                         % (color, self.line_width),
 586                         '         points="%s" />'
 587                         % ' '.join(['%d,%d' % ((region_pos[id(r)]+rt_start+p)
 588                                            *(1,-1) # svg y value increases down
 589                                            +(0,height)) # shift back into bbox
 590                                     for p in rt])
 591                         ])
 592         for t in world.territories():
 593             regions = terr_regions[t.name]
 594             center = self._territory_center(region_pos, regions)
 595             radius = self.army_scale*math.sqrt(t.armies)
 596             color = template.player_colors[players.index(t.player)]
 597             if color == None:
 598                 continue
 599             if template.line_colors['army'] == None:
 600                 b_col_attr = ''
 601             else:
 602                 b_col_attr = ' stroke="%s" stroke-width="%d"' \
 603                     % (template.line_colors['army'], self.line_width)
 604                 radius += self.line_width/2.
 605             lines.extend([
 606                     '<circle title="%s / %s / %s"' % (t, t.player, t.armies),
 607                     '         fill="%s"%s' % (color, b_col_attr),
 608                     '         cx="%d" cy="%d" r="%.1f" />'
 609                     % (center[0], center[1]*-1+height, radius),
 610                     ])
 611         lines.extend(['</svg>', ''])
 612         return '\n'.join(lines)
 613     def _locate(self, template):
 614         region_pos = {} # {id: absolute position, ...}
 615         boundary_pos = {} # {id: absolute position, ...}
 616         route_pos = {} # {id: absolute position, ...}
 617         b1 = template.regions[0][0]
 618         boundary_pos[id(b1)] = Vector((0,0)) # fix the first boundary point
 619         stack = [r for r in b1.regions]
 620         while len(stack) > 0:
 621             r = stack.pop()
 622             if id(r) in region_pos:
 623                 continue # skip duplicate entries
 624             r_start = None
 625             for b,rel_b_start in zip(r, r.starts):
 626                 if id(b) in boundary_pos:
 627                     b_start = boundary_pos[id(b)]
 628                     r_start = b_start - rel_b_start
 629                     break # found an anchor
 630             if r_start == None:
 631                 for rt,rel_rt_start in zip(r.routes, r.route_starts):
 632                     if id(rt) in route_pos:
 633                         rt_start = route_pos[id(rt)]
 634                         r_start = rt_start - rel_rt_start
 635                         break # found an anchor
 636             region_pos[id(r)] = r_start
 637             for b,rel_b_start in zip(r, r.starts):
 638                 if id(b) not in boundary_pos:
 639                     boundary_pos[id(b)] = r_start + rel_b_start
 640                     for r2 in b.regions:
 641                         stack.append(r2)
 642             for rt,rt_start in zip(r.routes, r.route_starts):
 643                 if id(rt) not in route_pos:
 644                     route_pos[id(rt)] = r_start + rt_start
 645                     for r2 in rt.regions:
 646                         stack.append(r2)
 647         for r in template.regions:
 648             if id(r) not in region_pos:
 649                 raise KeyError(r.name)
 650         x_min = min([r.x_min + region_pos[id(r)][0]
 651                      for r in template.regions]) - self.buf
 652         x_max = max([r.x_max + region_pos[id(r)][0]
 653                      for r in template.regions]) + self.buf
 654         y_min = min([r.y_min + region_pos[id(r)][1]
 655                      for r in template.regions]) - self.buf
 656         y_max = max([r.y_max + region_pos[id(r)][1]
 657                      for r in template.regions]) + self.buf
 658         for key,value in region_pos.items():
 659             region_pos[key] = value - Vector((x_min, y_min))
 660         return (region_pos, x_max-x_min, y_max-y_min)
 661     def _matching_territory(self, world, region):
 662         t = None
 663         try:
 664             t = world.territory_by_name(region.name)
 665         except KeyError:
 666             for rt in region.routes:
 667                 if not rt.virtual:
 668                     continue
 669                 for r in rt.regions:
 670                     try:
 671                         t = world.territory_by_name(r.name)
 672                     except KeyError:
 673                         pass
 674         assert t != None, 'No territory in %s associated with region %s' \
 675             % (world, region)
 676         return t
 677     def _territory_center(self, region_pos, regions):
 678         """Return the center of mass of a territory composed of regions.
 679         """
 680         cas = []
 681         for r in regions:
 682             center = r.center_of_mass() + region_pos[id(r)]
 683             area = r.area()
 684             cas.append((center, area))
 685         m = sum([a for c,a in cas])
 686         average = Vector((int(sum([c[0]*a for c,a in cas])/m),
 687                           int(sum([c[1]*a for c,a in cas])/m)))
 688         return average
 689     def _auto_template(self, world):
 690         raise NotImplementedError
 691
 692 def test():
 693     import doctest, sys
 694     failures,tests = doctest.testmod(sys.modules[__name__])
 695     return failures
 696
 697 def render_earth():
 698     from .base import generate_earth,Player,Engine
 699     players = [Player('Alice'), Player('Bob'), Player('Charlie'),
 700                Player('Eve'), Player('Mallory'), Player('Zoe')]
 701     world = generate_earth()
 702     e = Engine(world, players)
 703     e.setup()
 704     r = WorldRenderer()
 705     print r.render(e.world, players)