Battle-for-Tismo/shared/roads.js

// Pre-generated road network. The network is built once, after the cities are
// placed but before any player controls them, and never changes afterwards.
//
// The steps mirror the brief:
//   1. weigh every possible city-to-city route with the same hex pathfinding
//      units use, on a cost that grows exponentially with the terrain;
//   2. order those candidate links by cost and keep a greedy geometric spanner
//      of stretch `ROADS.spannerStretch`, so the road network stays sparse
//      while no two cities are more than that factor worse off than direct;
//   3. return the set of tiles the chosen routes cross.

import { key, parseKey } from "./hex.js";
import { ROADS } from "./data/roads.js";

// Cost of running a road through a tile. Non-land tiles are impassable, and a
// city tile is free because cities are founded with a road already in place.
export function tileRoadCost(tile, isCity = false) {
  if (isCity) return ROADS.cityCost;
  if (!tile || tile.terrainClass !== "Land") return Infinity;
  return Math.pow(ROADS.costBase, tile.movementCostMultiplier || 1);
}

class MinHeap {
  constructor() {
    this.keys = [];
    this.values = [];
  }

  isEmpty() {
    return this.keys.length === 0;
  }

  push(priority, value) {
    this.keys.push(priority);
    this.values.push(value);
    let index = this.keys.length - 1;
    while (index > 0) {
      const parent = (index - 1) >> 1;
      if (this.keys[parent] <= this.keys[index]) break;
      this._swap(parent, index);
      index = parent;
    }
  }

  pop() {
    const value = this.values[0];
    const last = this.keys.length - 1;
    this.keys[0] = this.keys[last];
    this.values[0] = this.values[last];
    this.keys.pop();
    this.values.pop();
    let index = 0;
    while (true) {
      let smallest = index;
      const left = (index << 1) + 1;
      const right = left + 1;
      if (left < this.keys.length && this.keys[left] < this.keys[smallest]) smallest = left;
      if (right < this.keys.length && this.keys[right] < this.keys[smallest]) smallest = right;
      if (smallest === index) break;
      this._swap(index, smallest);
      index = smallest;
    }
    return value;
  }

  _swap(a, b) {
    const k = this.keys[a];
    this.keys[a] = this.keys[b];
    this.keys[b] = k;
    const v = this.values[a];
    this.values[a] = this.values[b];
    this.values[b] = v;
  }
}

// Dijkstra over the land tiles from `source`, costing each step through
// `stepCost(coords, tile)`. Returns the distance to every reachable tile and
// the parent needed to rebuild the route.
//
// `targets` (optional) is a set of canonical keys the caller actually needs:
// once every one of them is settled the search stops, which keeps the
// road-network build from flooding the whole continent from each city.
export function shortestPaths(source, topology, tiles, stepCost, targets = null) {
  const sourceKey = key(source.x, source.y);
  const distance = new Map([[sourceKey, 0]]);
  const parent = new Map();
  const settled = new Set();
  const remaining = targets ? new Set(targets) : null;
  if (remaining) remaining.delete(sourceKey);
  const heap = new MinHeap();
  heap.push(0, source);
  while (!heap.isEmpty()) {
    const current = heap.pop();
    const currentKey = key(current.x, current.y);
    if (settled.has(currentKey)) continue;
    settled.add(currentKey);
    if (remaining) {
      remaining.delete(currentKey);
      if (remaining.size === 0 && distance.has(currentKey)) break;
    }
    for (const neighbour of topology.neighbours(current.x, current.y)) {
      const nk = key(neighbour.x, neighbour.y);
      const tile = tiles[nk];
      if (!tile || tile.terrainClass !== "Land") continue;
      const cost = stepCost(neighbour, tile);
      if (!Number.isFinite(cost)) continue;
      const candidate = distance.get(currentKey) + cost;
      if (candidate < (distance.has(nk) ? distance.get(nk) : Infinity)) {
        distance.set(nk, candidate);
        parent.set(nk, current);
        heap.push(candidate, neighbour);
      }
    }
  }
  return { distance, parent };
}

function reconstruct(parent, sourceKey, goalKey) {
  const path = [];
  let cursor = parseKey(goalKey);
  while (cursor && key(cursor.x, cursor.y) !== sourceKey) {
    path.push(cursor);
    cursor = parent.get(key(cursor.x, cursor.y));
    if (path.length > 100000) return [];
  }
  path.push(parseKey(sourceKey));
  return path.reverse();
}

// Distance between two city indices in a weighted adjacency map, or Infinity
// when no spanner path connects them yet.
function spannerDistance(adjacency, from, to) {
  if (from === to) return 0;
  const distance = new Map([[from, 0]]);
  const settled = new Set();
  const heap = new MinHeap();
  heap.push(0, from);
  while (!heap.isEmpty()) {
    const current = heap.pop();
    if (settled.has(current)) continue;
    settled.add(current);
    if (current === to) return distance.get(current);
    for (const [next, weight] of adjacency.get(current) || []) {
      const candidate = distance.get(current) + weight;
      if (candidate < (distance.has(next) ? distance.get(next) : Infinity)) {
        distance.set(next, candidate);
        heap.push(candidate, next);
      }
    }
  }
  return Infinity;
}

// Builds the road tile set connecting `cities`. `cities` is a list of objects
// with a `coords` field; the returned Set holds canonical "x,y" keys, cities
// included.
export function buildRoadNetwork(cities, topology, tiles, options = {}) {
  const stretch = options.spannerStretch || ROADS.spannerStretch;
  const roads = new Set();
  if (!cities || cities.length === 0) return roads;
  const cityKeys = cities.map((city) => key(city.coords.x, city.coords.y));
  const isCity = new Set(cityKeys);
  const stepCost = (coords, tile) => tileRoadCost(tile, isCity.has(key(coords.x, coords.y)));
  for (const k of cityKeys) roads.add(k);
  if (cities.length < 2) return roads;

  // Every possible link, with the cheapest route and its cost. Each search may
  // stop as soon as it has reached every other city, instead of flooding the
  // whole continent.
  const searches = cities.map((city, index) =>
    shortestPaths(
      city.coords,
      topology,
      tiles,
      stepCost,
      cityKeys.filter((_, other) => other !== index)
    )
  );
  const edges = [];
  for (let a = 0; a < cities.length; a++) {
    for (let b = a + 1; b < cities.length; b++) {
      if (!searches[a].distance.has(cityKeys[b])) continue;
      edges.push({
        a,
        b,
        cost: searches[a].distance.get(cityKeys[b]),
        path: reconstruct(searches[a].parent, cityKeys[a], cityKeys[b]),
      });
    }
  }
  edges.sort((a, b) => a.cost - b.cost || a.a - b.a || a.b - b.b);
  for (const edge of greedySpanner(edges, stretch)) {
    for (const coords of edge.path) roads.add(key(coords.x, coords.y));
  }
  return roads;
}

// Greedy geometric spanner: walk the candidate links cheapest first and keep a
// link only when the links kept so far do not already connect its ends within
// `stretch` times its cost. Exported so the spanner property can be tested on a
// synthetic edge list without a hex map.
export function greedySpanner(edges, stretch = ROADS.spannerStretch) {
  const adjacency = new Map();
  const chosen = [];
  const addEdge = (a, b, cost) => {
    if (!adjacency.has(a)) adjacency.set(a, []);
    if (!adjacency.has(b)) adjacency.set(b, []);
    adjacency.get(a).push([b, cost]);
    adjacency.get(b).push([a, cost]);
  };
  for (const edge of edges) {
    if (spannerDistance(adjacency, edge.a, edge.b) > stretch * edge.cost) {
      addEdge(edge.a, edge.b, edge.cost);
      chosen.push(edge);
    }
  }
  return chosen;
}