#!/usr/bin/env python

# Ragnarok, by Jonathan Cooper

# ragnarok.py: main program

# At the moment, this file is a bit of a jumble. It will probably remain so :)

# Our version
version = 410
version_string = "Ragnarok 4.10 (network game support)"
version_date = "2002/09/05"
# Earliest version of saved game files that we can load
save_version = 400


import random, copy, traceback, sys
try:
  import readline
except:
  pass
from UserList import UserList
from colour import *
import config as conf
from tech import *
import ships, graphics
from graphics import *
import server

## Detailed listing of classes, for debugging.
class Lister:
  def __repr__(self):
    return ("<Instance of %s, address 0x%x:\n%s>" %
            (self.__class__.__name__, id(self), self.attrnames()))
  def __str__(self):
    return("<Instance of %s at address 0x%x>" % (self.__class__.__name__,
                                                 id(self)))
  def attrnames(self):
    result = ''
    for attr in self.__dict__.keys():
      if attr[:2] == '__':
        result = result + "\tname %s=<built-in>\n" % attr
      else:
        result = result + "\tname %s=%s\n" % (attr, `self.__dict__[attr]`)
    return result

def debug(*args, **kwargs):
  if conf.debug:
    targ = []
    for arg in args:
      if type(arg) == type(''): targ.append(arg)
      else: targ.append(str(arg))
    text = ' '.join(targ)
    if kwargs.has_key('nl'): nl=kwargs['nl']
    else: nl = 1
    if nl: print text
    else: print text,


## Various functions that don't seem to fit anywhere else
def jtime(from_, to, tech, pl, pos=0):
  """Return the time taken for a fleet owned by pl with technology tech
  to get from star from_ to star to."""
  if from_ is None:
    # Resending from pos with dread_comm
    t = conf.trav * sqrt(dist(pos, to.coords()))
  else:
    # Special case: warp portal
    if from_.tech() & tech_num['warp portal']:
      return 0.01
    t = conf.trav * sqrt(dist(from_.coords(), to.coords()))
  # Hyperwarp
  if tech & tech_num['hyperwarp']:
    if pl.getres(tech_num['hyperwarp']):
      t = t / 2.1
    else:
      t = t / 1.8
  return t

def validate_route(s1, s2, stars):
  "Is there a valid straight line flight path between these 2 stars?"
  import math
  x1, y1 = s1.coords()
  x2, y2 = s2.coords()
#.  debug("validate_route():",x1,y1,x2,y2,nl=0)
  # Fiddle x values so no vertical lines
  if x1 - x2 == 0:
    x1 += 0.00001
#.    debug("fiddled",nl=0)
  # Find gradient & y-intercept of line between 2 stars
  m = (y1 - y2) / float(x1 - x2);
  c = y2 - m * x2;

  twoa = 2.0 * (1.0 + m*m);
#.  debug("len =",len(stars),nl=0)
  for st in stars:
    if st is s1 or st is s2: continue
    x, y = st.coords()
#.    debug("(",x,y,")",nl=0)
    cminusy = c - y
    rsq = 25.0
    if st.isnova(): rsq = 49.0
    minusb = -2.0*(m*cminusy - x)
    discrim = (minusb*minusb - 2*twoa*(x*x + cminusy*cminusy - rsq))
    if discrim >= 0:
#.      debug("discrim =",discrim,nl=0)
      # Path could intersect the star
      discrim = math.sqrt(discrim)
      intx = (minusb+discrim)/twoa  # Solution 1 of quadratic
      t = (intx-x2)/(x1-x2)  # Is solution on line _segment_ ?
      if t > 0 and t < 1: return 0
      intx = (minusb-discrim)/twoa  # Solution 2 of quadratic
      t = (intx-x2)/(x1-x2)  # Is solution on line _segment_ ?
      if t > 0 and t < 1: return 0
#.  debug(".")
  return 1


def str_s(n):
  "Return 's' if n != 1"
  if n != 1:
    return 's'
  else:
    return ''
def str_ns(n):
  "Return 's' if n == 1"
  if n == 1:
    return 's'
  else:
    return ''

def sanity_check(last_event):
  sfx = "\n Last event: " + `last_event`
  for ev in events:
    assert ev.date() >= gamedate, "Pending event " + `ev` + " is in the past." + sfx
  for fl in fleets:
    shs, nsh = fl.ships(), 0
    for sh in shs:
      nsh += sh.num()
    assert nsh == fl.nships(), "Fleet " + `fl` + " has inconsistent ship numbers (" + `nsh` + ")." + sfx
    assert nsh > 0, "Fleet " + `fl` + " has -ve or 0 size." + sfx


## Player class
class Player(Lister):
  "Methods and variables describing a player's state and what he can do."
  def __init__(self, name, human, colour, _id=None):
    self._name, self._human, self._colour = name, human, colour
    self._turn = 0
    self._researches = {}
    for t in techs.keys():
      if techs[t][tech_resable]:
        self._researches[t] = 0
    self._str = 0
    self._allies = []
    self._sock = None
    if _id:
      self.id = _id
    else:
      self.id = id(self)

  def net_repr(self):
    "Return a string with enough detail to recreate this player."
    repr = "%s\0%s\0(%d,%d,%d)\0%d\0" % (self._name, self.__class__,
                                         self._colour[0], self._colour[1],
                                         self._colour[2], self._turn)
    tech = 0
    for t in self._researches.keys():
      if self._researches[t]: tech |= t
    def idextr(obj):
      "Extract the unique (across network) id of an object."
      return obj.id
    repr = repr + "%d\0%d\0%s\0%d" % (tech, self._str, map(idextr, self._allies),
                                      self.id)
    return repr
    
  def setname(self, name):
    self._name = name
  def name(self):
    return self._name

  def sethuman(self, human):
    self._human = human
  def human(self):
    return self._human

  def setcolour(self, colour):
    self._colour = colour
  def colour(self):
    return self._colour

  def giveturn(self):
    "Set this player's turn flag to true."
    self._turn = 1
  def do_turn(self, gamedate):
    "Execute this player's turn, if he has one."
    if self._turn:
      self.turn(gamedate)
      self._turn = 0

  def getres(self, tech):
    "Has player researched tech?"
    return self._researches[tech]
  def do_research(self, tech):
    "Player has research technology tech."
    self._researches[tech] = 1
  def randomize_researches(self):
    "Give the player a random set of researched technologies."
    for t in techs.keys():
      if techs[t][tech_resable]:
        self._researches[t] = random.randint(0,1)

  def gainstar(self):
    "Player takes over a star."
    self._str += 1
  def losestar(self):
    "Player loses a star."
    self._str -= 1
  def calc_str(self):
    "Recalculate player strength (ie number of stars controlled)."
    self._str = 0
    for st in stars:
      if st.player() is self: self._str += 1
  def str(self):
    "Return player strength."
    return self._str
  def check_win(self):
    "Check if player has won."
    if not game_ended:
      n_dead_st = 0
      for st in stars:
        if st.isnova() or st.hastech(tech_num['black hole']):
          n_dead_st += 1
      if len(stars) - n_dead_st == 0:
        return (self.str() > 0)
      if self.str()/float(len(stars) - n_dead_st) > conf.winpercent/100.0:
        # Check fleet sizes
        debug("Player",self.name(),"has enough stars.")
        tsh = psh = 0  # Total ships, player's ships
        for fl in fleets:
          tsh += fl.nships()
          if fl.player() is self: psh += fl.nships()
        if psh/float(tsh) > conf.winpercent/100.0:
          # Player has won
          if conf.end_win:
            raise GameOver, self
          else:
            game_over(self)
      # Allied victory
      if not game_ended:
        str = self.str()
        for pl in self.allies():
          str += pl.str()
          if str/float(len(stars) - n_dead_st) > conf.winpercent/100.0:
            # Check fleet sizes
            tsh = psh = 0
            for fl in fleets:
              tsh += fl.nships()
              if fl.player() is self or fl.player() in self.allies():
                psh += fl.nships()
            if psh/float(tsh) > conf.winpercent/100.0:
              # Allies have won
              l = copy.copy(self.allies())
              l.append(self)
              if conf.end_win:
                raise GameOver, l
              else:
                game_over(l)

  def kill_gene(self):
    "Remove all genestealers from player's stars & fleets."
    for st in stars:
      if st.player() is self:
        st.remtech(tech_num['genestealers'])
    for fl in fleets:
      if fl.player() is self:
        fl.remtech(tech_num['genestealers'])

  # Alliance stuff
  def allies(self):
    return self._allies
  def num_allies(self):
    return len(self._allies)
  def allied(self, pl):
    "Are we allied with pl?"
    if pl in self._allies: return 1
    else: return 0
  def ally_add(self, pl):
    "Add pl to our allies."
    if not self.allied(pl):
      self._allies.append(pl)
      debug("Alliance formed:",self.name(),"&",pl.name())
      pl.ally_add(self)
  def ally_accept(self, pl):
    "Return true if we accept an alliance with pl, and add pl to our allies."
    # Subclasses should probably override this
    return 0
  def ally_fleet_arrived(self, pl, fl, st):
    """fl has arrived at star st owned by our ally pl.
    Return 0 to fight, 1 to donate fleet, 2 if re-sent fleet."""
    # Subclasses should probably override this
    self.ally_end(pl)
    return 0
  def ally_end(self, pl):
    "End our alliance with pl."
    if pl in self._allies:
      self._allies.remove(pl)
      pl.ally_end(self)
  def ally_offer(self, pl):
    "Offer pl an alliance with us."
    if not self.allied(pl) and pl.ally_accept(self):
      self.ally_add(pl)
      success = 1
    else:
      success = 0
    return success

  # Network game stuff
  def sock(self):
    "Return the socket associated with this player."
    try:
      return self._sock
    except:
      return None
  def setsock(self, sock):
    "Set the socket associated with this player."
    self._sock = sock


## Star class
class Star(Lister):
  def __init__(self, x, y, player, tech = 0, _id=None):
    "Create a new star."
    self._x, self._y = x, y
    self._player, self._tech = player, tech
    self._type_bld = None # Type of next (not current) build at this star
    self._stargate = 0    # Date when stargate (if present) can be used
    self._black_hole = 0  # Whether the comp knows there's a black hole here
    player.gainstar()
    if _id:
      self.id = _id
    else:
      self.id = id(self)

  def net_repr(self):
    "Return a string with enough info to allow us to recreate the star."
    repr = "%d\0%d\0%d\0%d" % (self._x, self._y, self._player.id, self._tech)
    if self._type_bld:
      repr = repr + "\0%d" % self._type_bld.id()
    else:
      repr = repr + "\00"
    repr = repr + "\0%f\0%d\0%d" % (self._stargate, self._black_hole, self.id)
    return repr

  def coords(self):
    return self._x, self._y
  def setcoords(self, x, y):
    self._x, self._y = x, y

  def player(self):
    "Return the controlling player."
    return self._player
  def takeover(self, player):
    "player takes control of this star."
    self._player.losestar()
    self._player = player
    player.gainstar()
    
  def tech(self):
    "Return the star's technology."
    return self._tech
  def hastech(self, tech):
    "Does this star have this tech?"
    return self._tech & tech
  def addtech(self, tech):
    "Add tech to the star."
    self._tech |= tech
  def remtech(self, tech):
    "Remove tech from the star."
    self._tech &= ~tech
  def isnova(self):
    "Has this star been nova'ed?"
    return (self._tech & tech_num['supernova'])

  def stargate_date(self):
    "Return the date when the star's stargate can next be activated. Result only makes sense if the star actually _has_ a stargate."
    return self._stargate
  def use_stargate(self):
    "Use the star's stargate."
    success = 0
    if self._tech & tech_num['stargate']:
      if self._stargate <= gamedate:
        self._stargate = gamedate + 5
        success = 1
    return success
  def stargate(self):
    "Return true if the star has a usable stargate."
    return (self._tech & tech_num['stargate'] and self._stargate <= gamedate)

  def black_hole_found(self):
    self._black_hole = 1
  def black_hole(self):
    return self._black_hole
  def black_hole_removed(self):
    # Used in cheat routines, and also exp device
    self._black_hole = 0
  
  def type_bld(self):
    return self._type_bld
  def set_bld(self, type_bld):
    self._type_bld = type_bld
  def start_build(self):
    btype = copy.copy(self.type_bld())
    if btype.type() == "ship":
      if self.tech() & tech_num['robot factory']:
        btype.set_bld_time(btype.bld_time() / 2.0)
    elif btype.type() == "research":
      if btype.bld_time() == 5:
        btype.set_bld_time(btype.bld_time() + random.randint(1,5))
    BuildEvent(gamedate + btype.bld_time(), self, btype)
  def no_build(self):
    "Remove any pending build events at this star."
    debug("no_build(): using events",id(events))
    blah = None
    for ev in events:
      if isinstance(ev, BuildEvent) and ev.star() is self:
        debug("Removing event",ev,"date",ev.date(),"ship",ev.bld_item(),"from star",self,"player",ev.star().player().name())
        blah = ev
        ev.remove() # Ho, hum :)
        if ev in events:
          debug("Failed.")
    if blah in events:
      debug("Still failed.")
  def takeover_build(self, fl, pl):
    "star changes ownership from pl due to arrival of fleet fl. Decide what to build at st."
    build_ev = None
    if random.randrange(20) or pl is aliens:
      # Remove any build in progress at the star
      self.no_build()
    else:
      # Build survives. Find it.
      for ev in events:
        if isinstance(ev, BuildEvent) and ev.star() is self:
          build_ev = ev
          debug("Build",build_ev,"in events",id(events),"survives at star",self)
          break
    # Decide what to build next
    if self.player().human():
      human.choose_build(self.player(), self, gamedate)
    else:
      computer.choose_build(self.player(), self, gamedate)
    if build_ev is None:
      # Build it
      self.start_build()
  
  def nova(self, fl = None):
    "Nova this star. If fl is specified and is not None, destroy fl as well."
    if not fl is None:
      fl.remove()
    self.no_build()
    self.takeover(aliens)
    self.addtech(tech_num['supernova'])

  def mark(self):
    "Mark this star."
    graphics.mark_star(self)
  def draw(self):
    "Draw this star."
    graphics.draw_star(self)

def random_star():
  "Pick a random star in the galaxy."
  return random.choice(stars)

class StarList(UserList):
  "Basically, what it says on the tin."
  def __init__(self, seq = []):
    self.data = seq
    self.sev_last = None
  
  def random(self):
    "Return a randomly chosen star in the galaxy."
    return random.choice(self.data)
  def draw(self):
    "Draw the galaxy."
    graphics.draw_stars(self)


## Events
class Event(Lister):
  "Base class for events."
  def __init__(self, date):
    self._date = date
    
#.  def __eq__(self, other):
#.    return self._date == other._date
#.  def __ne__(self, other):
#.    return self._date != other._date
  def __lt__(self, other):
    return self._date < other._date
  def __le__(self, other):
    return self._date <= other._date
  def __gt__(self, other):
    return self._date > other._date
  def __ge__(self, other):
    return self._date >= other._date

  def net_repr(self):
    "Give a representation of this event suitable for sending across the net."
    return "0Event\0%f" % self.date()
  
  def date(self):
    return self._date
  def process(self):
    """Base process method: set gamedate to date of this event, draw stars,
    display date & remove event from queue.
    Also set stars.sev_last to this event's star, if it has one, or None."""
    global gamedate
    try:
      stars.sev_last = self.star()
    except AttributeError:
      stars.sev_last = None
    gamedate = self.date()
    debug("Event type",self.__class__,"date",gamedate)
    if net == 1:
      # We're a server, so tell everyone about the event
      server.net_send_text("Process event")
      server.net_send_obj(self)
    else:
      # We're a client or single-computer, so process the event as normal
      draw_stars(stars)
      msg("Date: %.1f     \n\n" % gamedate)
      if stars.sev_last: stars.sev_last.mark()
    self.remove()
  def insert(self):
    "Add this event to the queue."
    events.insert(self)
  def remove(self):
    "Remove this event from the queue."
    debug("Removing event",self,"from",id(events))
    events.remove(self)

class ArriveEvent(Event):
  "Arrival event."
  def __init__(self, date, star, fleet, jour, sending_star):
    Event.__init__(self, date)
    self._star, self._fleet = star, fleet
    self._jour, self._sending_star = jour, sending_star
    self.insert()

  def net_repr(self):
    return "1ArrivalEvent\0%f\0%d\0%d\0%f\0%d" % (self._date, self._star.id,
                                                  self._fleet.id, self._jour,
                                                  self._sending_star.id)
  def star(self):
    return self._star
  def fleet(self):
    return self._fleet
  def jour(self):
    return self._jour
  def sending_star(self):
    return self._sending_star

  def supernova(self):
    "Fleet arrives at a dead star."
    ns = self.fleet().nships()
    msg("%d %s ship%s arrive%s.\n" % (ns, self.fleet().player().name(),
                                      str_s(ns), str_ns(ns)))
    if ns == 1:
      msg("It is destroyed.\n")
    else:
      msg("They are all destroyed.\n")
    if conf.await_user: graphics.await_user()
    else: graphics.wait(100)
    self.fleet().player().giveturn()
    self.fleet().remove()
  def black_hole(self):
    "Fleet arrives at a black hole."
    ns = self.fleet().nships()
    msg("%d %s ship%s arrive%s.\n" % (ns, self.fleet().player().name(),
                                      str_s(ns), str_ns(ns)))
    msg(" This star is orbited by a BLACK HOLE!\n")
    self.fleet().player().giveturn()
    self.fleet().remove()
    self.star().black_hole_found()
    if music.on:
      music.death_tune()
    if conf.await_user: graphics.await_user()
    else: graphics.wait(200)
  def nothing_here(self):
    "No ships currently at destination star."
    st = self.star()
    fl = self.fleet()
    ns = fl.nships()
    msg("%d %s ship%s arrive%s.\n" % (ns, self.fleet().player().name(),
                                      str_s(ns), str_ns(ns)))
    fl.player().giveturn()
    fl.setstar(st)
    if not conf.await_user: graphics.wait(50)
    # Spread genestealers
    if fl.tech() & tech_num['genestealers']:
      st.addtech(tech_num['genestealers'])
    # Transfer tech from star to fleet
    fl.addtech(st.tech() & tech_transfer_mask)
    # If star owned by someone else, take it over
    if not st.player() is fl.player():
      if conf.await_user: graphics.wait(50)
      msg(" Unopposed takeover.\n")
      p = st.player()
      st.takeover(fl.player())
      draw_star(st)
      if not conf.await_user: graphics.wait(50)
      else: graphics.await_user()
      st.takeover_build(fl, p)
      draw_stars(stars)
      mark_star(st)
    else:
      if conf.await_user: graphics.await_user()
  def friendly_here(self, fhere):
    "Friendly fleet at destination star."
    fl = self.fleet()
    ns = fl.nships()
    msg("%d %s ship%s arrive%s.\n" % (ns, fl.player().name(),
                                      str_s(ns), str_ns(ns)))
    fhere.player().giveturn()
    # Transfer ships to fleet at star
    fhere.addships(fl.ships())
    # Transfer tech
    fhere.addtech(fl.tech() & tech_transfer_mask)
    # Transfer genestealers
    if fhere.tech() & tech_num['genestealers']:
      fhere.star().addtech(tech_num['genestealers'])
    # Remove travelling fleet
    fl.remove()
    if conf.await_user: graphics.await_user()
    else: graphics.wait(100)
  def hostile_here(self, fhere):
    fl = self.fleet()
    ships_att = fl.nships()
    ships_def = fhere.nships()
    msg("%d %s ship%s encounter%s %d %s ship%s.\n" %
        (ships_att, fl.player().name(), str_s(ships_att), str_ns(ships_att),
         ships_def, fhere.player().name(), str_s(ships_def)))
    if conf.await_user: graphics.await_user()
    else: graphics.wait(100)
    fl.player().giveturn()
    fhere.player().giveturn()
    # Check for an alliance
    if fl.player().allied(fhere.player()):
      res = fl.player().ally_fleet_arrived(fhere.player(), fl, fhere.star())
      if res == 0:
        # Fight
        battle.battle(fl, fhere)
      elif res == 1:
        # Donate fleet
        msg("Fleet donated.\n")
        fhere.addtech(fl.tech())
        fhere.addships(fl.ships())
        fl.remove()
        graphics.wait(100)
      else:
        # Re-sent fleet
        pass
    else:
      battle.battle(fl, fhere)
    draw_stars(stars)
    mark_star(self.star())
    msg("Date: %.1f     \n\n" % gamedate)
    
  def process(self):
    "Process arrival event."
    Event.process(self)
    debug(self.fleet().player().name(),"fleet arrives at",self.star())
    # Is this star dead?
    if self.star().isnova():
      self.supernova()
      return
    # Is there a black hole here?
    if self.star().tech() & tech_num['black hole']:
      self.black_hole()
      return
    # Is there a warp portal here?
    if self.star().tech() & tech_num['warp portal']:
      if self.fleet().player().name() != conf.pl_cht:
        self.supernova()  # Pretend the star is dead
        return
    # Is there a fleet already at the destination star?
    fhere = fleets.find_at_star(self.star())
    if fhere is None:
      # No fleet here
      self.nothing_here()
    else:
      if fhere.player() is self.fleet().player():
        self.friendly_here(fhere)
      else:
        self.hostile_here(fhere)

class BuildEvent(Event):
  "Build event."
  def __init__(self, date, star, bld_item):
    Event.__init__(self, date)
    self._star, self._bld_item = star, bld_item
    self.insert()

  def net_repr(self):
    return "2BuildEvent\0%f\0%d\0%d", (self._date, self._star.id,
                                       self._bld_item.id)

  def star(self):
    return self._star
  def bld_item(self):
    return self._bld_item

  def process(self):
    "Process build event."
    Event.process(self)
    pl = self.star().player()
    s = self.bld_item()
    msg("1 %s " % pl.name())
    if s.type() == "research":
      msg("research ")
    msg("%s built.\n" % (s.name(),))
    pl.giveturn()
    if not conf.await_user: graphics.wait(100)
    if s.type() == "ship":
      # Find the fleet, if any, at this star
      fl = fleets.find_at_star(self.star())
      debug("build() at star,",self.star(),"fl =",fl)
      if fl is None:
        # Create new fleet
        debug("build(): new fleet")
        fl = Fleet([], self.star(), pl, self.star().tech() & tech_transfer_mask)
      # Add ship to fleet
      fl.addships([s])
      # Allow genestealers to take over
      if self.star().tech() & tech_num['genestealers'] and not pl is pl_gene and not random.randrange(10):
        if not pl.getres(tech_num['genestealers']):
          if conf.await_user: graphics.wait(100)
          msg(" The genestealers take over!\n")
          if not conf.await_user: graphics.wait(100)
          self.star().takeover(pl_gene)
          self.star().no_build()
          fl.setplayer(pl_gene)
          draw_star(self.star())
          pl_gene.giveturn()
          pl = pl_gene
    elif s.type() == "research":
      # Research tech
      pl.do_research(tech_num[s.name()])
      if s.name() == 'genestealers':
        pl.kill_gene()
      if self.star().type_bld() == s:
        self.star().set_bld(ships.Fighter())
    else:
      print >> sys.stderr, "Unknown build type:", str(s)
    if not pl is aliens: # In case of genestealer takeover
      # Computer chooses next build type
      if not pl.human():
        computer.choose_build(pl, self.star(), gamedate)
      # Start next build
      self.star().start_build()
    if conf.await_user: graphics.await_user()

class TurnEvent(Event):
  "Event giving a player a turn."
  def __init__(self, date, player, star=None):
    # Check we're not trying to give aliens a turn
    if player is aliens: return
    # Check we don't already have an identical event in the queue
    debug("TurnEvent: events =",id(events))
    for ev in events:
      if isinstance(ev, TurnEvent) and ev.player() is player and \
         abs(ev.date() - date) < 0.0001:
        return
    # Add us
    debug("TurnEvent: added",player.name(),"at",date)
    Event.__init__(self, date)
    self._player, self._star = player, star
    self.insert()

  def net_repr(self):
    return "3TurnEvent\0%f\0%d", (self._date, self._player.id)

  def player(self):
    return self._player
  def star(self):
    return self._star

  def process(self):
    "Process a turn event."
    Event.process(self)
    self.player().giveturn()

class AlienBuildEvent(Event):
  "Alien build event."
  def __init__(self, date):
    Event.__init__(self, date)
    self.time = conf.abld  # Initial time between alien builds
    self.insert()

  def net_repr(self):
    return "4AlienBuildEvent\0%f" % self._date

  def process(self):
    "Process alien build event."
    Event.process(self)
    if self.date() > 40 and self.date() <= 70:
      self.time /= 2
      bld = ships.Frigate
    elif self.date() > 70:
      self.time /= 4.0
      bld = ships.Dreadnought
    else:
      bld = ships.Fighter
    # Now go through all stars, possibly building on each alien one.
    # On an alien star a ship will be built if there are ships already present.
    # If not, there's a 50-50 chance of a build.
    #debug("Alien Build: aliens =",aliens)
    for st in stars:
      #debug("Alien Build: player =",st.player(),",nova =",st.isnova())
      if st.player() is aliens and not st.isnova():
        afl = fleets.find_at_star(st)
        debug("Alien Build: afl =",afl)
        if afl is None and random.randint(0,1):
          afl = Fleet([], st, aliens, st.tech() & tech_transfer_mask)
        if not afl is None:
          afl.addships([bld()])
    # Add next alien build event
    debug("Alien Build:",gamedate,"+",self.time,"(now",self.date(),")","bld =",bld())
    AlienBuildEvent(gamedate + self.time)


class EventQueue(UserList):
  """
  Event queue management functions.
  Queue is implemented as a straightforward list of instances of Event subclasses.
  """
  def __init__(self, seq = []):
    self.data = seq

  def insert(self, ev):
    "Add ev to the event queue."
    self.data.append(ev)

  def next_event(self):
    "Return the next event to be processed."
    return min(self.data)

  def process(self):
    "Process the next event in the queue."
    self.next_event().process()

  def empty(self):
    "Return true if the queue is empty."
    return (self.data == [])


## Fleets
class Fleet(Lister):
  def __init__(self, ships, star, player, tech = 0, _id=None):
    "Create a new fleet. ships is a list of Ship instances."
    self._nships, self._ships = 0, ships
    for ship in ships:
      self._nships += ship.num()
    self._star, self._player = star, player
    self._tech = tech
    self.insert()
    if _id:
      self.id = _id
    else:
      self.id = id(self)

  def net_repr(self):
    repr = "%d\0%d\0%d\0" % (self._star.id, self._player.id, self._tech)
    def descsh(sh):
      "Describe a ship."
      return "%d.%d" % (sh.id(), sh.num())
    repr = repr + map(descsh, self._ships)
    return repr

  def tech(self):
    "Return the fleet's technology."
    return self._tech
  def hastech(self, tech):
    "Does this fleet have this tech?"
    return self._tech & tech
  def addtech(self, tech):
    "Add tech to the fleet."
    self._tech |= tech
  def remtech(self, tech):
    "Remove tech from the fleet."
    self._tech &= ~tech

  def player(self):
    return self._player
  def setplayer(self, player):
    self._player = player

  def star(self):
    return self._star
  def setstar(self, star):
    self._star = star

  def nshots(self):
    "Return the number of guns this fleet has."
    guns = 0
    for sh in self._ships:
      guns += sh.num() * sh.shots()
    return guns

  def nships(self):
    "Return the total number of ships in this fleet."
    return self._nships
  def loseship(self):
    "Fleet loses a ship in battle."
    self._nships -= 1
  def ships(self, ship_class = ships.NoShip()):
    """Return a fleet's ship instance. Return only class ship_class if present,
    else return all classes of ship."""
    self._ships.sort()
    if ship_class == ships.NoShip():
      return self._ships
    else:
      for ship in self._ships:
        if ship == ship_class:  # Note: equality test is on name for ships
          return ship
      else:
        return ships.NoShip()
  def addships(self, ships):
    "Add ships to fleet. ships should be a list of instances of class Ship."
    for ship in ships:
      for cur in self._ships:
        if cur == ship:
          debug("Adding",ship.num(),"ships of type",ship.name(),"to fleet size",self._nships,"with",cur.num(),"atm.",nl=0)
          cur.inc_num(ship.num())
          self._nships = self._nships + ship.num()
          debug("Now size",self._nships,"with",cur.num())
          break
      else:
        debug("Appending",ship.num(),"ships of type",ship.name(),"to fleet size",self._nships,nl=0)
        self._ships.append(ship.__class__(ship.num()))
        self._nships = self._nships + ship.num()
        debug(". Size now",self._nships)
  def removeships(self, ships):
    "Remove ships from fleet. ships should be a list of instances of class Ship."
    for ship in ships:
      idx = self._ships.index(ship)
      assert ship.num() <= self._ships[idx].num(), "Tried to remove too many ships"
      debug("Removing",ship.num(),"ships of type",ship.name(),"from",self._ships[idx].num(),"(total:",self._nships,")",nl=0)
      self._nships -= ship.num()
      self._ships[idx].dec_num(ship.num())
      debug("leaving",self._ships[idx].num(),"(total:",self._nships,")")
      if self._ships[idx].num() == 0:
        del self._ships[idx]
        debug("Ship type deleted.")
  def setships(self, ships):
    "Set fleet's ship list to ships."
    self._ships = ships
    self._nships = 0
    for ship in ships:
      self._nships = self._nships + ship.num()

  def speed(self):
    "Return the speed of the slowest ship in this fleet."
    spd = []
    for ship in self._ships:
      spd.append(ship.speed())
    if spd == []:
      return 1.0
    else:
      return min(spd)
  def send_to(self, st, spd=None, noact=0, nodelay=0, pos=0):
    "Send this fleet to star st."
    if not noact: debug("send_to():",self.nships(),"ships go to",st,"from",self.star(),nl=0)
    if self.star() is None:
      # We must be resending using dread_comm
      fromx, fromy = pos
    else:
      fromx, fromy = self.star().coords()
    # Calculate arrival date
    if spd is None: spd = self.speed()
    jour = jtime(self.star(), st, self.tech(), self.player(), pos=pos) / spd
    if self.star() and self.star().stargate():
      if not noact: self.star().use_stargate()
      jour = 0.00001
      if not self.player().getres(tech_num['stargate']) and not random.randrange(10):
        st = random_star()
    # Send fleet
    draw_line((fromx, fromy), st.coords(), self.player().colour())
    if not noact: debug("Arrive",gamedate+jour,"jour =",jour)
    if noact:
      return gamedate+jour
    ArriveEvent(gamedate + jour, st, self, jour, self.star())
    if not self.player() is st.player():
      TurnEvent(gamedate, st.player(), star=st)
    self.setstar(None)
    if not nodelay: graphics.wait(50)
    undraw_line()

  def remove(self):
    "Remove this fleet from the list."
    fleets.remove(self)
  def insert(self):
    "Add this fleet to the list."
    fleets.insert(self)



class FleetList(UserList):
  "Class to manage the list of fleets."
  def __init__(self, seq = []):
    self.data = seq
  
  def insert(self, fl):
    "Add fl to the fleet list."
    self.data.append(fl)

  def find_at_star(self, star):
    "Find any fleet at star."
    f = None
    for fl in self.data:
      if fl.star() is star:
        if f:
          debug("!!!!!Extra fleets at star",star)
        else:
          f = fl
    else:
      return f


## Saving & loading games
def save_game_wrapper():
  save_game(game_filename)

def save_game(filename, panic=0):
  """Save the game to file filename, by default in directory conf.savedgames.
  If panic is true, save to file !!Panic!! instead."""
  if panic: path = conf.savedgames + "!!Panic!!"
  else: path = conf.savedgames + filename
  # Attempt to open file
  try:
    fp = open(path, "w")
  except IOError:
    pass
  try:
    fp = open(filename, "w")
    path = filename
  except IOError:
    yn = raw_input("Failed to open save game file. Panic save? (Y/N) ")
    if yn.lower() in ['y', 'yes']:
      try:
        fp = open("!!Panic!!", "w")
      except IOError:
        print "Failed to open panic save file, bailing out. Exception was:"
        raise
    else:
      print "Not saving. Exception was:"
      raise
  # Now we try writing the file
  try:
    import cPickle
    p = cPickle.Pickler(fp, 0)
    p.dump(version)
    npl = len(players)
    nst = len(stars)
    nfl = len(fleets)
    nev = len(events)
    p.dump(npl)
    for pl in players:
      p.dump(pl)
    p.dump(nst)
    for st in stars:
      p.dump(st)
    p.dump(stars.xmax)
    p.dump(stars.ymax)
    p.dump(nfl)
    for fl in fleets:
      p.dump(fl)
    p.dump(nev)
    for ev in events:
      p.dump(ev)
    p.dump(gamedate)
    p.dump(filename)
  finally:
    fp.close()
  # Done (possibly)
  debug("Game",filename,"saved as",path)

def load_game(path):
  "Load a saved game from path."
  global players, events, stars, fleets, aliens, pl_gene, gamedate, game_filename
  # Attempt to open file
  try:
    fp = open(path, "r")
  except:
    path = conf.savedgames + path
    fp = open(path, "r")  # Try with the "savedgames/"
  try:
    # Exception for bad version of savedgame file
    VersionError = "Saved game file is from too early a version to load"
    import cPickle
    p = cPickle.Unpickler(fp)
    v = p.load()
    if v < save_version:
      raise VersionError, "Our version: " + `version` + ", file version: " + `v`
    # Load players
    npl = p.load()
    while players:
      players.pop()
    for i in range(npl):
      players.append(p.load())
    # Load stars
    nst = p.load()
    while stars:
      stars.pop()
    for i in range(nst):
      st = p.load()
      if st.player().name() == "alien":
        st.takeover(aliens)  # Oh, the hackishness :)
      stars.append(st)
    stars.xmax = p.load()
    stars.ymax = p.load()
    # Load fleets
    nfl = p.load()
    while fleets:
      fleets.pop()
    for i in range(nfl):
      fl = p.load()
      if fl.player().name() == "alien":
        fl.setplayer(aliens)
      fleets.append(fl)
    # Load events
    while events:
      events.pop()
    nev = p.load()
    for i in range(nev):
      events.append(p.load())
    # Game 'clock'
    gamedate = p.load()
    # Filename
    game_filename = p.load()
    # Alien player
    aliens.calc_str()
    # Genestealers
    pl_gene = aliens
    for pl in players:
      if pl.name().lower()[:11] == "genestealer":
        pl_gene = pl
  finally:
    fp.close()
  # Done (possibly)


## Main game loop function
GameOver = 'Game Over'  # End of game exception
def start_game():
  "Set a game going."
  # Set up easygame
  graphics.init_graphics()
  try:
    while not events.empty():
      # Process next event
      last_event = events.next_event()
      last_event_date = last_event.date()
      events.process()
      if conf.merge_events:
        try:
          cond = events.next_event().date()-last_event_date < \
                 conf.merge_events_time and \
                 events.next_event().star() is last_event.star()
        except AttributeError:
          cond = 0
        while cond:
          last_event = events.next_event()
          events.process()
          try:
            cond = events.next_event().date()-last_event_date < \
                   conf.merge_events_time and \
                   events.next_event().star() is last_event.star()
          except AttributeError:
            cond = 0
      sanity_check(None)
      # Player turns
      for pl in players:
        pl.check_win()
        pl.do_turn(last_event.date())
      # Go through any remaining (pygame) events
      evs = graphics.event_get()
      for ev in evs:
        check_event(ev)
      sanity_check(last_event)
  except GameOver, pl:
    # Game has ended. pl is the player(s) who won, or None if user quitted early.
    graphics.quit_graphics()
    if pl is None:
      # Offer to save game
      yn = raw_input("Do you wish to save the game? (Y/N) ")
      if yn.lower() in ['y', 'yes']:
        save_game(game_filename)
    else:
      if type(pl) == type(aliens):
        # Single player wins
        print pl.name(),"has won! Congratulations!"
      elif type(pl) == type([aliens]):
        # Coalition win
        names = ""
        for p in pl:
          names = names + p.name() + " & "
        names = names[:-3]
        print names,"have won! Congratulations!"
  except:
    print "An error has occurred."
    traceback.print_exc()
    yn = raw_input("Attempt to save game? (Y/N) ")
    if yn.lower() in ['y', 'yes']:
      print "Saving game as !!Panic!!"
      save_game(game_filename, panic=1)
      print "Save successful."
    print "Re-raising exception."
    raise

def check_event(ev):
  "See if ev is interesting."
  if ev.type == graphics.KEYDOWN:
    #debug("Keydown (key =",ev.key,",mod =",ev.mod,")")
    # Game 'speed'
    if ev.key == graphics.K_F3:
      graphics.scale = 0
    if ev.key == graphics.K_F4:
      graphics.scale = 10
    if ev.key == graphics.K_F5:
      graphics.scale += 2
      if graphics.scale > 20: graphics.scale = 20
    if ev.key == graphics.K_F6:
      graphics.scale -= 2
      if graphics.scale < 1: graphics.scale = 1
    # Alter conf.await_user
    if ev.key == graphics.K_F7: conf.await_user = 1
    if ev.key == graphics.K_F8: conf.await_user = 0
    # Toggle conf.debug
    if ev.key == graphics.K_F12: conf.debug = 1 - conf.debug
    # Cheat - give player turn
    if conf.cheats:
      i = 0
      #debug("players.len=",len(players),"r.players.len=",len(r.players))
      for pl in r.players:
        i += 1
        exec "key = graphics.K_%d" % i
        if ev.key == key and ev.mod == KMOD_LALT:
          pl.giveturn()
    # Cheats
    if conf.cheats and ev.key == graphics.K_F1: human.cheat_fn(None, None, None)
  elif ev.type == graphics.QUIT:
    raise GameOver, None
  elif ev.type == graphics.AUTOSAVE:
    r.save_game_wrapper() # This does work :)
  else: pass

game_ended = 0

def game_over(pl):
  "Game has ended. pl is the player(s) who won. Print msg and continue with game."
  global game_ended
  game_ended = 1
  if type(pl) == type(aliens):
    names = pl.name()
    msg("%s has won! Congratulations!" % names)
  elif type(pl) == type([aliens]):
    names = ""
    for p in pl:
      names = names + p.name() + " & "
    names = names[:-2]
    msg("%s have won! Congratulations!" % names)
  if conf.await_user: graphics.await_user()
  else: graphics.wait(500)


## Game creation
from math import hypot, sqrt

def dist((a, b), (c, d)):
  "Calculate the distance between 2 points in 2d space."
  return hypot(a - c, b - d)

def generate_stars(nst, (xmax, ymax), npl, stars):
  """Generate a starfield with nst stars in a rectangle xmax by ymax in size.
  npl is the number of players."""
  stars.xmax, stars.ymax = xmax, ymax
  for i in range(nst):
    # Create star i
    ok = 0
    while not ok:
      # Find a place not too close to any other stars
      x, y = random.randrange(xmax) + 10, random.randrange(ymax) + 20
      ok = 1
      for st in stars:
        # Stars are circles radius 4
        if dist((x, y), st.coords()) < 10: ok = 0
    st = Star(x, y, aliens)
    st.set_bld(ships.Fighter())
    stars.append(st)
    if i >= npl and random.randint(0,1):
      # Add a fleet of 1-3 ships
      fl = Fleet([], st, aliens)
      s = ships.Fighter(random.randint(1, 3))
      fl.addships([s])
  return stars

def distribute_tech(max_occurrences):
  "Place some random technologies around the galaxy."
  for i in range(max_occurrences):
    for tech in techs.keys():
      if techs[tech][tech_distribute] and random.randrange(3):
        # Place tech on a random alien star
        st = stars.random()
        while not st.player() is aliens:
          st = stars.random()
        fl = fleets.find_at_star(st)
        if fl:
          fl.remtech(st.tech() & tech_transfer_mask)
          fl.addtech(tech)
        st.remtech(st.tech())
        st.addtech(tech)


def new_game(npl, nst):
  "Start a new game. npl is the number of players; nst the number of stars."
  # Make galaxy
  global stars
  generate_stars(nst, (conf.xmax, conf.ymax), npl, stars)
  for i in range(npl):
    pl = players[i]
    # Give computer players random technology researches
    if not pl.human(): pl.randomize_researches()
    # Give player a starting fleet on his star
    stars[i].takeover(pl);
    Fleet([ships.Fighter(5)], stars[i], pl)
    # Initial player build event
    BuildEvent(0, stars[i], ships.Fighter())
  # Initial alien build
  AlienBuildEvent(conf.abld_first)
  # Distribute some random tech about the galaxy
  distribute_tech(conf.max_tech)
  # Get name for the saved game file
  if conf.setup == 1:
    # use TK SaveFileDialog
    import tkFileDialog,Tkinter
    root = Tkinter.Tk()
    root.withdraw()
    filename = tkFileDialog.asksaveasfilename(title="Select file to save game as",
                                              initialdir=conf.savedgames,
                                              parent=root)
    debug("GUI savefiledialog: filename =",filename)
  else:
    # Use CLI
    import os.path
    while 1:
      filename = raw_input("Enter name for game: ")
      path = conf.savedgames + filename
      if os.path.exists(path):
        if os.path.isfile(path):
          # File exists
          overwrite = raw_input("File already exists. Overwrite? (Y/N) ")
          if overwrite.lower() in ['y', 'yes']:
            break
        else:
          print "Path exists and is not a regular file. Please choose a different name."
      else:
        break
  # Save the game
  global gamedate, game_filename
  gamedate, game_filename = 0, filename
  save_game(filename)


## Import the rest of the program
import music, battle
battle.graphics = graphics

events = EventQueue()
fleets = FleetList()
stars = StarList()
players = []
aliens = Player("alien", 0, colour_white)
pl_gene = aliens
gamedate = 0.0

import computer
computer.events, computer.fleets, computer.stars = events, fleets, stars
computer.players, computer.aliens = players, aliens
computer.ArriveEvent, computer.Fleet = ArriveEvent, Fleet


import human
human.stars, human.fleets, human.Fleet = stars, fleets, Fleet
human.save_game, human.GameOver = save_game_wrapper, GameOver
human.events, human.BuildEvent, human.ArriveEvent = events, BuildEvent, ArriveEvent
human.players = players
human.gamedate = gamedate

# Just don't ask...
import ragnarok as r
r.stars, r.fleets, r.players, r.events = stars, fleets, players, events
r.Fleet, r.ArriveEvent, r.BuildEvent = Fleet, ArriveEvent, BuildEvent
r.aliens = aliens
r.save_game_wrapper, r.GameOver = save_game_wrapper, GameOver
graphics.net = r.net = net = 0

## Game setup routines
def setup():
  "Set up game parameters. Currently using a plain terminal interface."
  # Available colours
  import colour
  cols = []
  for var in dir(colour):
    if var[:7] == "colour_":
      exec "cols.append((\"%s\", colour.%s))" % (var[7:], var)

  npl = input("Enter number of players: ")
  for p in range(npl):
    name = raw_input("Enter name of player %d: " % (p+1))
    human = raw_input("Is player %d human (Y/N) ?" % (p+1))
    if human.lower() in ["y", "yes"]: human = 1
    else: human = 0
    print "Choose player colour:"
    i = 0
    for col in cols:
      i += 1
      print "  %d - %s" % (i, cols[i][0])
    col = input("Enter choice: ")
    col = cols[col][1]
    if not human:
      print "Choose computer ai style:"
      print "  1 - Normal"
      print "  2 - Aggressive"
      print "  3 - Technological"
      i = input("Enter choice: ")
      if i == 1: ai = computer.ai_normal
      elif i == 2: ai = computer.ai_aggressive
      elif i == 3: ai = computer.ai_tech
      else: ai = computer.ai_normal
    else:
      ai = None
    players.append(Player(name, human, col, ai))
  nst = input("Enter number of stars: ")
  return npl, nst


## Start us going.
def main():
  global players
  # If a file passed on the command line, treat it as a saved game file
  if len(sys.argv) > 1:
    debug("Loading saved game from", sys.argv[1], "...")
    load_game(sys.argv[1])
    start_game()
  else:
    # Start a new game
    if conf.setup == 0:
      debug("Using terminal-based setup (yuck!)")
      npl, nst = setup()
    elif conf.setup == 1:
      # Default params
      players.append(computer.Normal("Thargoid", colour_red))
      players.append(computer.Aggressive("Dalek", colour_green))
      players.append(computer.Aggressive("Borg", colour_grey))
      players.append(computer.Tech("Puppeteer", colour_cyan))
      players.append(computer.Tech("Romulan", colour_magenta))
      players.append(computer.Normal("Pssthpk", colour_yellow))
      nst = 40
      import setup
      debug("Starting graphical (Tk) setup.")
      code, nst = setup.setup(players, human.Human, computer.ais, nst)
      if code == setup.CANCELLED:
        sys.exit(1)
      elif code == setup.LOADGAME:
        debug("Loading saved game from", nst, "...")
        load_game(nst)
        start_game()
        sys.exit()
      else:
        pass
      npl = len(players)
    else:
      debug("Setting up using values hard-coded in ragnarok.py.")
      # My params
      #  args to Human() are name, colour
      #  args to Computer() are name, colour;
      #   the subclasses are different AIs (UTSL)
      players.append(human.Human("Eldar", colour_green))
      players.append(computer.Normal("Thargoid", colour_red))
      players.append(computer.Aggressive("Borg", colour_grey))
      players.append(computer.Allied("Puppeteer", colour_cyan, players[0]))
      players[0].ally_add(players[3])
      players.append(computer.Tech("Romulan", colour_magenta))
      players.append(computer.Normal("Pssthpk", colour_olive))
      players.append(computer.Tech("Dalek", colour_yellow))
      npl, nst = len(players), 50
    # Create galaxy
    new_game(npl, nst)
    # Start playing
    start_game()


if __name__ == '__main__':
  main()

