10 Room Maze

10-room-maze.py

# Quick dungeon

import random
import itertools
import math

DIR_VEC = {
    "n":  (0,  1, 0),
    "s":  (0, -1, 0),
    "e":  (1,  0, 0),
    "w":  (-1, 0, 0),
    "ne": (1,  1, 0),
    "nw": (-1, 1, 0),
    "se": (1, -1, 0),
    "sw": (-1,-1, 0),
    "u":  (0,  0, 1),
    "d":  (0,  0,-1),
}

def dot(a,b): return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]

def norm(v): return math.sqrt(dot(v,v))

def cos_sim(a,b):
    na, nb = norm(a), norm(b)
    return dot(a,b) / (na*nb)

def best_return_dir(b_free, dir_from_a):
    target = tuple(-x for x in DIR_VEC[dir_from_a])
    best = None
    best_score = -2.0
    for d in b_free:
        score = cos_sim(DIR_VEC[d], target)
        if score > best_score:
            best_score = score
            best = d
    return best, best_score

def add_pair(a, b, threshold):
    a_used = nodes[a]["exits"]
    b_used = nodes[b]["exits"]
    a_free = list(directions - a_used.keys())
    b_free = list(directions - b_used.keys())
    if not a_free or not b_free:
        return False  # ran out of direction slots

    random.shuffle(a_free)

    # try each possible outgoing dir from a, pick the best return dir in b
    best_choice = None  # (dir_a, dir_b, score)
    for dir_a in a_free:
        dir_b, score = best_return_dir(b_free, dir_a)
        if dir_b is None:
            continue
        if score >= threshold:
            # good enough; take first fit to keep it fast/varied
            nodes[a]["exits"][dir_a] = b
            nodes[b]["exits"][dir_b] = a
            return True
        # keep best in case we relax later (optional)
        if best_choice is None or score > best_choice[2]:
            best_choice = (dir_a, dir_b, score)

    return False

def solve_unsolved(unsolved_pairs):
    # passes: strict, near, rough, random
    passes = [
        (0.999999, "strict"),
        (0.707106, "near"),
        (0.0,      "rough"),
        (-2.0,     "random"),
    ]
    remaining = unsolved_pairs[:]
    for thr, name in passes:
        if not remaining:
            break
        next_remaining = []
        for a,b in remaining:
            ok = add_pair(a,b,thr)
            if not ok:
                next_remaining.append((a,b))
        remaining = next_remaining
    return remaining


directions = {'n','s','e','w','ne','nw','se','sw','u','d'}

inverse_dir = {
    'n':'s',
    's':'n',
    'e':'w',
    'w':'e',
    'ne':'sw',
    'nw':'se',
    'se':'nw',
    'sw':'ne',
    'u':'d',
    'd':'u'
}

secret_code = str(random.randint(1000, 9999))

start = 0
end = 11

# nodes = {i:{"exits":{e:0 for e in directions}} for i in range(12)}
nodes = {i:{"exits":{}, "desc": f"In room {i}."} for i in range(0,12)}

def rd_set(keys):
    unused_directions = list(directions.difference(keys))
    random.shuffle(unused_directions)
    return unused_directions

def room_set(values):
    unreachable_rooms = list(set(range(0,12)).difference(values))
    return unreachable_rooms

# def rd(keys):
#     return random.randint(0,len(keys))

nodes[0]["desc"] = "Maze Start (0)"

pairs = list(itertools.combinations(list(range(1,11)), 2))
random.shuffle(pairs)
pairs.insert(0, (0,1))
pairs.insert(1, (10,11))
unsolved_pairs = []

for a,b in pairs:
    # try strict first
    ok = add_pair(a,b,0.999999)
    if not ok:
        unsolved_pairs.append((a,b))

still_unsolved = solve_unsolved(unsolved_pairs)
if still_unsolved:
    print("Could not solve (ran out of direction slots):", still_unsolved)

# for a,b in pairs:
#     keys = nodes[a]["exits"].keys()
#     dir = None
#     opposite = None
#     # while not dir and not opposite and opposite not in nodes[b]["exits"]:
#     tries = 0
#     max_tries = 10
#     while not dir and not opposite or (inverse_dir[dir] not in nodes[b]["exits"] and tries < max_tries):
#         dir = rd_set(keys)[0]
#         opposite = inverse_dir[dir]
#         tries += 1
#     if inverse_dir[dir] in nodes[b]["exits"]:
#         # can't use this one directly, save for later
#         unsolved_pairs.append((a,b))
#     else:
#         nodes[a]["exits"] |= { dir: b }
#         nodes[b]["exits"] |= { opposite: a }
for room in range(2, 10):
    keys = nodes[room]["exits"].keys()
    loop_back = rd_set(keys)[0]
    nodes[room]["exits"][loop_back] = room

for room in range(0,12):
    keys = nodes[room]["exits"].keys()
    other_exits = rd_set(keys)
    values = nodes[room]["exits"].values()
    unreachable_rooms = room_set(values)
    print(room,"has other exits", other_exits)
    print(room,"can't reach", unreachable_rooms)

print(nodes)


# nodes[1]["exits"] = { e: door for e, door in zip(rd_set({}),range(10) )}

# for room in range(2,11):
#     keys = nodes[room]["exits"].keys()
#     nodes[room]["exits"] = {e: door for e, door in zip(rd_set(keys), range(room, 11))}

# room = 10
# keys = nodes[room]["exits"].keys()
# nodes[room]["exits"] = {e: door for e, door in zip(rd_set(keys), [11])}
# nodes[11]["desc"] = "Maze Exit (11)"


# nodes = {
#     "start":{
#         "desc":"In start",
#         "exits":{
#             "n": "finish",
#             "s": "a1",
#         }
#     },
#     "finish":{
#         "desc":"You see a keypad",
#         "exits":{
#             secret_code: "win",
#             "s":"start"
#         }
#     },
#     "a1":{
#         "desc":"South of maze",
#         "exits":{
#             "n": "start",
#             "e": "b1"
#         }
#     },
#     "b1":{
#         "desc": f"Side room, and you see scrawled on the wall '{secret_code}'",
#         "exits":{
#             "s":"a1"
#         }
#     }
# }

# Canonical direction order (NOT a set)
DIRECTION_ORDER = ("n","s","e","w","ne","nw","se","sw","u","d")
DIR_INDEX = {d:i for i,d in enumerate(DIRECTION_ORDER)}

def init_visit_state(nodes):
    for r, node in nodes.items():
        node.setdefault("visited", False)
        node.setdefault("traversed", {})  # dir -> bool


def ordered_dirs(iterable_dirs):
    return sorted(iterable_dirs, key=lambda d: DIR_INDEX.get(d, 10**9))

# Add once when building nodes
for rid in nodes:
    nodes[rid].setdefault("nick", str(rid))   # room nickname for map display
    nodes[rid].setdefault("visited", False)
    nodes[rid].setdefault("traversed", {})    # dir -> bool


def _fmt_dir_for_room(room, d, *, map_level):
    """
    Returns (shown_dir, shown_dest_or_blank)
    """
    trav = nodes[room].get("traversed", {})
    exits = nodes[room]["exits"]

    shown = d.upper() if (map_level >= 1 and trav.get(d, False)) else d

    # destination naming rules:
    # map_level 0/1: none
    # map_level 2: only if traversed
    # map_level >=3: always if exit exists
    show_dest = (map_level >= 3) or (map_level >= 2 and trav.get(d, False))

    if show_dest and d in exits:
        dest = exits[d]
        dest_nick = nodes[dest].get("nick", str(dest))
        return shown, dest_nick

    return shown, ""


def _cell(room, d, *, map_level, width=14):
    """
    Build a single cell like:
      "NE" or "NE Kitchen" (padded to width)
    If the exit doesn't exist, returns blanks.
    """
    exits = nodes[room]["exits"]
    if d not in exits:
        return " " * width

    shown, dest = _fmt_dir_for_room(room, d, map_level=map_level)
    text = f"{shown} {dest}".rstrip()
    return f"{text:<{width}}"


def _center(text, width):
    return f"{text:^{width}}"


def question_flat(msg, answers, *, room=None, map_level=0):
    """
    map_level:
      0 = no map decorations
      1 = capitalize traversed exits
      2 = capitalize traversed exits + show destination nick (only if traversed)
      3 = show destination nick always (optional upgrade)
    """
    resp = ""
    visible_answers = ordered_dirs(list(answers))
    if secret_code in visible_answers:
        visible_answers.remove(secret_code)

    if map_level and room is not None:
        trav = nodes[room].get("traversed", {})
        exits = nodes[room]["exits"]

        def fmt_dir(d):
            shown = d.upper() if (map_level >= 1 and trav.get(d, False)) else d
            if (map_level >= 2 and trav.get(d, False)) or (map_level >= 3):
                dest = exits[d]
                dest_nick = nodes[dest].get("nick", str(dest))
                return f"{shown} {dest_nick}"
            return shown

        visible_answers_disp = [fmt_dir(d) for d in visible_answers]
    else:
        visible_answers_disp = visible_answers

    visible_answers_str = "|".join(visible_answers_disp)

    valid = set(visible_answers) | {d.upper() for d in visible_answers}
    while resp not in valid:
        resp = input(f"{msg} [{visible_answers_str}] ").strip()
    return resp.lower()


def question_dpad(msg, answers, *, room=None, map_level=0, colw=16):
    """
    Same semantics as question_flat, but shows a DPAD view plus a compact input list.
    """
    resp = ""
    visible_answers = ordered_dirs(list(answers))
    if secret_code in visible_answers:
        visible_answers.remove(secret_code)

    if room is not None and map_level > 0:
        cur = nodes[room].get("nick", str(room))
        mid = _center(cur, colw)

        # 3-column layout (nw/n/ne), (w/cur/e), (sw/s/se)
        line1 = f"{'':<{colw}}{_center('U', colw)}{'':<{colw}}"
        line2 = f"{'':<{colw}}{_cell(room,'u',map_level=map_level,width=colw)}{'':<{colw}}"

        line3 = f"{_center('NW', colw)}{_center('N', colw)}{_center('NE', colw)}"
        line4 = f"{_cell(room,'nw',map_level=map_level,width=colw)}{_cell(room,'n',map_level=map_level,width=colw)}{_cell(room,'ne',map_level=map_level,width=colw)}"

        line5 = f"{_center('W', colw)}{mid}{_center('E', colw)}"
        line6 = f"{_cell(room,'w',map_level=map_level,width=colw)}{mid}{_cell(room,'e',map_level=map_level,width=colw)}"

        line7 = f"{_center('SW', colw)}{_center('S', colw)}{_center('SE', colw)}"
        line8 = f"{_cell(room,'sw',map_level=map_level,width=colw)}{_cell(room,'s',map_level=map_level,width=colw)}{_cell(room,'se',map_level=map_level,width=colw)}"

        line9  = f"{'':<{colw}}{_center('D', colw)}{'':<{colw}}"
        line10 = f"{'':<{colw}}{_cell(room,'d',map_level=map_level,width=colw)}{'':<{colw}}"

        print(msg)
        # print(line1);  
        print(line2)
        # print(line3);  
        print(line4)
        # print(line5);  
        print(line6)
        # print(line7);  
        print(line8)
        # print(line9);  
        print(line10)

    # keep a compact prompt too (user types direction only)
    # show decorated tokens (dir or DIR nick) in the bracket list
    if room is not None and map_level > 0:
        disp = []
        for d in visible_answers:
            shown, dest = _fmt_dir_for_room(room, d, map_level=map_level)
            token = f"{shown} {dest}".rstrip()
            disp.append(token)
        visible_answers_str = "|".join(disp)
    else:
        visible_answers_str = "|".join(visible_answers)

    valid = set(visible_answers) | {d.upper() for d in visible_answers}
    while resp not in valid:
        # resp = input(f"[{visible_answers_str}] ").strip()
        resp = input("? ").strip()
    return resp.lower()


def mark_traversal(a, dir_a, b):
    """Mark the exit dir_a from room a as traversed and also mark the corresponding exit in b."""
    nodes[a].setdefault("traversed", {})[dir_a] = True

    # find reverse direction by looking up which exit in b returns to a
    for dir_b, dest in nodes[b]["exits"].items():
        if dest == a:
            nodes[b].setdefault("traversed", {})[dir_b] = True
            break


def run(*, map_level=0):
    room = 0
    nodes[room]["visited"] = True

    while True:
        node = nodes[room]
        exits = node["exits"]

        # direction = question(node["desc"], exits.keys(), room=room, map_level=map_level)
        # direction = question_flat(node["desc"], exits.keys(), room=room, map_level=map_level)
        direction = question_dpad(node["desc"], exits.keys(), room=room, map_level=map_level)
        next_room = exits[direction]

        mark_traversal(room, direction, next_room)
        room = next_room
        nodes[room]["visited"] = True

        if room == 11:
            print(nodes[room]["desc"])
            print("You exited the dungeon!")
            break


def to_mermaid(nodes, *, direction="LR", include_desc=False):
    """
    Mermaid flowchart output for https://mermaid.live
    nodes: {id: {"exits": {dir: neighbor_id}, "desc": str}}
    """
    lines = [f"flowchart {direction}"]
    if include_desc:
        for nid, data in nodes.items():
            label = data.get("nick", f"room {nid}").replace('"', "'")
            lines.append(f'  {nid}["{label}"]')

    seen = set()  # undirected dedupe: (min,max,dir_from_min,dir_from_max) is overkill; keep simple pair dedupe
    for a, data in nodes.items():
        for d, b in data.get("exits", {}).items():
            # If your graph is bidirectional, suppress the reverse edge duplicate
            key = tuple(sorted((a, b)) + [d])  # keeps one of them; still shows label
            if (b, a) in seen:
                continue
            seen.add((a, b))
            lines.append(f'  {a} -- "{d}" --> {b}')
    return "\n".join(lines)

DIR_TO_PORT = {
    "n": "n", "ne": "ne", "e": "e", "se": "se",
    "s": "s", "sw": "sw", "w": "w", "nw": "nw",
    "u": "c", "d": "c",
}

def to_dot_with_ports(nodes, inverse_dir, *, graph_name="maze", rankdir="LR",
                      directed=True, include_desc=True, dedupe_bidirectional=True):
    g = "digraph" if directed else "graph"
    edgeop = "->" if directed else "--"

    lines = [f"{g} {graph_name} {{", f"  rankdir={rankdir};", '  node [shape=box];']

    if include_desc:
        for nid, data in nodes.items():
            label = data.get("nick", f"room {nid}").replace('"', r'\"')
            lines.append(f'  {nid} [label="{label}"];')

    seen = set()
    for a, data in nodes.items():
        for d, b in data.get("exits", {}).items():
            if dedupe_bidirectional and (b, a) in seen:
                continue
            seen.add((a, b))

            tail = DIR_TO_PORT.get(d, "c")
            head = DIR_TO_PORT.get(inverse_dir.get(d, d), "c")

            # node:compass syntax mounts the edge on that side/corner
            # label shows your direction name
            lines.append(f'  {a}:{tail} {edgeop} {b}:{head} [label="{d}"];')

    lines.append("}")
    return "\n".join(lines)


# --- Themes (each has exactly 10 names for rooms 1..10) ---
# --- Airport ---
AIRPORT = [
    "Terminal","Gate","Concourse","Security",
    "Baggage Claim","Ticketing","Customs",
    "Lounge","Restrooms","Control Tower"
]

# --- US Cities ---
US_CITIES = [
    "New York","Los Angeles","Chicago","Houston",
    "Phoenix","Philadelphia","San Antonio",
    "San Diego","Dallas","San Jose"
]

# --- Zoo ---
ZOO = [
    "Entrance","Savannah","Reptile House","Aviary",
    "Big Cats","Primate House","Aquarium",
    "Insect House","Petting Zoo","Food Plaza"
]

# --- Aquarium / Sea World ---
AQUARIUM = [
    "Coral Reef","Open Ocean","Shark Tunnel","Kelp Forest",
    "Touch Pool","Penguin Habitat","Jellyfish Gallery",
    "Seahorse Bay","Dolphin Lagoon","Research Lab"
]

# --- Jurassic Park ---
JURASSIC_PARK = [
    "Visitor Center","Raptor Paddock","Tyrannosaur Enclosure",
    "Control Room","Genetics Lab","Maintenance Shed",
    "Power Station","Helipad","Safari Trail","Dock"
]

# --- Home Depot Aisles ---
HOME_DEPOT = [
    "Lumber","Plumbing","Electrical","Paint",
    "Hardware","Flooring","Garden",
    "Appliances","Lighting","Tool Rental"
]

# --- Department Store Aisles ---
DEPARTMENT_STORE = [
    "Entrance","Men's Wear","Women's Wear","Shoes",
    "Accessories","Cosmetics","Housewares",
    "Electronics","Kids","Checkout"
]

# --- Disney Land / Disney World ---
DISNEY = [
    "Main Street","Adventureland","Frontierland",
    "Fantasyland","Tomorrowland","Liberty Square",
    "New Orleans Square","Toontown","Galaxy's Edge","Castle"
]

# --- Lego Land ---
LEGOLAND = [
    "Miniland","Brick Factory","Pirate Shores",
    "Adventure Zone","Kingdoms","Ninjago World",
    "Imagination Zone","Technic Coaster","Water Park","Entrance Plaza"
]

# --- Wonders of the World ---
WONDERS = [
    "Great Pyramid","Hanging Gardens","Statue of Zeus",
    "Temple of Artemis","Mausoleum","Colossus",
    "Lighthouse","Machu Picchu","Taj Mahal","Petra"
]

# --- Master Planned Community ---
MASTER_COMMUNITY = [
    "Main Gate","Town Center","Clubhouse","Pool",
    "Park","Elementary School","Shopping Plaza",
    "Walking Trail","Community Lake","Sales Office"
]

# --- Major Department Stores / Franchises ---
DEPARTMENT_CHAINS = [
    "Macy's","Target","Walmart","Costco",
    "Nordstrom","Kohl's","IKEA",
    "Best Buy","HomeGoods","TJ Maxx"
]

# --- Major Fast Food Chains ---
FAST_FOOD = [
    "McDonald's","Burger King","Wendy's","Taco Bell",
    "KFC","Subway","Chick-fil-A",
    "In-N-Out","Popeyes","Arby's"
]

# --- Major Restaurant Chains ---
RESTAURANT_CHAINS = [
    "Olive Garden","Applebee's","Chili's","IHOP",
    "Denny's","Red Lobster","Cheesecake Factory",
    "Outback","Buffalo Wild Wings","Cracker Barrel"
]

# --- Holiday Themed Town ---
HOLIDAY_TOWN = [
    "Town Square","Candy Cane Lane","Toy Workshop",
    "Clock Tower","Graveyard Hill","Pumpkin Patch",
    "Town Hall","Snow Plaza","Holiday Market","North Gate"
]

# --- Locations in The Simpsons ---
SIMPSONS = [
    "Simpson House","Kwik-E-Mart","Springfield Elementary",
    "Moe's Tavern","Nuclear Plant","Town Hall",
    "Android's Dungeon","Krusty Burger","City Jail","Evergreen Terrace"
]

# --- Locations in StrongBadia ---
STRONGBADIA = [
    "Strong House","The Stick","Bubs' Concession",
    "The Field","The Pit","StrongBadia Border",
    "Marzipan's","Coach Z's","King of Town","Computer Room"
]

# --- Sections of a Library ---
LIBRARY_SECTIONS = [
    "Entrance","Reference","Stacks","Reading Room",
    "Periodicals","Archives","Children's",
    "Media Center","Study Carrels","Circulation Desk"
]

# --- Bureaucratic Building Departments ---
BUREAUCRACY = [
    "Lobby","Information Desk","Permits Office",
    "Records","Finance","Human Resources",
    "Legal","Compliance","Director's Office","Break Room"
]

# --- School Rooms / Departments ---
SCHOOL = [
    "Front Office","Classroom","Science Lab","Library",
    "Gym","Cafeteria","Auditorium",
    "Nurse's Office","Counseling","Playground"
]

# --- College / University Campus ---
COLLEGE = [
    "Quad","Lecture Hall","Library","Student Union",
    "Dormitory","Science Building","Administration",
    "Gymnasium","Cafeteria","Observatory"
]

# --- Food Court Layout ---
FOOD_COURT = [
    "Entrance","Pizza Counter","Burger Grill","Asian Kitchen",
    "Mexican Grill","Salad Bar","Dessert Stand",
    "Coffee Kiosk","Seating Area","Trash Station"
]

THEMES = {
    "clue": [
        "Hall","Lounge","Dining","Kitchen","Ballroom",
        "Conservatory","Billiard","Library","Study","Cellar"
    ],
    "mansion": [
        "Hall","Parlor","Dining","Kitchen","Ballroom",
        "Garden","Gallery","Library","Study","Vault"
    ],
    "dungeon": [
        "Entry","Armory","Library","Chapel","Vault",
        "Forge","Garden","Hall","Cellar","Sanctum"
    ],
    "Airport": AIRPORT,
    "US Cities": US_CITIES,
    "Zoo": ZOO,
    "Aquarium / Sea World": AQUARIUM,
    "Jurassic Park": JURASSIC_PARK,
    "Home Depot": HOME_DEPOT,
    "Departments": DEPARTMENT_STORE,
    "Disney": DISNEY,
    "Lego Land": LEGOLAND,
    "Wonders of the World": WONDERS,
    "Community": MASTER_COMMUNITY,
    "Department Stores": DEPARTMENT_CHAINS,
    "Fast Food": FAST_FOOD,
    "Restaurant": RESTAURANT_CHAINS,
    "Holidays": HOLIDAY_TOWN,
    "Simpsons": SIMPSONS,
    "StrongBad": STRONGBADIA,
    "Library": LIBRARY_SECTIONS,
    "Bureaucracy": BUREAUCRACY,
    "School": SCHOOL,
    "College Campus": COLLEGE,
    "Food Court": FOOD_COURT,
}

def assign_room_theme(nodes, *, start_id=0, end_id=11):
    """
    Randomly choose a theme and assign nodes[r]["nick"] + nodes[r]["desc"].
    Rooms 1..10 get themed names; 0 and 11 get fixed names.
    Returns the chosen theme name.
    """
    theme_name = random.choice(list(THEMES.keys()))
    names = THEMES[theme_name].copy()
    random.shuffle(names)

    # fixed endpoints
    nodes[start_id]["nick"] = "Start"
    nodes[start_id]["desc"] = "Maze Start"
    nodes[end_id]["nick"] = "Exit"
    nodes[end_id]["desc"] = "Maze Exit"

    # assign 10 themed names to rooms 1..10
    for rid, room_name in zip(range(1, 11), names):
        nodes[rid]["nick"] = room_name
        nodes[rid]["desc"] = f"You are in the {room_name}."

    return theme_name


if __name__ == "__main__":
    # print("\n"*3)
    # print(to_mermaid(nodes, direction="LR", include_desc=True))
    print("\n"*3)
    # print(to_dot(nodes, include_desc=True, directed=True))
    print(to_dot_with_ports(nodes, inverse_dir, directed=True, include_desc=True))
    print("\n"*3)
    
    theme = assign_room_theme(nodes)
    print(f"Theme: {theme}")
    
    try:
        run(map_level=3)
    except KeyboardInterrupt:
        print("\nThanks for playing")
        raise SystemExit(0)