make_graph.py

   1 #!/usr/bin/env python3
   2 """\
   3 usage: make-graph.py [-a] -d] [-m] [-s]
   4
   5 Make a DOT graph of Colossal Cave.
   6
   7 -a = emit graph of entire dungeon
   8 -d = emit graoh of mazw all different
   9 -m = emit graph of maze all alike
  10 -s = emit graph of surface locations
  11 """
  12 # Copyright (c) 2017 by Eric S. Raymond
  13 # SPDX-License-Identifier: BSD-2-clause
  14
  15 import sys, getopt, yaml
  16
  17 def allalike(loc):
  18     "Select out loci related to the Maze All Alike"
  19     return ("ALIKE" in loc) or (loc == "LOC_PITBRINK") or ("MAZEEND" in loc) or ("STALACTITE" in loc)
  20
  21 def alldifferent(loc):
  22     "Select out loci related to the Maze All Alike"
  23     return ("DIFFERENT" in loc) or (loc == "LOC_DEADEND13")
  24
  25 def surface(loc):
  26     "Select out surface locations"
  27     attrs = location_lookup[loc]
  28     if ("ABOVE" in attrs["conditions"]) and attrs["conditions"]["ABOVE"]:
  29         return True
  30     if ("FOREST" in attrs["conditions"]) and attrs["conditions"]["FOREST"]:
  31         return True
  32     return False
  33
  34 def abbreviate(d):
  35     m = {"NORTH":"N", "EAST":"E", "SOUTH":"S", "WEST":"W", "UPWAR":"U", "DOWN":"D"}
  36     return m.get(d, d)
  37
  38 def roomlabel(loc):
  39     "Generate a room label from the description, if possible"
  40     loc_descriptions = location_lookup[loc]['description']
  41     description = loc[4:]
  42     longd = loc_descriptions["long"]
  43     short = loc_descriptions["maptag"] or loc_descriptions["short"]
  44     if short is None and longd is not None and len(longd) < 20:
  45         short = loc_descriptions["long"]
  46     if short is not None:
  47         if short.startswith("You're "):
  48             short = short[7:]
  49         if short.startswith("You are "):
  50             short = short[8 :]
  51         if short.startswith("in ") or short.startswith("at ") or short.startswith("on "):
  52             short = short[3:]
  53         if short.startswith("the "):
  54             short = short[4:]
  55         if short[:3] in {"n/s", "e/w"}:
  56             short = short[:3].upper() + short[3:]
  57         elif short[:2] in {"ne", "sw", "se", "nw"}:
  58             short = short[:2].upper() + short[2:]
  59         else:
  60             short = short[0].upper() + short[1:]
  61         description += "\\n" + short
  62         if loc in startlocs:
  63             description += "\\n(" + ",".join(startlocs[loc]).lower() + ")"
  64     return description
  65
  66 # A forwarder is a location that you can't actually stop in - when you go there
  67 # it ships some message (which is the point) then shifts you to a nexr location.
  68 # A forwarder has a zero-length array of notion verbs in its travel section.
  69 #
  70 # Here is an example forwarder declaration:
  71 #
  72 # - LOC_GRUESOME:
  73 #    description:
  74 #      long: 'There is now one more gruesome aspect to the spectacular vista.'
  75 #      short: !!null
  76 #      maptag: !!null
  77 #    conditions: {DEEP: true}
  78 #    travel: [
  79 #      {verbs: [], action: [goto, LOC_NOWHERE]},
  80 #    ]
  81
  82 def is_forwarder(loc):
  83     "Is a location a forwarder?"
  84     travel = location_lookup[loc]['travel']
  85     return len(travel) == 1 and len(travel[0]['verbs']) == 0
  86
  87 def forward(loc):
  88     "Chase a location through forwarding links."
  89     while is_forwarder(loc):
  90         loc = location_lookup[loc]["travel"][0]["action"][1]
  91     return loc
  92
  93 if __name__ == "__main__":
  94     with open("adventure.yaml", "r") as f:
  95         db = yaml.safe_load(f)
  96
  97     location_lookup = dict(db["locations"])
  98
  99     try:
 100         (options, arguments) = getopt.getopt(sys.argv[1:], "adms")
 101     except getopt.GetoptError as e:
 102         print(e)
 103         sys.exit(1)
 104
 105     subset = allalike
 106     for (switch, val) in options:
 107         if switch == '-a':
 108             subset = lambda loc: True
 109         elif switch == '-d':
 110             subset = alldifferent
 111         elif switch == '-m':
 112             subset = allalike
 113         elif switch == '-s':
 114             subset = surface
 115         else:
 116             sys.stderr.write(__doc__)
 117             raise SystemExit(1)
 118
 119     startlocs = {}
 120     for obj in db["objects"]:
 121         objname = obj[0]
 122         location = obj[1].get("locations")
 123         if "OBJ" not in objname and location != "LOC_NOWHERE" and ("immovable" not in obj[1] or not obj[1]["immovable"]):
 124             if location in startlocs:
 125                 startlocs[location].append(objname)
 126             else:
 127                 startlocs[location] = [objname]
 128
 129     # Compute reachability, using forwards.
 130     # Dictionary ke6y is (from, to) iff its a valid link,
 131     # value is correspoinding motion verbs.
 132     links = {}
 133     nodes = set()
 134     for (loc, attrs) in db["locations"]:
 135         nodes.add(loc)
 136         travel = attrs["travel"]
 137         if len(travel) > 0:
 138             for dest in travel:
 139                 verbs = [abbreviate(x) for x in dest["verbs"]]
 140                 if len(verbs) == 0:
 141                     continue
 142                 action = dest["action"]
 143                 if action[0] == "goto":
 144                     dest = forward(action[1])
 145                     if not (subset(loc) or subset(dest)):
 146                         continue
 147                     links[(loc, dest)] = verbs
 148
 149     neighbors = set()
 150     for loc in nodes:
 151         for (f, t) in links:
 152             if f == 'LOC_NOWHERE' or t == 'LOC_NOWHERE':
 153                 continue
 154             if (f == loc and subset(t)) or (t == loc and subset(f)):
 155                 if loc not in neighbors:
 156                     neighbors.add(loc)
 157
 158     print("digraph G {")
 159
 160     for loc in nodes:
 161         if is_forwarder(loc):
 162             continue
 163         node_label = roomlabel(loc)
 164         if subset(loc):
 165             print('    %s [shape=box,label="%s"]' % (loc[4:], node_label))
 166         elif loc in neighbors:
 167             print('    %s [label="%s"]' % (loc[4:], node_label))
 168
 169     # Draw arcs
 170     for (f, t) in links:
 171         arc = "%s -> %s" % (f[4:], t[4:])
 172         label=",".join(links[(f, t)]).lower()
 173         if len(label) > 0:
 174             arc += ' [label="%s"]' % label
 175         print("    " + arc)
 176     print("}")
 177
 178 # end