mirror of
https://github.com/brazilofmux/tinymux
synced 2026-08-13 00:23:11 -04:00
e7eb6ec76d
Mechanical hygiene under the opt-in M_() design: replace T("#-1…") and
T("#-2…") with S_() so softcode ABI tokens are obvious in source and
cannot enter a player catalog. ~400 call sites across engine, exp3,
mail, and driver. Assembled/library-spliced diagnostics (plan §4.2)
are unchanged where they are not a single literal.
1121 lines
30 KiB
C++
1121 lines
30 KiB
C++
/*! \file routing.cpp
|
|
* \brief Routing: per-zone next-hop tables with cross-zone meta-table.
|
|
*
|
|
* Implements BFS-based shortest-path routing over rooms marked NAVIGABLE,
|
|
* partitioned by zone. Each zone has an independent routing table with
|
|
* its own generation counter. Cross-zone routing uses a gateway-edge
|
|
* meta-table with Dijkstra over the (small) zone graph.
|
|
*
|
|
* Compression techniques per zone:
|
|
* 1. Diagonal elimination -- source == dest needs no entry.
|
|
* 2. Row redundancy -- if every reachable destination funnels
|
|
* through the same exit, store a single "always(exit)" sentinel.
|
|
*
|
|
* See docs/design-routing.md for the full design.
|
|
*/
|
|
|
|
#include "copyright.h"
|
|
#include "autoconf.h"
|
|
#include "config.h"
|
|
#include "externs.h"
|
|
|
|
#include "attrs.h"
|
|
#include "command.h"
|
|
#include "flags.h"
|
|
#include "routing.h"
|
|
#include "sqlite_backend.h"
|
|
|
|
#include <vector>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
#include <queue>
|
|
#include <climits>
|
|
#include <cstring>
|
|
#include <algorithm>
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Data structures.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
struct ExitEdge
|
|
{
|
|
dbref exit_dbref;
|
|
dbref dest_room;
|
|
};
|
|
|
|
// Per-room routing row within a zone.
|
|
//
|
|
struct RouteRow
|
|
{
|
|
dbref always_exit; // NOTHING if not compressed.
|
|
std::unordered_map<dbref, dbref> next_hop; // dest_room -> exit dbref.
|
|
};
|
|
|
|
// Per-zone routing table.
|
|
//
|
|
struct ZoneTable
|
|
{
|
|
int generation; // Bumped on invalidation.
|
|
int table_generation; // Generation at last rebuild.
|
|
bool valid;
|
|
|
|
std::unordered_map<dbref, int> node_index; // room -> dense index.
|
|
std::vector<dbref> index_to_room; // dense index -> room.
|
|
std::vector<RouteRow> table; // indexed by dense index.
|
|
std::vector<std::vector<ExitEdge>> adj; // adjacency lists.
|
|
|
|
ZoneTable() : generation(0), table_generation(-1), valid(false) {}
|
|
};
|
|
|
|
// Gateway edge: a cross-zone exit connecting two zones.
|
|
//
|
|
struct GatewayEdge
|
|
{
|
|
dbref source_zone;
|
|
dbref dest_zone;
|
|
dbref gate_room; // Room in source_zone containing the exit.
|
|
dbref gate_exit; // The exit itself.
|
|
dbref target_room; // Room in dest_zone the exit leads to.
|
|
};
|
|
|
|
// Meta-table for inter-zone routing.
|
|
//
|
|
struct MetaTable
|
|
{
|
|
int generation;
|
|
int table_generation;
|
|
bool valid;
|
|
|
|
std::vector<GatewayEdge> edges;
|
|
|
|
MetaTable() : generation(0), table_generation(-1), valid(false) {}
|
|
};
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Global state.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
// All navigable rooms, keyed by room dbref -> zone dbref.
|
|
//
|
|
static std::unordered_map<dbref, dbref> g_room_to_zone;
|
|
|
|
// Per-zone tables, keyed by zone dbref (NOTHING for orphan rooms).
|
|
//
|
|
static std::unordered_map<dbref, ZoneTable> g_zone_tables;
|
|
|
|
// Meta-table for cross-zone routing.
|
|
//
|
|
static MetaTable g_meta;
|
|
|
|
// Global node index across all zones (for navigable-check in route_query).
|
|
//
|
|
static std::unordered_set<dbref> g_all_navigable;
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Forward declarations.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void route_scan_navigable(void);
|
|
static void route_build_zone(dbref zone_id);
|
|
static void route_build_meta(void);
|
|
static void route_ensure_zone_current(dbref zone_id);
|
|
static void route_ensure_meta_current(void);
|
|
static void route_persist_to_sqlite(void);
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Initialization / shutdown.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
void route_init(void)
|
|
{
|
|
g_room_to_zone.clear();
|
|
g_zone_tables.clear();
|
|
g_all_navigable.clear();
|
|
g_meta = MetaTable();
|
|
}
|
|
|
|
void route_shutdown(void)
|
|
{
|
|
g_room_to_zone.clear();
|
|
g_zone_tables.clear();
|
|
g_all_navigable.clear();
|
|
g_meta = MetaTable();
|
|
}
|
|
|
|
void route_invalidate(void)
|
|
{
|
|
for (auto &kv : g_zone_tables)
|
|
{
|
|
kv.second.generation++;
|
|
}
|
|
g_meta.generation++;
|
|
|
|
// Also invalidate the navigable scan so new rooms are picked up.
|
|
//
|
|
g_all_navigable.clear();
|
|
g_room_to_zone.clear();
|
|
}
|
|
|
|
void route_invalidate_zone(dbref zone_id)
|
|
{
|
|
auto it = g_zone_tables.find(zone_id);
|
|
if (it != g_zone_tables.end())
|
|
{
|
|
it->second.generation++;
|
|
}
|
|
|
|
// A zone-local change might also affect gateway edges (e.g., a new
|
|
// room at the border). Invalidate the scan and meta conservatively.
|
|
//
|
|
g_all_navigable.clear();
|
|
g_room_to_zone.clear();
|
|
g_meta.generation++;
|
|
}
|
|
|
|
void route_invalidate_meta(void)
|
|
{
|
|
g_meta.generation++;
|
|
g_all_navigable.clear();
|
|
g_room_to_zone.clear();
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Scan all navigable rooms and partition by zone.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void route_scan_navigable(void)
|
|
{
|
|
if (!g_all_navigable.empty())
|
|
{
|
|
return; // Already scanned since last invalidation.
|
|
}
|
|
|
|
g_room_to_zone.clear();
|
|
|
|
// Discover all navigable rooms and their zones.
|
|
//
|
|
dbref thing;
|
|
DO_WHOLE_DB(thing)
|
|
{
|
|
if ( isRoom(thing)
|
|
&& !isGarbage(thing)
|
|
&& Navigable(thing))
|
|
{
|
|
dbref z = Zone(thing);
|
|
g_room_to_zone[thing] = z;
|
|
g_all_navigable.insert(thing);
|
|
|
|
// Ensure a ZoneTable entry exists (preserve generation if
|
|
// already present).
|
|
//
|
|
if (g_zone_tables.find(z) == g_zone_tables.end())
|
|
{
|
|
g_zone_tables[z] = ZoneTable();
|
|
}
|
|
}
|
|
}
|
|
|
|
// Prune zone tables for zones that no longer have navigable rooms.
|
|
//
|
|
std::unordered_set<dbref> active_zones;
|
|
for (const auto &kv : g_room_to_zone)
|
|
{
|
|
active_zones.insert(kv.second);
|
|
}
|
|
for (auto it = g_zone_tables.begin(); it != g_zone_tables.end(); )
|
|
{
|
|
if (active_zones.find(it->first) == active_zones.end())
|
|
{
|
|
it = g_zone_tables.erase(it);
|
|
}
|
|
else
|
|
{
|
|
++it;
|
|
}
|
|
}
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Collect edges for a single room (walks parent chain).
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void collect_room_edges(
|
|
dbref room,
|
|
const std::unordered_map<dbref, int> &node_idx,
|
|
std::vector<ExitEdge> &edges)
|
|
{
|
|
edges.clear();
|
|
|
|
std::unordered_set<dbref> seen_exits;
|
|
int level;
|
|
dbref parent;
|
|
ITER_PARENTS(room, parent, level)
|
|
{
|
|
dbref exit_obj;
|
|
DOLIST(exit_obj, Exits(parent))
|
|
{
|
|
if ( !isExit(exit_obj)
|
|
|| !seen_exits.insert(exit_obj).second)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
const UTF8 *vdest = atr_get_raw(exit_obj, A_EXITVARDEST);
|
|
if (vdest && *vdest)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
dbref dest = Location(exit_obj);
|
|
if ( !Good_obj(dest)
|
|
|| !isRoom(dest))
|
|
{
|
|
continue;
|
|
}
|
|
|
|
// Destination must be navigable (in any zone).
|
|
//
|
|
if (g_all_navigable.find(dest) == g_all_navigable.end())
|
|
{
|
|
continue;
|
|
}
|
|
|
|
// For zone-local edges, destination must be in the same zone
|
|
// OR we accept it as a gateway edge if it's in a different
|
|
// zone. The node_idx check restricts to same-zone nodes.
|
|
// Cross-zone edges are still recorded (dest is navigable)
|
|
// but won't match node_idx -- that's fine, they are handled
|
|
// by the meta-table.
|
|
//
|
|
auto it = node_idx.find(dest);
|
|
if (it == node_idx.end())
|
|
{
|
|
continue;
|
|
}
|
|
|
|
ExitEdge edge;
|
|
edge.exit_dbref = exit_obj;
|
|
edge.dest_room = dest;
|
|
edges.push_back(edge);
|
|
}
|
|
}
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// BFS from a single source within a zone.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void bfs_from_source(
|
|
int source_idx,
|
|
const std::vector<std::vector<ExitEdge>> &adj,
|
|
const std::unordered_map<dbref, int> &node_idx,
|
|
const std::vector<dbref> &idx_to_room,
|
|
RouteRow &row)
|
|
{
|
|
int n = static_cast<int>(idx_to_room.size());
|
|
row.always_exit = NOTHING;
|
|
row.next_hop.clear();
|
|
|
|
std::vector<bool> visited(n, false);
|
|
std::vector<dbref> first_exit(n, NOTHING);
|
|
std::queue<int> queue;
|
|
|
|
visited[source_idx] = true;
|
|
|
|
for (const auto &edge : adj[source_idx])
|
|
{
|
|
auto it = node_idx.find(edge.dest_room);
|
|
if (it == node_idx.end())
|
|
{
|
|
continue;
|
|
}
|
|
int dest_idx = it->second;
|
|
if (!visited[dest_idx])
|
|
{
|
|
visited[dest_idx] = true;
|
|
first_exit[dest_idx] = edge.exit_dbref;
|
|
queue.push(dest_idx);
|
|
}
|
|
}
|
|
|
|
while (!queue.empty())
|
|
{
|
|
int cur = queue.front();
|
|
queue.pop();
|
|
|
|
for (const auto &edge : adj[cur])
|
|
{
|
|
auto it = node_idx.find(edge.dest_room);
|
|
if (it == node_idx.end())
|
|
{
|
|
continue;
|
|
}
|
|
int next_idx = it->second;
|
|
if (!visited[next_idx])
|
|
{
|
|
visited[next_idx] = true;
|
|
first_exit[next_idx] = first_exit[cur];
|
|
queue.push(next_idx);
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
if (i == source_idx)
|
|
{
|
|
continue;
|
|
}
|
|
if (first_exit[i] != NOTHING)
|
|
{
|
|
row.next_hop[idx_to_room[i]] = first_exit[i];
|
|
}
|
|
}
|
|
|
|
// Row redundancy compression: only safe when all non-diagonal
|
|
// destinations are reachable.
|
|
//
|
|
if ( !row.next_hop.empty()
|
|
&& row.next_hop.size() == static_cast<size_t>(n - 1))
|
|
{
|
|
dbref candidate = row.next_hop.begin()->second;
|
|
bool all_same = true;
|
|
for (const auto &kv : row.next_hop)
|
|
{
|
|
if (kv.second != candidate)
|
|
{
|
|
all_same = false;
|
|
break;
|
|
}
|
|
}
|
|
if (all_same)
|
|
{
|
|
row.always_exit = candidate;
|
|
row.next_hop.clear();
|
|
}
|
|
}
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Build one zone's routing table.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void route_build_zone(dbref zone_id)
|
|
{
|
|
route_scan_navigable();
|
|
|
|
auto zt_it = g_zone_tables.find(zone_id);
|
|
if (zt_it == g_zone_tables.end())
|
|
{
|
|
return;
|
|
}
|
|
ZoneTable &zt = zt_it->second;
|
|
|
|
zt.node_index.clear();
|
|
zt.index_to_room.clear();
|
|
|
|
// Collect rooms in this zone.
|
|
//
|
|
for (const auto &kv : g_room_to_zone)
|
|
{
|
|
if (kv.second == zone_id)
|
|
{
|
|
int idx = static_cast<int>(zt.index_to_room.size());
|
|
zt.node_index[kv.first] = idx;
|
|
zt.index_to_room.push_back(kv.first);
|
|
}
|
|
}
|
|
|
|
int n = static_cast<int>(zt.index_to_room.size());
|
|
zt.adj.resize(n);
|
|
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
collect_room_edges(zt.index_to_room[i], zt.node_index, zt.adj[i]);
|
|
}
|
|
|
|
zt.table.resize(n);
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
bfs_from_source(i, zt.adj, zt.node_index, zt.index_to_room,
|
|
zt.table[i]);
|
|
}
|
|
|
|
zt.table_generation = zt.generation;
|
|
zt.valid = true;
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Build the inter-zone meta-table: collect gateway edges.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void route_build_meta(void)
|
|
{
|
|
route_scan_navigable();
|
|
|
|
g_meta.edges.clear();
|
|
|
|
// Scan all navigable rooms. For each exit that leads to a room in
|
|
// a different zone, emit a gateway edge.
|
|
//
|
|
for (const auto &kv : g_room_to_zone)
|
|
{
|
|
dbref room = kv.first;
|
|
dbref src_zone = kv.second;
|
|
|
|
std::unordered_set<dbref> seen_exits;
|
|
int level;
|
|
dbref parent;
|
|
ITER_PARENTS(room, parent, level)
|
|
{
|
|
dbref exit_obj;
|
|
DOLIST(exit_obj, Exits(parent))
|
|
{
|
|
if ( !isExit(exit_obj)
|
|
|| !seen_exits.insert(exit_obj).second)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
const UTF8 *vdest = atr_get_raw(exit_obj, A_EXITVARDEST);
|
|
if (vdest && *vdest)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
dbref dest = Location(exit_obj);
|
|
if ( !Good_obj(dest)
|
|
|| !isRoom(dest))
|
|
{
|
|
continue;
|
|
}
|
|
|
|
if (g_all_navigable.find(dest) == g_all_navigable.end())
|
|
{
|
|
continue;
|
|
}
|
|
|
|
dbref dst_zone = g_room_to_zone[dest];
|
|
if (dst_zone == src_zone)
|
|
{
|
|
continue; // Intra-zone, not a gateway.
|
|
}
|
|
|
|
GatewayEdge ge;
|
|
ge.source_zone = src_zone;
|
|
ge.dest_zone = dst_zone;
|
|
ge.gate_room = room;
|
|
ge.gate_exit = exit_obj;
|
|
ge.target_room = dest;
|
|
g_meta.edges.push_back(ge);
|
|
}
|
|
}
|
|
}
|
|
|
|
g_meta.table_generation = g_meta.generation;
|
|
g_meta.valid = true;
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Ensure tables are current.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void route_ensure_zone_current(dbref zone_id)
|
|
{
|
|
route_scan_navigable();
|
|
|
|
auto it = g_zone_tables.find(zone_id);
|
|
if (it == g_zone_tables.end())
|
|
{
|
|
return;
|
|
}
|
|
if (it->second.valid && it->second.table_generation == it->second.generation)
|
|
{
|
|
return;
|
|
}
|
|
route_build_zone(zone_id);
|
|
route_persist_to_sqlite();
|
|
}
|
|
|
|
static void route_ensure_meta_current(void)
|
|
{
|
|
route_scan_navigable();
|
|
|
|
if (g_meta.valid && g_meta.table_generation == g_meta.generation)
|
|
{
|
|
return;
|
|
}
|
|
route_build_meta();
|
|
route_persist_to_sqlite();
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Intra-zone next-hop lookup.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static dbref zone_next_hop(const ZoneTable &zt, dbref source, dbref destination)
|
|
{
|
|
auto src_it = zt.node_index.find(source);
|
|
if (src_it == zt.node_index.end())
|
|
{
|
|
return NOTHING;
|
|
}
|
|
|
|
const RouteRow &row = zt.table[src_it->second];
|
|
if (row.always_exit != NOTHING)
|
|
{
|
|
return row.always_exit;
|
|
}
|
|
|
|
auto hop_it = row.next_hop.find(destination);
|
|
if (hop_it == row.next_hop.end())
|
|
{
|
|
return NOTHING;
|
|
}
|
|
return hop_it->second;
|
|
}
|
|
|
|
// Append the exact intra-zone path from source to destination. Returns
|
|
// false if the destination is unreachable from source.
|
|
//
|
|
static bool append_zone_path(const ZoneTable &zt, dbref source,
|
|
dbref destination, std::vector<dbref> &path)
|
|
{
|
|
if (source == destination)
|
|
{
|
|
return true;
|
|
}
|
|
|
|
auto src_it = zt.node_index.find(source);
|
|
auto dst_it = zt.node_index.find(destination);
|
|
if (src_it == zt.node_index.end() || dst_it == zt.node_index.end())
|
|
{
|
|
return false;
|
|
}
|
|
|
|
dbref current = source;
|
|
int hops = 0;
|
|
int max_hops = static_cast<int>(zt.index_to_room.size());
|
|
|
|
while (current != destination && hops < max_hops)
|
|
{
|
|
dbref next_exit = zone_next_hop(zt, current, destination);
|
|
if (next_exit == NOTHING)
|
|
{
|
|
return false;
|
|
}
|
|
|
|
dbref next_room = Location(next_exit);
|
|
if (!Good_obj(next_room) || next_room == current)
|
|
{
|
|
return false;
|
|
}
|
|
|
|
path.push_back(next_exit);
|
|
current = next_room;
|
|
hops++;
|
|
}
|
|
|
|
return current == destination;
|
|
}
|
|
|
|
// Intra-zone hop count between two rooms (returns -1 if unreachable).
|
|
//
|
|
static int zone_hop_count(const ZoneTable &zt, dbref source, dbref destination)
|
|
{
|
|
if (source == destination)
|
|
{
|
|
return 0;
|
|
}
|
|
|
|
auto src_it = zt.node_index.find(source);
|
|
auto dst_it = zt.node_index.find(destination);
|
|
if (src_it == zt.node_index.end() || dst_it == zt.node_index.end())
|
|
{
|
|
return -1;
|
|
}
|
|
|
|
// Walk next-hop chain counting steps.
|
|
//
|
|
dbref current = source;
|
|
int hops = 0;
|
|
int max_hops = static_cast<int>(zt.index_to_room.size());
|
|
|
|
while (current != destination && hops < max_hops)
|
|
{
|
|
dbref next_exit = zone_next_hop(zt, current, destination);
|
|
if (next_exit == NOTHING)
|
|
{
|
|
return -1;
|
|
}
|
|
dbref next_room = Location(next_exit);
|
|
if (!Good_obj(next_room) || next_room == current)
|
|
{
|
|
return -1;
|
|
}
|
|
current = next_room;
|
|
hops++;
|
|
}
|
|
return (current == destination) ? hops : -1;
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Cross-zone Dijkstra: find the sequence of gateway edges from
|
|
// source_zone to dest_zone.
|
|
//
|
|
// Returns the gateway edges in order. Empty result = no route.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void meta_dijkstra(
|
|
dbref source_room,
|
|
dbref dest_room,
|
|
std::vector<const GatewayEdge *> &result)
|
|
{
|
|
result.clear();
|
|
|
|
dbref source_zone = g_room_to_zone[source_room];
|
|
dbref dest_zone = g_room_to_zone[dest_room];
|
|
if (source_zone == dest_zone)
|
|
{
|
|
return;
|
|
}
|
|
|
|
// Build adjacency: zone -> list of edge indices.
|
|
//
|
|
std::unordered_map<dbref, std::vector<int>> adj;
|
|
for (int i = 0; i < static_cast<int>(g_meta.edges.size()); i++)
|
|
{
|
|
adj[g_meta.edges[i].source_zone].push_back(i);
|
|
}
|
|
|
|
// Dijkstra over actual room states. The state is "currently standing in
|
|
// room R", where R is the query source or the target room of a gateway
|
|
// edge already crossed. This avoids choosing an unreachable gateway just
|
|
// because its zone edge count looks shorter.
|
|
//
|
|
std::unordered_map<dbref, int> dist;
|
|
std::unordered_map<dbref, dbref> prev_room;
|
|
std::unordered_map<dbref, int> prev_edge; // room -> gateway edge index.
|
|
|
|
// Priority queue: (distance, room).
|
|
//
|
|
typedef std::pair<int, dbref> PQEntry;
|
|
std::priority_queue<PQEntry, std::vector<PQEntry>, std::greater<PQEntry>> pq;
|
|
|
|
int best_goal = INT_MAX;
|
|
dbref best_goal_room = NOTHING;
|
|
|
|
dist[source_room] = 0;
|
|
pq.push({0, source_room});
|
|
|
|
while (!pq.empty())
|
|
{
|
|
auto [d, room] = pq.top();
|
|
pq.pop();
|
|
|
|
auto dist_it = dist.find(room);
|
|
if (dist_it == dist.end() || d > dist_it->second)
|
|
{
|
|
continue; // Stale entry.
|
|
}
|
|
|
|
if (d >= best_goal)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
dbref zone = g_room_to_zone[room];
|
|
route_ensure_zone_current(zone);
|
|
auto zt_it = g_zone_tables.find(zone);
|
|
if (zt_it == g_zone_tables.end())
|
|
{
|
|
continue;
|
|
}
|
|
|
|
// Any state already inside the destination zone can finish with an
|
|
// exact local-table lookup.
|
|
//
|
|
if (zone == dest_zone)
|
|
{
|
|
int final_cost = zone_hop_count(zt_it->second, room, dest_room);
|
|
if ( final_cost >= 0
|
|
&& d + final_cost < best_goal)
|
|
{
|
|
best_goal = d + final_cost;
|
|
best_goal_room = room;
|
|
}
|
|
}
|
|
|
|
auto adj_it = adj.find(zone);
|
|
if (adj_it == adj.end())
|
|
{
|
|
continue;
|
|
}
|
|
|
|
for (int ei : adj_it->second)
|
|
{
|
|
const GatewayEdge &ge = g_meta.edges[ei];
|
|
int approach_cost = zone_hop_count(zt_it->second, room, ge.gate_room);
|
|
if (approach_cost < 0)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
dbref next_room = ge.target_room;
|
|
int new_dist = d + approach_cost + 1;
|
|
|
|
auto next_it = dist.find(next_room);
|
|
if (next_it == dist.end() || new_dist < next_it->second)
|
|
{
|
|
dist[next_room] = new_dist;
|
|
prev_room[next_room] = room;
|
|
prev_edge[next_room] = ei;
|
|
pq.push({new_dist, next_room});
|
|
}
|
|
}
|
|
}
|
|
|
|
// Reconstruct path.
|
|
//
|
|
if (best_goal_room == NOTHING)
|
|
{
|
|
return;
|
|
}
|
|
|
|
std::vector<int> edge_path;
|
|
dbref room = best_goal_room;
|
|
while (room != source_room)
|
|
{
|
|
auto pe_it = prev_edge.find(room);
|
|
if (pe_it == prev_edge.end())
|
|
{
|
|
result.clear();
|
|
return;
|
|
}
|
|
edge_path.push_back(pe_it->second);
|
|
room = prev_room[room];
|
|
}
|
|
|
|
// Reverse to get source-to-dest order.
|
|
//
|
|
std::reverse(edge_path.begin(), edge_path.end());
|
|
for (int ei : edge_path)
|
|
{
|
|
result.push_back(&g_meta.edges[ei]);
|
|
}
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Full path reconstruction (handles cross-zone).
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void route_get_path(dbref source, dbref destination,
|
|
std::vector<dbref> &path)
|
|
{
|
|
path.clear();
|
|
|
|
dbref src_zone = g_room_to_zone[source];
|
|
dbref dst_zone = g_room_to_zone[destination];
|
|
|
|
if (src_zone == dst_zone)
|
|
{
|
|
// Same zone: walk next-hop chain.
|
|
//
|
|
route_ensure_zone_current(src_zone);
|
|
auto zt_it = g_zone_tables.find(src_zone);
|
|
if (zt_it == g_zone_tables.end())
|
|
{
|
|
return;
|
|
}
|
|
const ZoneTable &zt = zt_it->second;
|
|
if (!append_zone_path(zt, source, destination, path))
|
|
{
|
|
path.clear();
|
|
}
|
|
return;
|
|
}
|
|
|
|
// Cross-zone: use meta-table to find gateway chain.
|
|
//
|
|
route_ensure_meta_current();
|
|
|
|
std::vector<const GatewayEdge *> gw_path;
|
|
meta_dijkstra(source, destination, gw_path);
|
|
if (gw_path.empty())
|
|
{
|
|
return;
|
|
}
|
|
|
|
dbref current = source;
|
|
|
|
for (size_t gi = 0; gi < gw_path.size(); gi++)
|
|
{
|
|
const GatewayEdge *ge = gw_path[gi];
|
|
dbref gate_room = ge->gate_room;
|
|
|
|
// Route within current zone from current to gate_room.
|
|
//
|
|
dbref cur_zone = g_room_to_zone[current];
|
|
route_ensure_zone_current(cur_zone);
|
|
auto zt_it = g_zone_tables.find(cur_zone);
|
|
if (zt_it == g_zone_tables.end())
|
|
{
|
|
path.clear();
|
|
return;
|
|
}
|
|
const ZoneTable &zt = zt_it->second;
|
|
if (!append_zone_path(zt, current, gate_room, path))
|
|
{
|
|
path.clear();
|
|
return;
|
|
}
|
|
|
|
// Cross the gateway exit.
|
|
//
|
|
path.push_back(ge->gate_exit);
|
|
current = ge->target_room;
|
|
}
|
|
|
|
// Final segment: route within destination zone to the destination.
|
|
//
|
|
if (current != destination)
|
|
{
|
|
route_ensure_zone_current(dst_zone);
|
|
auto zt_it = g_zone_tables.find(dst_zone);
|
|
if (zt_it == g_zone_tables.end())
|
|
{
|
|
path.clear();
|
|
return;
|
|
}
|
|
const ZoneTable &zt = zt_it->second;
|
|
if (!append_zone_path(zt, current, destination, path))
|
|
{
|
|
path.clear();
|
|
}
|
|
}
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// SQLite persistence (metadata only for now).
|
|
// ---------------------------------------------------------------------------
|
|
|
|
static void route_persist_to_sqlite(void)
|
|
{
|
|
if ( nullptr == g_pSQLiteBackend
|
|
|| !g_pSQLiteBackend->GetDB().IsOpen())
|
|
{
|
|
return;
|
|
}
|
|
|
|
CSQLiteDB &sqldb = g_pSQLiteBackend->GetDB();
|
|
|
|
sqldb.PutMeta("route_zone_count",
|
|
static_cast<int>(g_zone_tables.size()));
|
|
sqldb.PutMeta("route_node_count",
|
|
static_cast<int>(g_all_navigable.size()));
|
|
sqldb.PutMeta("route_gateway_count",
|
|
static_cast<int>(g_meta.edges.size()));
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Query interface.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
void route_query(dbref executor, dbref source, dbref destination,
|
|
int options, UTF8 *buff, UTF8 **bufc)
|
|
{
|
|
// Handle rebuild option (wizard-only).
|
|
//
|
|
if (options & ROUTE_OPT_REBUILD)
|
|
{
|
|
if (!Wizard(executor))
|
|
{
|
|
safe_str(S_("#-1 PERMISSION DENIED"), buff, bufc);
|
|
return;
|
|
}
|
|
route_invalidate();
|
|
}
|
|
|
|
// Validate source and destination.
|
|
//
|
|
if ( !Good_obj(source)
|
|
|| !isRoom(source)
|
|
|| !Good_obj(destination)
|
|
|| !isRoom(destination))
|
|
{
|
|
safe_str(S_("#-2"), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
// Same room?
|
|
//
|
|
if (source == destination)
|
|
{
|
|
if (options & ROUTE_OPT_DISTANCE)
|
|
{
|
|
safe_chr('0', buff, bufc);
|
|
}
|
|
else if (options & ROUTE_OPT_PATH)
|
|
{
|
|
// Empty path -- already there.
|
|
}
|
|
else
|
|
{
|
|
safe_str(S_("#-1"), buff, bufc);
|
|
}
|
|
return;
|
|
}
|
|
|
|
// Ensure navigable rooms are scanned.
|
|
//
|
|
route_scan_navigable();
|
|
|
|
// Check that both rooms are navigable.
|
|
//
|
|
if ( g_all_navigable.find(source) == g_all_navigable.end()
|
|
|| g_all_navigable.find(destination) == g_all_navigable.end())
|
|
{
|
|
safe_str(S_("#-1 NOT NAVIGABLE"), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
dbref src_zone = g_room_to_zone[source];
|
|
dbref dst_zone = g_room_to_zone[destination];
|
|
|
|
// Preserve the O(1) same-zone next-hop lookup for the common case.
|
|
// Phase 3a only needs full-path reconstruction for distance/path, or
|
|
// when the route itself spans zones.
|
|
//
|
|
if ( !(options & (ROUTE_OPT_PATH | ROUTE_OPT_DISTANCE))
|
|
&& src_zone == dst_zone)
|
|
{
|
|
route_ensure_zone_current(src_zone);
|
|
auto zt_it = g_zone_tables.find(src_zone);
|
|
if (zt_it == g_zone_tables.end())
|
|
{
|
|
safe_str(S_("#-1 NO ROUTE"), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
dbref next_exit = zone_next_hop(zt_it->second, source, destination);
|
|
if (next_exit == NOTHING)
|
|
{
|
|
safe_str(S_("#-1 NO ROUTE"), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
if ( (options & ROUTE_OPT_LOCKED)
|
|
&& !could_doit(executor, next_exit, A_LOCK))
|
|
{
|
|
safe_str(S_("#-1 EXIT IMPASSABLE"), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
safe_tprintf_str(buff, bufc, T("#%d"), next_exit);
|
|
return;
|
|
}
|
|
|
|
// Resolve the full path for distance/path output and for cross-zone
|
|
// routing, where the first hop may need intra-zone movement to a
|
|
// gateway room before crossing zones.
|
|
//
|
|
std::vector<dbref> path;
|
|
route_get_path(source, destination, path);
|
|
if (path.empty())
|
|
{
|
|
safe_str(S_("#-1 NO ROUTE"), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
// Locked mode validates only the next hop at query time.
|
|
//
|
|
if ( (options & ROUTE_OPT_LOCKED)
|
|
&& !could_doit(executor, path[0], A_LOCK))
|
|
{
|
|
safe_str(S_("#-1 EXIT IMPASSABLE"), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
if (options & ROUTE_OPT_PATH)
|
|
{
|
|
for (size_t i = 0; i < path.size(); i++)
|
|
{
|
|
if (i > 0)
|
|
{
|
|
safe_chr(' ', buff, bufc);
|
|
}
|
|
safe_tprintf_str(buff, bufc, T("#%d"), path[i]);
|
|
}
|
|
return;
|
|
}
|
|
|
|
if (options & ROUTE_OPT_DISTANCE)
|
|
{
|
|
safe_ltoa(static_cast<long>(path.size()), buff, bufc);
|
|
return;
|
|
}
|
|
|
|
// Default: return next-hop exit.
|
|
//
|
|
safe_tprintf_str(buff, bufc, T("#%d"), path[0]);
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// C-level next-hop lookup for @walk/@patrol.
|
|
// ---------------------------------------------------------------------------
|
|
|
|
dbref route_next_exit(dbref executor, dbref source, dbref destination,
|
|
int options)
|
|
{
|
|
if ( !Good_obj(source)
|
|
|| !isRoom(source)
|
|
|| !Good_obj(destination)
|
|
|| !isRoom(destination)
|
|
|| source == destination)
|
|
{
|
|
return NOTHING;
|
|
}
|
|
|
|
route_scan_navigable();
|
|
|
|
if ( g_all_navigable.find(source) == g_all_navigable.end()
|
|
|| g_all_navigable.find(destination) == g_all_navigable.end())
|
|
{
|
|
return NOTHING;
|
|
}
|
|
|
|
dbref src_zone = g_room_to_zone[source];
|
|
dbref dst_zone = g_room_to_zone[destination];
|
|
|
|
dbref next_exit = NOTHING;
|
|
|
|
if (src_zone == dst_zone)
|
|
{
|
|
route_ensure_zone_current(src_zone);
|
|
auto zt_it = g_zone_tables.find(src_zone);
|
|
if (zt_it != g_zone_tables.end())
|
|
{
|
|
next_exit = zone_next_hop(zt_it->second, source, destination);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
// Cross-zone: get the full path and return the first hop.
|
|
//
|
|
std::vector<dbref> path;
|
|
route_get_path(source, destination, path);
|
|
if (!path.empty())
|
|
{
|
|
next_exit = path[0];
|
|
}
|
|
}
|
|
|
|
if ( next_exit != NOTHING
|
|
&& (options & ROUTE_OPT_LOCKED)
|
|
&& !could_doit(executor, next_exit, A_LOCK))
|
|
{
|
|
return NOTHING;
|
|
}
|
|
|
|
return next_exit;
|
|
}
|