lttp.js

class Node {
  constructor(area, itemCount, smallKeyCount, dungeonPrizeCount) {
    this.area_ = area;
    this.itemCount_ = itemCount;
    this.smallKeyCount_ = smallKeyCount;
    this.dungeonPrizeCount_ = dungeonPrizeCount;
    this.edgesOut_ = [];
  }
};

function N(a,b,c,d) {
  return new Node(a,b,c,d);
}

class Edge {
  constructor(nodeFrom, nodeTo, requirements, bidirectional) {
    this.nodeFrom_ = nodeFrom;
    this.nodeTo_ = nodeTo;
    this.requirements_ = requirements;
    this.bidirectional_ = bidirectional;
  }
};

function E(nodeFrom, nodeTo, requirements, bidirectional) {
  var e = new Edge(Nodes[nodeFrom], Nodes[nodeTo], requirements || [], bidirectional !== false);
  Nodes[nodeFrom].edgesOut_.push(e);
  if (bidirectional) {
    Nodes[nodeTo].edgesOut_.push(e);
  }
  return e;
}

let Items = [
  'L1Sword',
  'L2Sword',
  'L3Sword',
  'L4Sword',
  'Bow',
  'Hammer',
  'Lamp',
  'L1Gloves',
  'L2Gloves',
  'MoonPearl',
  'FireRod',
  'PODKey',
  'PODMap',
  'PODCompass',
  'PODBigKey',
  'EPMap',
  'EPCompass',
  'EPBigKey',
  'EPKey',
  'Boots'
];

let Enemies = {
  'Popo': ['L1Sword', 'L2Sword', 'L3Sword', 'L4Sword', 'Hammer', 'FireRod', 'Bow'],
  'Terrorpin': ['Hammer'],
  'RedMimic': ['Bow'],
  'GreenMimic': ['L1Sword', 'L2Sword', 'L3Sword', 'L4Sword', 'Bow', 'Hammer', 'FireRod'],
  'ArmosKnights': ['L1Sword', 'L2Sword', 'L3Sword', 'L4Sword', 'Bow', 'Hammer'],
  'HelmasaurKing': ['Hammer'],
  'Bubble': [],
  'GreenEyegore': ['L1Sword', 'L2Sword', 'L3Sword', 'L4Sword', 'Hammer', 'Bow'],
  'RedEyegore': ['Bow'],
  'Stalfos': [],
};

// N(area, num_items, num_small_keys, num_dungeon_prizes)
let Nodes = [
/*  0 */  N('A'),
/*  1 */  N('U', 1),
/*  2 */  N('LW'),
/*  3 */  N('U'),
/*  4 */  N('U'),
/*  5 */  N('U', 3),
/*  6 */  N('EP', 3),
/*  7 */  N('EP', 1),
/*  8 */  N('EP', 0, 1),
/*  9 */  N('EP', 1),
/* 10 */  N('EP'),
/* 11 */  N('EP', 0, 1),
/* 12 */  N('EP', 1, 0, 1),
/* 13 */  N('DW'),
/* 14 */  N('U'),
/* 15 */  N('U'),
/* 16 */  N('U'),
/* 17 */  N('POD', 1),
/* 18 */  N('POD', 2),
/* 19 */  N('POD', 2),
/* 20 */  N('POD', 1),
/* 21 */  N('POD', 1),
/* 22 */  N('POD', 1),
/* 23 */  N('POD', 2),
/* 24 */  N('POD', 2),
/* 25 */  N('POD'),
/* 26 */  N('POD', 1),
/* 27 */  N('POD', 1, 0, 1),
/* 28 */  N('A', 1)
];

// E(node_from, node_to, requirements)
let Edges = [
  E(0, 1),
  E(1, 2),
  E(2, 3),
  E(2, 4),
  E(2, 5),
  E(2, 6),
  E(2, 13, [['Hammer', 'L1Gloves', 'MoonPearl'], ['Hammer', 'L2Gloves', 'MoonPearl']]),
  E(6, 7, ['EPBigKey']),
  E(6, 8, ['EPDarkRoom1']),
  E(6, 10, ['EPDarkRoom2', 'EPBigKey']),
  E(8, 9, ['GreenEyegore', 'Stalfos', 'Stalfos', 'Popo', 'Popo', 'Bubble', 'Bubble', 'Bubble', 'Bubble', 'EP Door']),
  E(10, 11, ['GreenEyegore']),
  E(10, 12, ['RedEyegore', 'RedEyegore', 'RedEyegore', 'Stalfos', 'Stalfos', 'Popo', 'Popo', 'Popo', 'Popo', 'Popo', 'Popo', 'EPDoor', 'ArmosKnights']),
  E(13, 14),
  E(13, 15),
  E(13, 16),
  E(13, 17),
  E(17, 18, ['PODDoor']),
  E(17, 19, ['RedMimic', 'GreenMimic', 'GreenMimic']),
  E(18, 19, ['Hover'], false),
  E(18, 20, ['PODDoor']),
  E(18, 21, ['PODDoor']),
  E(19, 18, ['Hammer'], false),
  E(19, 27, ['PODDoor', 'PODBigKey', 'RedMimic', 'GreenMimic', 'GreenMimic', 'Bow', 'Hammer', 'Terrorpin', 'Terrorpin', 'Terrorpin', 'Terrorpin', 'Terrorpin', 'Terrorpin', 'PODDarkRoomFinal', 'HelmasaurKing']),
  E(21, 22, ['PODDoor']),
  E(21, 23, ['PODDark Basement']),
  E(21, 24, ['PODDoor', 'PODDarkMaze']),
  E(21, 25, [['PODHammerJump'], ['Hover']]),
  E(24, 25, ['PODDarkMaze']),
  E(25, 24, ['PODDarkMaze']),
  E(25, 26, ['PODBigKey']),
  E(0, 28, ['Crystal1', 'Crystal2'])
];

let map = {
  items: new WeakMap([
    [Nodes[ 1], ['L1Sword']],
    [Nodes[ 5], ['L2Sword', 'L3Sword', 'L4Sword']],
    [Nodes[ 6], ['Bow', 'Hammer', 'Lamp']],
    [Nodes[ 7], ['L1Gloves']],
    [Nodes[ 8], ['EPKey']],
    [Nodes[ 9], ['L2Gloves']],
    [Nodes[11], ['EPKey']],
    [Nodes[12], ['MoonPearl']],
    [Nodes[17], ['FireRod']],
    [Nodes[18], ['PODKey', 'PODKey']],
    [Nodes[19], ['PODKey', 'PODKey']],
    [Nodes[20], ['PODKey']],
    [Nodes[21], ['PODKey']],
    [Nodes[22], ['PODMap']],
    [Nodes[23], ['PODCompass', 'PODBigKey']],
    [Nodes[24], ['EPMap', 'EPCompass']],
    [Nodes[26], ['EPBigKey']],
    [Nodes[27], ['Boots']],
    [Nodes[28], ['Triforce']]
  ]),
  prizes: new WeakMap([
    [Nodes[12], 'Crystal1'],
    [Nodes[27], 'Crystal2']
  ])
};

function isValidMap(map) {
  // this probably needs better logic.
  // we need to support something that can handle very basic boolean logic
  // like the dark world entrace below eastern requires:
  // Hammer && MoonPearl && (L1Gloves || L2Gloves)
  // in the current implementation, this is represented by this:
  // ['Hammer', 'MoonPearl', ['L1Gloves', 'L2Gloves']]
  // so the first level is assumed to be && and subsequent levels are assumed to be ||.
  function isPassable(edge) {
    function isPassableSingle(req) {
      if (Array.isArray(req)) {
        return req.some(isPassableSingle);
      }
      if (Items.includes(req) || req.match(/Crystal/)) {
        if (!items.includes(req)) {
          return false;
        }
        return true;
      } else if (Enemies[req]) {
        var foo = !Enemies[req].some((v, i, a) => {
          return items.includes(v);
        });
        if (!Enemies[req].length || foo) {
          return false;
        }
        return true;
      } else if (req.match(/Dark/)) {
        if (!items.includes('Lamp')) {
          return false;
        }
        return true;
      } else if (req === 'Hover') {
        return false;
      } else if (req.match(/Jump/)) {
        return false;
      } else if (req.match(/Door/)) {
        return false;
      } else {
        throw Error('unknown requirement');
      }
      return true;
    }
    return edge.requirements_.every(isPassableSingle);
  }

  let items = [];
  let visitedEdges = [];
  let availableEdges = [];
  let visitedNodes = [];
  let availableNodes = [Nodes[0]];

  while (true) {
    while (availableNodes.length) {
      let node = availableNodes.pop();
      if (visitedNodes.includes(node)) {
        continue;
      }
      visitedNodes.push(node);
      if (map.items.has(node)) {
        items = items.concat(map.items.get(node));
      }
      if (map.prizes.has(node)) {
        items.push(map.prizes.get(node));
      }
      for (let i = 0; i < node.edgesOut_.length; i++) {
        let edgeOut = node.edgesOut_[i];
        if (visitedEdges.includes(edgeOut)) {
          continue;
        }
        if (visitedNodes.includes(edgeOut.nodeFrom_) && visitedNodes.includes(edgeOut.nodeTo_)) {
          // need to account for small keys in this situation.
          // this is an edge we haven't passed but don't need to because we have already visited both nodes.
          // if it has a small key requirement, it needs to be accounted for.
          continue;
        }
        if (node === edgeOut.nodeFrom_ && visitedNodes.includes(edgeOut.nodeTo_)) {
          continue;
        }
        if (node === edgeOut.nodeTo_ && visitedNodes.includes(edgeOut.nodeFrom_)) {
          continue;
        }
        if (isPassable(edgeOut)) {
          visitedEdges.push(edgeOut);
          if (node === edgeOut.nodeTo_) {
            availableNodes.push(edgeOut.nodeFrom_);
          } else if (node === edgeOut.nodeFrom_) {
            availableNodes.push(edgeOut.nodeTo_);
          } else {
            throw Error('weird edge thing just happened');
          }
        } else if (!availableEdges.includes(edgeOut)) {
          availableEdges.push(edgeOut);
        }
      }
    }

    let newAvailableEdges = [];
    for (let i = 0; i < availableEdges.length; i++) {
      let edge = availableEdges[i];
      if (isPassable(edge)) {
        visitedEdges.push(edge);
        if (!visitedNodes.includes(edge.nodeFrom_)) {
          availableNodes.push(edge.nodeFrom_);
        }
        if (!visitedNodes.includes(edge.nodeTo_)) {
          availableNodes.push(edge.nodeTo_);
        }
      } else {
        newAvailableEdges.push(edge);
      }
    }

    if (newAvailableEdges.length === availableEdges.length) {
      break;
    }
    availableEdges = newAvailableEdges;
  }
  return items.includes('Triforce');
}