Talk:Chariot Routes

I've modified the regions.jpg in an attempt to show chariot routes. Unfortunately, several of them are currently 1-way so the lines have arrows on them. If both directions are open it's like 2 arrows bumping up against eachother making a diamond shape. Um, the graphics are rudimentary & really not that good. Also, just from looking at the thumbnail, I can tell it's not always so easy to see the arrows. But for a first draft, it's better than nothing. If anyone has any suggestions or comments, feel free to leave them here or change the image. amisibastet 21:25, 23 December 2008 (EST)

Route table calculation

Here, more or less, is the code I used to generate the route table. Feel free to modify and rerun it as needed.

import cStringIO
import csv
import math
import sys


chariots_csv = """\
Adn,Adn,1029,6958
Cat's Claw Ridge,CCR,-403,6586
Falcon Bay,FB,4292,-632
Khmun,KHM,-2092,480
Meroe,MR,826,-3654
Nomad's Paradise,NP,-1419,2769
Pyramid Lake,PL,4286,7264
Queen's Retreat,QR,584,-6145
Saqqarah,SQ,640,-760
Shabbat Ab,SA,1419,1794
Sinai,SI,3205,4357
Stillwater,SW,1696,3718"""


routenames = [
  ("Cat's Claw Ridge", "Adn"),
  ("Cat's Claw Ridge", "Nomad's Paradise"),
  ("Adn", "Pyramid Lake"),
  ("Adn", "Sinai"),
  ("Adn", "Stillwater"),
  ("Pyramid Lake", "Sinai"),
  ("Nomad's Paradise", "Stillwater"),
  ("Nomad's Paradise", "Shabbat Ab"),
  ("Sinai", "Falcon Bay"),
  ("Stillwater", "Shabbat Ab"),
  ("Shabbat Ab", "Khmun"),
  ("Shabbat Ab", "Falcon Bay"),
  ("Khmun", "Meroe"),
  ("Saqqarah", "Meroe"),
  ("Saqqarah", "Queen's Retreat"),
  ("Falcon Bay", "Meroe"),
  ("Meroe", "Queen's Retreat")
]


class ChariotStop(object):
  def __init__(self, name, shortname, x, y):
    self.name = name
    self.shortname = shortname
    self.x = int(x)
    self.y = int(y)
  
  def getDistance(self, other):
    return math.sqrt((self.x-other.x)**2 + (self.y-other.y)**2)


def createRoutes(stops, routenames):
  routes = {}
  for src, dest in routenames:
    src_stop = stops[src]
    dest_stop = stops[dest]
    routes.setdefault(src_stop, set()).add(dest_stop)
    routes.setdefault(dest_stop, set()).add(src_stop)
  return routes


def calculateDistances(routes):
  distances = {}
  frontier = []
  
  # Populate frontier
  for src, dests in routes.iteritems():
    for dest in dests:
      distance = src.getDistance(dest)
      frontier.append((src, dest, distance, None))
      distances[(src, dest)] = (distance, None)
  
  while frontier:
    src, dest, distance, via = frontier.pop()
    for newdest in routes[dest]:
      leg = (src, newdest)
      cost = distance + dest.getDistance(newdest)
      if cost < distances.get(leg, (sys.maxint, None))[0]:
        if not via:
          via = dest
        distances[leg] = (cost, via)
        frontier.append((src, newdest, cost, via))
  
  return distances


def toTimespan(secs):
  secs = int(secs) / 60 * 5
  return '%d:%.2d' % (secs/60, secs%60)


reader = csv.reader(cStringIO.StringIO(chariots_csv))
stops = dict((x[0], ChariotStop(*x)) for x in reader)
routes = createRoutes(stops, routenames)
distances = calculateDistances(routes)

# Print via table
def printVia():
  print '{|'
  print '|'
  for name in names:
    print '!%s' % stops[name].shortname
  print '|-'
  for row in names:
    print '!%s' % row
    for col in names:
      time, via = distances[(stops[row], stops[col])]
      if row == col:
        print '|'
      elif via is None:
        print "|'''%s'''" % toTimespan(time)
      else:
        print '|%s (%s)' % (toTimespan(time), via.shortname)
    print '|-'
  print '|}'