src/core/pathfinding.ts - main - docNemo/hex-map-editor

src/core/pathfinding.ts
144 строки5 KB
docNemo
feat(hexcrawl): раскрытие карты, время пути, журнал и точка расширения
31 июл 2026, 17:59
31 июл 2026, 17:59f06076f
import { hexDistance, hexNeighbors } from './hex';
import type { HexMap } from './map-model';

/**
 * Поиск маршрута наименьшей стоимости по гекс-сетке.
 *
 * Общий для прокладки дорог при генерации и для расчёта времени пути в игре:
 * две отдельные реализации неизбежно разошлись бы, и дорога перестала бы
 * соответствовать маршруту, который модуль показывает партии.
 */

/** Стоимость входа в гекс. `Infinity` означает непроходимость. */
export type CostFunction = (index: number) => number;

export interface PathResult {
  /** Гексы маршрута от начального до конечного включительно. */
  path: number[];
  /** Суммарная стоимость входа во все гексы, кроме начального. */
  cost: number;
}

/** Двоичная куча минимумов: очередь с приоритетом для A*. */
class PriorityQueue {
  private readonly keys: number[] = [];
  private readonly values: number[] = [];

  get size(): number {
    return this.values.length;
  }

  push(key: number, value: number): void {
    this.keys.push(key);
    this.values.push(value);
    let child = this.values.length - 1;
    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (this.keys[parent]! <= this.keys[child]!) break;
      this.swap(parent, child);
      child = parent;
    }
  }

  pop(): number | undefined {
    if (this.values.length === 0) return undefined;
    const top = this.values[0]!;

    const lastKey = this.keys.pop()!;
    const lastValue = this.values.pop()!;
    if (this.values.length > 0) {
      this.keys[0] = lastKey;
      this.values[0] = lastValue;

      let parent = 0;
      for (;;) {
        const left = parent * 2 + 1;
        const right = left + 1;
        let smallest = parent;
        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 === parent) break;
        this.swap(parent, smallest);
        parent = smallest;
      }
    }

    return top;
  }

  private swap(a: number, b: number): void {
    const key = this.keys[a]!;
    const value = this.values[a]!;
    this.keys[a] = this.keys[b]!;
    this.values[a] = this.values[b]!;
    this.keys[b] = key;
    this.values[b] = value;
  }
}

export interface PathOptions {
  /**
   * Наименьшая возможная стоимость шага. Используется в эвристике, поэтому обязана
   * не превышать реальную: завышенная оценка сделала бы A* неоптимальным и маршрут
   * перестал бы быть кратчайшим.
   */
  minStepCost?: number;
}

/**
 * Маршрут наименьшей стоимости между гексами, либо `null`, если пути нет.
 *
 * Эвристика — расстояние в гексах, умноженное на минимальную стоимость шага.
 * Она допустима по построению, поэтому найденный маршрут оптимален.
 */
export function findCheapestPath(
  map: HexMap,
  from: number,
  to: number,
  costOf: CostFunction,
  options: PathOptions = {},
): PathResult | null {
  if (from === to) return { path: [from], cost: 0 };

  const minStepCost = options.minStepCost ?? 1;
  const target = map.coordAt(to);

  const bestCost = new Float64Array(map.size).fill(Infinity);
  const cameFrom = new Int32Array(map.size).fill(-1);
  const closed = new Uint8Array(map.size);

  bestCost[from] = 0;
  const queue = new PriorityQueue();
  queue.push(hexDistance(map.coordAt(from), target) * minStepCost, from);

  while (queue.size > 0) {
    const current = queue.pop()!;
    if (closed[current]) continue;
    closed[current] = 1;

    if (current === to) {
      const path: number[] = [];
      for (let node = to; node !== -1; node = cameFrom[node]!) path.push(node);
      return { path: path.reverse(), cost: bestCost[to]! };
    }

    const costSoFar = bestCost[current]!;

    for (const neighbour of hexNeighbors(map.coordAt(current))) {
      const neighbourIndex = map.indexOf(neighbour);
      if (neighbourIndex < 0 || closed[neighbourIndex]) continue;

      const step = costOf(neighbourIndex);
      if (!Number.isFinite(step)) continue;

      const tentative = costSoFar + step;
      if (tentative >= bestCost[neighbourIndex]!) continue;

      bestCost[neighbourIndex] = tentative;
      cameFrom[neighbourIndex] = current;
      queue.push(tentative + hexDistance(neighbour, target) * minStepCost, neighbourIndex);
    }
  }

  return null;
}