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