dungeon_canvas_connected_view.cc

Go to the documentation of this file.

#include "dungeon_canvas_viewer.h"
 
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
 
#include "absl/strings/str_format.h"
#include "app/editor/dungeon/dungeon_project_labels.h"
#include "zelda3/dungeon/draw_routines/draw_routine_registry.h"
 
namespace yaze::editor {
 
namespace {
 
bool IsHeaderBackedInterroomStaircaseObject(int16_t object_id) {
  const int routine_id =
      zelda3::DrawRoutineRegistry::Get().GetRoutineIdForObject(object_id);
  switch (routine_id) {
    case zelda3::DrawRoutineIds::kInterRoomFatStairsUp:
    case zelda3::DrawRoutineIds::kInterRoomFatStairsDownA:
    case zelda3::DrawRoutineIds::kInterRoomFatStairsDownB:
    case zelda3::DrawRoutineIds::kStraightInterRoomStairs:
    case zelda3::DrawRoutineIds::kSpiralStairsGoingUpUpper:
    case zelda3::DrawRoutineIds::kSpiralStairsGoingDownUpper:
    case zelda3::DrawRoutineIds::kSpiralStairsGoingUpLower:
    case zelda3::DrawRoutineIds::kSpiralStairsGoingDownLower:
      return true;
    default:
      return false;
  }
}
 
std::pair<int, int> ConnectedDoorDelta(zelda3::DoorDirection dir) {
  switch (dir) {
    case zelda3::DoorDirection::North:
      return {0, -1};
    case zelda3::DoorDirection::South:
      return {0, 1};
    case zelda3::DoorDirection::West:
      return {-1, 0};
    case zelda3::DoorDirection::East:
      return {1, 0};
  }
  return {0, 0};
}
 
bool IsConnectedSlotOccupied(
    const std::map<std::pair<int, int>, int>& occupied_slots, int col,
    int row) {
  return occupied_slots.contains({col, row});
}
 
std::pair<int, int> FindConnectedDoorPlacement(
    const std::map<std::pair<int, int>, int>& occupied_slots, int source_col,
    int source_row, zelda3::DoorDirection dir) {
  const auto [dx, dy] = ConnectedDoorDelta(dir);
  int best_score = std::numeric_limits<int>::max();
  std::pair<int, int> best = {source_col + dx, source_row + dy};
 
  for (int radius = 1; radius <= 24; ++radius) {
    for (int row = source_row - radius; row <= source_row + radius; ++row) {
      for (int col = source_col - radius; col <= source_col + radius; ++col) {
        if (IsConnectedSlotOccupied(occupied_slots, col, row)) {
          continue;
        }
 
        const int rel_col = col - source_col;
        const int rel_row = row - source_row;
        const int forward = (rel_col * dx) + (rel_row * dy);
        if (forward <= 0) {
          continue;
        }
 
        const int lateral = std::abs((rel_col * dy) - (rel_row * dx));
        const int distance_from_ideal =
            std::abs(rel_col - dx) + std::abs(rel_row - dy);
        const int overshoot = std::max(0, forward - 1);
        const int score =
            (distance_from_ideal * 16) + (lateral * 20) + (overshoot * 6);
        if (score < best_score) {
          best_score = score;
          best = {col, row};
        }
      }
    }
    if (best_score != std::numeric_limits<int>::max()) {
      return best;
    }
  }
 
  return best;
}
 
std::pair<int, int> FindConnectedTransportPlacement(
    const std::map<std::pair<int, int>, int>& occupied_slots, int source_col,
    int source_row) {
  int best_score = std::numeric_limits<int>::max();
  std::pair<int, int> best = {source_col + 1, source_row + 1};
 
  for (int radius = 1; radius <= 24; ++radius) {
    for (int row = source_row - radius; row <= source_row + radius; ++row) {
      for (int col = source_col - radius; col <= source_col + radius; ++col) {
        if (IsConnectedSlotOccupied(occupied_slots, col, row)) {
          continue;
        }
 
        const int rel_col = col - source_col;
        const int rel_row = row - source_row;
        const int distance = std::abs(rel_col) + std::abs(rel_row);
        if (distance == 0) {
          continue;
        }
 
        const bool diagonal = rel_col != 0 && rel_row != 0;
        const bool axis_aligned = rel_col == 0 || rel_row == 0;
        const int distance_bias = std::abs(distance - 2);
        const int score = (distance_bias * 10) +
                          (diagonal       ? 0
                           : axis_aligned ? 8
                                          : 4) +
                          ((std::abs(rel_col) + std::abs(rel_row)) > 3 ? 4 : 0);
        if (score < best_score) {
          best_score = score;
          best = {col, row};
        }
      }
    }
    if (best_score != std::numeric_limits<int>::max()) {
      return best;
    }
  }
 
  return best;
}
 
// Dedup key for the connected-mode graph.
//
// Door / Holewarp links are undirected — emitting from either side produces
// the same logical edge — so we order the room pair (minmax) and treat both
// emissions as one. There can only be one of either type per room pair.
//
// Staircase links carry per-instance provenance (slot_index + object_id) and
// are *directed*: a stair object lives in exactly one room and points to
// another. Two stair objects in the same source room targeting the same
// destination, or two reciprocal stairs (A->B at slot 0 + B->A at slot 1),
// are distinct edges that must each be visible in the matrix. Including
// from_room/slot_index/object_id in the key preserves them.
std::tuple<int, int, DungeonConnectedLinkType, int, int16_t>
MakeConnectedLinkKey(const DungeonConnectedRoomLink& link) {
  if (link.type == DungeonConnectedLinkType::Staircase) {
    return std::make_tuple(link.from_room_id, link.to_room_id, link.type,
                           link.slot_index, link.object_id);
  }
  const auto ordered_rooms = std::minmax(link.from_room_id, link.to_room_id);
  return std::make_tuple(ordered_rooms.first, ordered_rooms.second, link.type,
                         -1, static_cast<int16_t>(-1));
}
 
}  // namespace
 
DungeonConnectedRoomLinkDiagnostics CollectDungeonConnectedRoomLinkDiagnostics(
    int room_id, const zelda3::Room& room,
    const std::function<bool(int, zelda3::DoorDirection)>&
        has_reciprocal_door) {
  DungeonConnectedRoomLinkDiagnostics result;
 
  const auto& doors = room.GetDoors();
  for (size_t door_index = 0; door_index < doors.size(); ++door_index) {
    const auto& door = doors[door_index];
    if (!zelda3::IsRoomConnectionDoorType(door.type)) {
      continue;
    }
 
    const int neighbor = NeighborRoomId(room_id, door.direction);
    if (neighbor < 0) {
      continue;
    }
    if (has_reciprocal_door &&
        !has_reciprocal_door(neighbor, OppositeDir(door.direction))) {
      continue;
    }
 
    DungeonConnectedRoomLink link;
    link.from_room_id = room_id;
    link.to_room_id = neighbor;
    link.type = DungeonConnectedLinkType::Door;
    link.direction = door.direction;
    link.door_index = static_cast<int>(door_index);
    link.door_type = door.type;
    result.links.push_back(link);
  }
 
  // Provisional navigation only: placement order is not a verified runtime
  // slot mapping. Vanilla writers use family-specific counters ($0438,
  // $047E/$0482, $04A2/$04A4, $043A, $0480/$0484, $04A6/$04A8) into $06B0.
  // Collision generation assigns indices later; $0462 & 3 selects the header.
  // Do not use these estimates to mutate or clear room metadata.
  std::array<bool, 4> slot_consumed{false, false, false, false};
  std::array<int16_t, 4> slot_object_id{
      static_cast<int16_t>(-1), static_cast<int16_t>(-1),
      static_cast<int16_t>(-1), static_cast<int16_t>(-1)};
  int next_slot = 0;
  for (const auto& object : room.GetTileObjects()) {
    if (!IsHeaderBackedInterroomStaircaseObject(object.id_)) {
      continue;
    }
    if (next_slot >= 4) {
      DungeonStaircaseIssue extra;
      extra.from_room_id = room_id;
      extra.kind = DungeonStaircaseIssueKind::ExtraPlacedObject;
      extra.object_id = object.id_;
      result.staircase_issues.push_back(extra);
      continue;
    }
    slot_consumed[next_slot] = true;
    slot_object_id[next_slot] = object.id_;
    ++next_slot;
  }
 
  for (int slot = 0; slot < 4; ++slot) {
    // Room 000 is a valid destination. The runtime writes the header byte to
    // $A0 and keeps $A1, so $119 slot $1D leads to $11D; zero is not a
    // sentinel for a consumed slot.
    const int stair_room = room.staircase_destination_room(slot);
    const bool header_valid =
        stair_room >= 0 && stair_room < zelda3::kNumberOfRooms;
    if (slot_consumed[slot]) {
      if (header_valid) {
        DungeonConnectedRoomLink link;
        link.from_room_id = room_id;
        link.to_room_id = stair_room;
        link.type = DungeonConnectedLinkType::Staircase;
        link.direction = zelda3::DoorDirection::North;
        link.slot_index = slot;
        link.object_id = slot_object_id[slot];
        result.links.push_back(link);
      } else {
        DungeonStaircaseIssue issue;
        issue.from_room_id = room_id;
        issue.kind = DungeonStaircaseIssueKind::MissingDestination;
        issue.slot_index = slot;
        issue.header_room_id = stair_room;
        issue.object_id = slot_object_id[slot];
        result.staircase_issues.push_back(issue);
      }
    } else if (header_valid && room.staircase_room(slot) != 0) {
      DungeonStaircaseIssue issue;
      issue.from_room_id = room_id;
      issue.kind = DungeonStaircaseIssueKind::UnusedHeader;
      issue.slot_index = slot;
      issue.header_room_id = stair_room;
      result.staircase_issues.push_back(issue);
    }
  }
 
  const int holewarp_room = room.holewarp_destination_room();
  if (room.holewarp() != 0 && holewarp_room < zelda3::kNumberOfRooms) {
    DungeonConnectedRoomLink link;
    link.from_room_id = room_id;
    link.to_room_id = holewarp_room;
    link.type = DungeonConnectedLinkType::Holewarp;
    link.direction = zelda3::DoorDirection::North;
    result.links.push_back(link);
  }
 
  return result;
}
 
std::vector<DungeonConnectedRoomLink> CollectDungeonConnectedRoomLinks(
    int room_id, const zelda3::Room& room,
    const std::function<bool(int, zelda3::DoorDirection)>&
        has_reciprocal_door) {
  return CollectDungeonConnectedRoomLinkDiagnostics(room_id, room,
                                                    has_reciprocal_door)
      .links;
}
 
namespace {
 
const char* DoorDirectionLabel(zelda3::DoorDirection dir) {
  switch (dir) {
    case zelda3::DoorDirection::North:
      return "North";
    case zelda3::DoorDirection::South:
      return "South";
    case zelda3::DoorDirection::West:
      return "West";
    case zelda3::DoorDirection::East:
      return "East";
  }
  return "?";
}
 
}  // namespace
 
std::string FormatDungeonConnectedLinkDescription(
    const DungeonConnectedRoomLink& link) {
  switch (link.type) {
    case DungeonConnectedLinkType::Door:
      return absl::StrFormat("Door (%s, type 0x%02X) -> [%03X]",
                             DoorDirectionLabel(link.direction),
                             static_cast<unsigned>(link.door_type),
                             static_cast<unsigned>(link.to_room_id));
    case DungeonConnectedLinkType::Staircase: {
      std::string object_str =
          (link.object_id >= 0)
              ? absl::StrFormat("0x%03X", static_cast<unsigned>(link.object_id))
              : std::string("(unknown)");
      const int slot_index = link.slot_index >= 0 ? link.slot_index : -1;
      if (slot_index < 0) {
        return absl::StrFormat("Estimated staircase obj %s -> [%03X]",
                               object_str,
                               static_cast<unsigned>(link.to_room_id));
      }
      return absl::StrFormat("Estimated staircase slot %d obj %s -> [%03X]",
                             slot_index, object_str,
                             static_cast<unsigned>(link.to_room_id));
    }
    case DungeonConnectedLinkType::Holewarp:
      return absl::StrFormat("Holewarp -> [%03X]",
                             static_cast<unsigned>(link.to_room_id));
  }
  return absl::StrFormat("Link -> [%03X]",
                         static_cast<unsigned>(link.to_room_id));
}
 
std::string FormatDungeonStaircaseIssueDescription(
    const DungeonStaircaseIssue& issue) {
  switch (issue.kind) {
    case DungeonStaircaseIssueKind::UnusedHeader:
      return absl::StrFormat(
          "Possibly unused staircase slot %d -> [%03X] (no placed "
          "interroom-stair "
          "object consumes this slot)",
          issue.slot_index, static_cast<unsigned>(issue.header_room_id));
    case DungeonStaircaseIssueKind::MissingDestination: {
      const std::string object_str =
          (issue.object_id >= 0)
              ? absl::StrFormat("0x%03X",
                                static_cast<unsigned>(issue.object_id))
              : std::string("(unknown)");
      const std::string header_str = absl::StrFormat(
          "0x%03X (out of range)", static_cast<unsigned>(issue.header_room_id));
      return absl::StrFormat(
          "Estimated missing staircase destination at slot %d (placed object "
          "%s, "
          "header value %s)",
          issue.slot_index, object_str, header_str);
    }
    case DungeonStaircaseIssueKind::ExtraPlacedObject: {
      const std::string object_str =
          (issue.object_id >= 0)
              ? absl::StrFormat("0x%03X",
                                static_cast<unsigned>(issue.object_id))
              : std::string("(unknown)");
      return absl::StrFormat(
          "Additional staircase object %s beyond the estimated 4 slots "
          "(runtime mapping unverified)",
          object_str);
    }
  }
  return std::string("Unknown staircase issue");
}
 
zelda3::Room* DungeonCanvasViewer::EnsureRoomLoadedForConnectedView(
    int room_id) {
  if (!rooms_ || !rom_ || !rom_->is_loaded() || room_id < 0 ||
      room_id >= zelda3::kNumberOfRooms) {
    return nullptr;
  }
 
  auto* room_ptr = rooms_->TryEnsureRoom(room_id);
  if (!room_ptr) {
    return nullptr;
  }
  auto& room = *room_ptr;
  room.SetRom(rom_);
  room.SetGameData(game_data_);
  if (!room.IsLoaded()) {
    room = zelda3::LoadRoomFromRom(rom_, room_id);
    room.SetGameData(game_data_);
  }
  return &room;
}
 
bool DungeonCanvasViewer::RoomHasNonExitDoorInDirection(
    int room_id, zelda3::DoorDirection dir) {
  zelda3::Room* room = EnsureRoomLoadedForConnectedView(room_id);
  if (!room) {
    return false;
  }
 
  for (const auto& door : room->GetDoors()) {
    if (door.direction == dir && zelda3::IsRoomConnectionDoorType(door.type)) {
      return true;
    }
  }
  return false;
}
 
DungeonCanvasViewer::ConnectedRoomGraphData
DungeonCanvasViewer::BuildConnectedRoomGraph(int start_room_id) {
  ConnectedRoomGraphData graph;
  if (start_room_id < 0 || start_room_id >= zelda3::kNumberOfRooms) {
    return graph;
  }
 
  zelda3::Room* start_room = EnsureRoomLoadedForConnectedView(start_room_id);
  if (!start_room) {
    return graph;
  }
 
  // Project-aware scoping: when the project registry maps the start room to
  // a dungeon entry, restrict BFS to that dungeon's rooms by default.
  // Cross-blockset / cross-dungeon resolved links are still surfaced via
  // out_of_scope_links so the diagnostic remains visible without polluting
  // the visual matrix with rooms from other dungeons.
  std::set<int> scoped_room_ids;
  std::map<int, const core::DungeonRoom*> scoped_rooms_by_id;
  if (const auto* dungeon =
          dungeon_project_labels::FindDungeonForRoom(project_, start_room_id)) {
    graph.dungeon_scope_active = true;
    for (const auto& dungeon_room : dungeon->rooms) {
      if (dungeon_room.id < 0 || dungeon_room.id >= zelda3::kNumberOfRooms) {
        continue;
      }
      scoped_room_ids.insert(dungeon_room.id);
      scoped_rooms_by_id[dungeon_room.id] = &dungeon_room;
      graph.room_floor_labels[static_cast<size_t>(dungeon_room.id)] =
          dungeon_room.floor;
      if (!dungeon_room.floor.empty() &&
          std::find(graph.floor_order.begin(), graph.floor_order.end(),
                    dungeon_room.floor) == graph.floor_order.end()) {
        graph.floor_order.push_back(dungeon_room.floor);
      }
    }
  }
 
  std::map<std::pair<int, int>, int> occupied_slots;
  std::queue<int> to_visit;
  std::set<std::tuple<int, int, DungeonConnectedLinkType, int, int16_t>>
      seen_links;
 
  auto track_room_bounds = [&](int room_id) {
    const auto& placement = graph.room_positions[static_cast<size_t>(room_id)];
    graph.min_col = std::min(graph.min_col, placement.col);
    graph.max_col = std::max(graph.max_col, placement.col);
    graph.min_row = std::min(graph.min_row, placement.row);
    graph.max_row = std::max(graph.max_row, placement.row);
  };
 
  auto registry_placement_for =
      [&](int room_id) -> std::optional<std::pair<int, int>> {
    const auto it = scoped_rooms_by_id.find(room_id);
    if (it == scoped_rooms_by_id.end() || !it->second->has_grid_position) {
      return std::nullopt;
    }
    return std::make_pair(it->second->grid_col, it->second->grid_row);
  };
 
  auto place_room = [&](int room_id, std::pair<int, int> desired_placement,
                        bool connected_to_start) {
    if (room_id < 0 || room_id >= zelda3::kNumberOfRooms) {
      return;
    }
    const size_t index = static_cast<size_t>(room_id);
    if (graph.room_mask[index]) {
      if (connected_to_start &&
          !graph.room_positions[index].connected_to_start) {
        graph.room_positions[index].connected_to_start = true;
        graph.unlinked_room_count = std::max(0, graph.unlinked_room_count - 1);
      }
      return;
    }
 
    std::pair<int, int> placement = desired_placement;
    const auto occupied = occupied_slots.find(placement);
    if (occupied != occupied_slots.end() && occupied->second != room_id) {
      placement = FindConnectedTransportPlacement(
          occupied_slots, desired_placement.first, desired_placement.second);
    }
 
    graph.room_mask[index] = true;
    graph.room_positions[index] = {placement.first, placement.second, true,
                                   connected_to_start};
    occupied_slots[placement] = room_id;
    ++graph.room_count;
    if (!connected_to_start) {
      ++graph.unlinked_room_count;
    }
    if (graph.room_count == 1) {
      graph.min_col = graph.max_col = placement.first;
      graph.min_row = graph.max_row = placement.second;
    } else {
      track_room_bounds(room_id);
    }
  };
 
  auto in_dungeon_scope = [&](int candidate_room_id) {
    if (!graph.dungeon_scope_active) {
      return true;
    }
    return scoped_room_ids.find(candidate_room_id) != scoped_room_ids.end();
  };
 
  place_room(
      start_room_id,
      registry_placement_for(start_room_id).value_or(std::make_pair(0, 0)),
      true);
  to_visit.push(start_room_id);
 
  while (!to_visit.empty()) {
    const int room_id = to_visit.front();
    to_visit.pop();
 
    zelda3::Room* room = EnsureRoomLoadedForConnectedView(room_id);
    if (!room) {
      continue;
    }
 
    const auto outgoing_diagnostics =
        CollectDungeonConnectedRoomLinkDiagnostics(
            room_id, *room,
            [this](int neighbor_room_id, zelda3::DoorDirection dir) {
              return RoomHasNonExitDoorInDirection(neighbor_room_id, dir);
            });
    for (const auto& issue : outgoing_diagnostics.staircase_issues) {
      graph.staircase_issues.push_back(issue);
    }
    const auto& outgoing_links = outgoing_diagnostics.links;
 
    for (const auto& link : outgoing_links) {
      if (link.to_room_id < 0 || link.to_room_id >= zelda3::kNumberOfRooms) {
        continue;
      }
 
      // Out-of-scope link (target room is not in the current dungeon group):
      // record as a diagnostic, do not recurse, do not add the target to the
      // visual graph. We still de-dup against `seen_links` so a reciprocal
      // edge from the other side won't double-list it later.
      if (!in_dungeon_scope(link.to_room_id)) {
        if (seen_links.insert(MakeConnectedLinkKey(link)).second) {
          graph.out_of_scope_links.push_back(link);
        }
        continue;
      }
 
      if (!EnsureRoomLoadedForConnectedView(link.to_room_id)) {
        continue;
      }
 
      if (seen_links.insert(MakeConnectedLinkKey(link)).second) {
        graph.links.push_back(link);
      }
 
      if (!graph.room_mask[static_cast<size_t>(link.to_room_id)]) {
        const auto& source_placement =
            graph.room_positions[static_cast<size_t>(room_id)];
        const std::pair<int, int> placement =
            registry_placement_for(link.to_room_id)
                .value_or((link.type == DungeonConnectedLinkType::Door)
                              ? FindConnectedDoorPlacement(
                                    occupied_slots, source_placement.col,
                                    source_placement.row, link.direction)
                              : FindConnectedTransportPlacement(
                                    occupied_slots, source_placement.col,
                                    source_placement.row));
        place_room(link.to_room_id, placement, true);
        to_visit.push(link.to_room_id);
      }
    }
  }
 
  // In project-scoped mode, connected view should show the whole dungeon group,
  // not only the currently reachable component. Unlinked rooms are drawn in the
  // same canvas with floor badges so bad headers/stairs are visible and fixable
  // instead of hiding the rest of the floor.
  if (graph.dungeon_scope_active) {
    const auto start_placement =
        graph.room_positions[static_cast<size_t>(start_room_id)];
    for (int room_id : scoped_room_ids) {
      if (graph.room_mask[static_cast<size_t>(room_id)]) {
        continue;
      }
      // Project registry entries can name rooms that have never been opened.
      // Materialize their ROM data before placing them in the preview graph;
      // otherwise the renderer sees a default Room with ID zero.
      if (!EnsureRoomLoadedForConnectedView(room_id)) {
        continue;
      }
      const std::pair<int, int> placement =
          registry_placement_for(room_id).value_or(
              FindConnectedTransportPlacement(
                  occupied_slots, start_placement.col, start_placement.row));
      place_room(room_id, placement, false);
    }
  }
 
  return graph;
}
 
int DungeonCanvasViewer::ApplyConnectedStaircaseIssueAutoFixes(
    int center_room_id) {
  // Retain a non-mutating guard for legacy callers until the runtime mapping
  // is implemented. Neither cached diagnostics nor a fresh estimate proves
  // that a destination is unused.
  (void)center_room_id;
  connected_action_status_message_ =
      "Automatic staircase repair is unavailable: slot mapping is unverified. "
      "Review destinations in the room inspector.";
  connected_action_status_is_error_ = true;
  return 0;
}
 
}  // namespace yaze::editor