portal_route.h

#pragma once
 
#include <tess/path/path.h>
#include <tess/path/portal_segment_cache.h>
 
#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <vector>
 
namespace tess {
 
namespace detail {
 
template <typename World, typename Class>
[[nodiscard]] auto weighted_endpoint_failure(const World& world,
                                             PathRequest request)
    -> std::optional<PathStatus> {
  using Shape = typename World::shape_type;
  if (!contains<Shape>(request.start) ||
      !is_passable<World, Class>(world, request.start)) {
    return PathStatus::InvalidStart;
  }
  if (!contains<Shape>(request.goal) ||
      !is_passable<World, Class>(world, request.goal)) {
    return PathStatus::InvalidGoal;
  }
  const auto start = tile_index<Shape>(request.start);
  const auto goal = tile_index<Shape>(request.goal);
  if (tile_entry_cost_index<World, Class>(world, start) == 0) {
    return PathStatus::InvalidStart;
  }
  if (tile_entry_cost_index<World, Class>(world, goal) == 0) {
    return PathStatus::InvalidGoal;
  }
  return std::nullopt;
}
 
template <typename World, typename Class>
[[nodiscard]] auto build_greedy_chunk_portal_candidate(
    const World& world, PathRequest request, std::vector<Coord3>& waypoints)
    -> PortalRouteCandidate {
  using Shape = typename World::shape_type;
 
  waypoints.clear();
  auto current = request.start;
  auto current_chunk = chunk_coord<Shape>(request.start);
  const auto goal_chunk = chunk_coord<Shape>(request.goal);
  auto result = PortalRouteCandidate{true, 0, 0};
 
  while (current_chunk != goal_chunk) {
    auto found_step = false;
    auto best_score = std::numeric_limits<std::uint32_t>::max();
    auto best_chunk = ChunkCoord3{};
    auto best_portal = Coord3{};
 
    const auto consider = [&](ChunkCoord3 next_chunk) {
      auto portal = Coord3{};
      auto scan_tiles = std::size_t{0};
      if (!memoized_chunk_portal<World, Class>(world, current_chunk, next_chunk,
                                               current, request.goal, portal,
                                               &scan_tiles)) {
        result.scan_tiles += scan_tiles;
        return;
      }
      result.scan_tiles += scan_tiles;
      const auto score = saturating_add(manhattan(current, portal),
                                        manhattan(portal, request.goal));
      if (!found_step || score < best_score) {
        found_step = true;
        best_score = score;
        best_chunk = next_chunk;
        best_portal = portal;
      }
    };
 
    if (current_chunk.x != goal_chunk.x) {
      auto next = current_chunk;
      if (current_chunk.x < goal_chunk.x) {
        ++next.x;
      } else {
        --next.x;
      }
      consider(next);
    }
    if (current_chunk.y != goal_chunk.y) {
      auto next = current_chunk;
      if (current_chunk.y < goal_chunk.y) {
        ++next.y;
      } else {
        --next.y;
      }
      consider(next);
    }
    if (current_chunk.z != goal_chunk.z) {
      auto next = current_chunk;
      if (current_chunk.z < goal_chunk.z) {
        ++next.z;
      } else {
        --next.z;
      }
      consider(next);
    }
 
    if (!found_step) {
      result.found = false;
      return result;
    }
    result.score =
        saturating_add(result.score, manhattan(current, best_portal));
    waypoints.push_back(best_portal);
    current = best_portal;
    current_chunk = best_chunk;
  }
 
  result.score = saturating_add(result.score, manhattan(current, request.goal));
  return result;
}
 
// Runs the chunk-portal candidate scan (six axis orders plus the greedy
// walk) and leaves the best-scoring waypoint sequence in
// `product.best_waypoints_`, with candidate/scan statistics accumulated on
// the product. Returns false when no goal-monotone candidate exists — the
// heuristic-tier limitation documented on the public builder below.
template <typename World, typename Class>
[[nodiscard]] auto select_chunk_portal_waypoints(
    const World& world, PathRequest request,
    WeightedPortalRouteProduct& product) -> bool {
  constexpr auto orders = std::array{
      std::array{Axis::X, Axis::Y, Axis::Z},
      std::array{Axis::X, Axis::Z, Axis::Y},
      std::array{Axis::Y, Axis::X, Axis::Z},
      std::array{Axis::Y, Axis::Z, Axis::X},
      std::array{Axis::Z, Axis::X, Axis::Y},
      std::array{Axis::Z, Axis::Y, Axis::X},
  };
 
  // Opens the memo for this selection and closes it however the
  // selection exits. A nested selection — reachable through a
  // user-supplied passability predicate — bypasses the memo rather than
  // sharing its generation, because the key omits the goal.
  const detail::PortalMemoScope memo_scope{detail::active_portal_memo()};
 
  auto found_route = false;
  auto best_score = std::numeric_limits<std::uint32_t>::max();
  product.best_waypoints_.clear();
  for (const auto& order : orders) {
    const auto candidate = build_chunk_portal_candidate<World, Class>(
        world, request, order, product.candidate_waypoints_);
    ++product.route_candidates_;
    product.portal_scan_tiles_ += candidate.scan_tiles;
    if (!candidate.found) {
      continue;
    }
    if (!found_route || candidate.score < best_score) {
      found_route = true;
      best_score = candidate.score;
      product.best_waypoints_.assign(product.candidate_waypoints_.begin(),
                                     product.candidate_waypoints_.end());
    }
  }
  {
    const auto candidate = build_greedy_chunk_portal_candidate<World, Class>(
        world, request, product.candidate_waypoints_);
    ++product.route_candidates_;
    product.portal_scan_tiles_ += candidate.scan_tiles;
    if (candidate.found && (!found_route || candidate.score < best_score)) {
      found_route = true;
      best_score = candidate.score;
      product.best_waypoints_.assign(product.candidate_waypoints_.begin(),
                                     product.candidate_waypoints_.end());
    }
  }
  return found_route;
}
 
}  // namespace detail
 
// HEURISTIC TIER: candidates walk only goal-monotone chunk staircases (each
// step moves one chunk closer on some axis) and only the single
// best-scoring candidate is stitched. `NoCandidate` means this tier found no
// route candidate; it is not a reachability conclusion. Topologies that
// require a chunk detour away from the goal (or whose best seam tile is sealed
// off) can return `NoCandidate` here while weighted_astar_path finds a route.
// Callers needing an authoritative answer must fall back to exact search.
template <typename World, typename Class>
[[nodiscard]] auto build_weighted_chunk_portal_route_product(
    const World& world, PathRequest request, PathScratch& scratch,
    WeightedPortalRouteProduct& product) -> PathResult {
  using Shape = typename World::shape_type;
  // Builds a portal route over the dense chunk-portal topology graph and tracks
  // content-version dependencies. The portal topology is dense-only; direct
  // weighted A* runs natively on sparse worlds.
  static_assert(
      std::is_same_v<typename World::residency_type, AlwaysResident>,
      "build_weighted_chunk_portal_route_product requires an "
      "AlwaysResidentWorld; use weighted_astar_path for sparse worlds.");
 
  product.clear();
  product.request_ = request;
 
  if (const auto failure =
          detail::weighted_endpoint_failure<World, Class>(world, request)) {
    product.status_ = *failure;
    detail::capture_failure_dependencies<Shape>(world, request, product.status_,
                                                product.dependencies_);
    return PathResult{product.status_, 0, 0, 0, product.path_};
  }
 
  const auto found_route = detail::select_chunk_portal_waypoints<World, Class>(
      world, request, product);
  if (!found_route) {
    product.status_ = PathStatus::NoCandidate;
    // Failure results depend on world content the portal scans sampled;
    // depend on every chunk so any edit invalidates a replayed failure.
    product.dependencies_.capture_all(world);
    return PathResult{product.status_, 0, 0, 0, product.path_};
  }
  product.waypoints_.assign(product.best_waypoints_.begin(),
                            product.best_waypoints_.end());
 
  auto from = request.start;
  auto total_cost = std::uint64_t{0};
  auto total_expanded = std::size_t{0};
  auto total_reached = std::size_t{0};
  auto append_segment = [&](PathRequest segment_request) {
    const auto result =
        weighted_astar_path<World, Class>(world, segment_request, scratch);
    total_expanded += result.expanded_nodes;
    total_reached += result.reached_nodes;
    if (result.status != PathStatus::Found) {
      product.path_.clear();
      product.status_ = PathStatus::NoCandidate;
      product.expanded_nodes_ = total_expanded;
      product.reached_nodes_ = total_reached;
      // Same failure-dependency contract as build_weighted_route_product;
      // the failing segment's endpoints are the offending tiles.
      detail::capture_failure_dependencies<Shape>(
          world, request, product.status_, product.dependencies_);
      return false;
    }
    total_cost += result.cost;
    if (total_cost >= std::numeric_limits<std::uint32_t>::max()) {
      product.path_.clear();
      product.status_ = PathStatus::CostOverflow;
      product.expanded_nodes_ = total_expanded;
      product.reached_nodes_ = total_reached;
      detail::capture_failure_dependencies<Shape>(
          world, request, product.status_, product.dependencies_);
      return false;
    }
    product.segment_.assign(result.path.begin(), result.path.end());
    for (std::size_t i = product.path_.empty() ? 0u : 1u;
         i < product.segment_.size(); ++i) {
      product.path_.push_back(product.segment_[i]);
    }
    return true;
  };
 
  for (const auto waypoint : product.waypoints_) {
    if (!append_segment(PathRequest{from, waypoint})) {
      return PathResult{product.status_, 0, total_expanded, total_reached,
                        product.path_};
    }
    from = waypoint;
  }
  if (!append_segment(PathRequest{from, request.goal})) {
    return PathResult{product.status_, 0, total_expanded, total_reached,
                      product.path_};
  }
 
  product.status_ = PathStatus::Found;
  product.cost_ = static_cast<std::uint32_t>(total_cost);
  product.expanded_nodes_ = total_expanded;
  product.reached_nodes_ = total_reached;
  for (const auto coord : product.path_) {
    const auto key = tile_key<Shape>(coord);
    product.dependencies_.add_chunk(world, chunk_key<Shape>(key));
  }
  return PathResult{product.status_, product.cost_, product.expanded_nodes_,
                    product.reached_nodes_, product.path_};
}
 
// Same heuristic tier and NoCandidate semantics as the uncached builder above:
// chunk-portal candidates select the waypoints, and stitching runs through
// the class-bound segment cache so repeated corridors serve without fresh
// searches. Unlike the uncached builder, the product records segment-level
// dependencies only (inside the cache); it is a serving product, not a
// replay product, and its returned path borrows the product exactly like
// the other builders.
template <typename World, typename Class>
[[nodiscard]] auto build_weighted_chunk_portal_route_product_cached(
    const World& world, PathRequest request, PathScratch& scratch,
    WeightedPortalSegmentCache& cache, WeightedPortalRouteProduct& product)
    -> PathResult {
  static_assert(
      std::is_same_v<typename World::residency_type, AlwaysResident>,
      "build_weighted_chunk_portal_route_product_cached requires an "
      "AlwaysResidentWorld; use weighted_astar_path for sparse worlds.");
 
  product.clear();
  product.request_ = request;
 
  if (const auto failure =
          detail::weighted_endpoint_failure<World, Class>(world, request)) {
    product.status_ = *failure;
    return PathResult{product.status_, 0, 0, 0, product.path_};
  }
 
  if (!detail::select_chunk_portal_waypoints<World, Class>(world, request,
                                                           product)) {
    product.status_ = PathStatus::NoCandidate;
    return PathResult{product.status_, 0, 0, 0, product.path_};
  }
  product.waypoints_.assign(product.best_waypoints_.begin(),
                            product.best_waypoints_.end());
 
  auto class_cache = cache.template for_class<Class>();
  auto from = request.start;
  // Segment costs accumulate in 64 bits: each segment cost is
  // representable, but a stitched total at or above the uint32 infinity
  // sentinel must report CostOverflow exactly as the exact search would —
  // never a Found route carrying an unrepresentable cost.
  auto total_cost = std::uint64_t{0};
  auto total_expanded = std::size_t{0};
  auto total_reached = std::size_t{0};
  auto append_segment = [&](PathRequest segment_request) {
    if (const auto hit =
            class_cache.lookup_append(world, segment_request, product.path_);
        hit.found) {
      total_cost += hit.cost;
      return true;
    }
    const auto result =
        weighted_astar_path<World, Class>(world, segment_request, scratch);
    class_cache.store(world, segment_request, result);
    total_expanded += result.expanded_nodes;
    total_reached += result.reached_nodes;
    if (result.status != PathStatus::Found) {
      product.path_.clear();
      product.status_ = PathStatus::NoCandidate;
      product.expanded_nodes_ = total_expanded;
      product.reached_nodes_ = total_reached;
      return false;
    }
    total_cost += result.cost;
    for (std::size_t i = product.path_.empty() ? 0u : 1u;
         i < result.path.size(); ++i) {
      product.path_.push_back(result.path[i]);
    }
    return true;
  };
 
  for (const auto waypoint : product.waypoints_) {
    if (!append_segment(PathRequest{from, waypoint})) {
      return PathResult{product.status_, 0, total_expanded, total_reached,
                        product.path_};
    }
    from = waypoint;
  }
  if (!append_segment(PathRequest{from, request.goal})) {
    return PathResult{product.status_, 0, total_expanded, total_reached,
                      product.path_};
  }
 
  if (total_cost >= std::numeric_limits<std::uint32_t>::max()) {
    product.path_.clear();
    product.status_ = PathStatus::CostOverflow;
    product.expanded_nodes_ = total_expanded;
    product.reached_nodes_ = total_reached;
    return PathResult{product.status_, 0, total_expanded, total_reached,
                      product.path_};
  }
 
  product.status_ = PathStatus::Found;
  product.cost_ = static_cast<std::uint32_t>(total_cost);
  product.expanded_nodes_ = total_expanded;
  product.reached_nodes_ = total_reached;
  return PathResult{product.status_, product.cost_, product.expanded_nodes_,
                    product.reached_nodes_, product.path_};
}
 
}  // namespace tess