make_graph.py

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