@statedelta/graph-core

Algoritmos de grafo agnósticos à fonte — busca best-first e travessias sobre uma interface abstrata neighbors / cost / heuristic / key. Zero dependências de runtime.

Filosofia

Não há noção de grid nem de coordenadas aqui — só grafo. Um GraphState alimenta adjacência explícita (das edges); um Board alimenta um grid implícito (via @statedelta-apex/board-kit). Um código, duas fontes. É a camada de algoritmo que tanto a rede quanto o espaço reusam.

Instalação

pnpm add @statedelta/graph-core

Conceito

Toda busca recebe o mesmo formato e devolve o mesmo SearchResult:

interface PathOptions<N> {
  neighbors: (node: N) => Iterable<N>;
  key: (node: N) => string | number; // identidade
  cost?: (from: N, to: N) => number; // default 1
  heuristic?: (node: N, goal: N) => number; // default 0
  maxExpansions?: number;
}

interface SearchResult<N> {
  path: N[] | null; // start..goal inclusive, ou null
  cost: number; // soma dos custos, ou Infinity
  found: boolean;
  expanded: number;
}

Algoritmos

| Função | Tipo | Ótimo? | | --------------------------------- | -------------------- | ----------------------------- | | bfs(start, goal, opts) | sem peso (FIFO) | sim (menos arestas) | | dijkstra(start, goal, opts) | com peso | sempre | | aStar(start, goal, opts) | com peso + heur. | sim, se heurística admissível | | greedyBestFirst(start, goal, …) | só heurística | não (rápido) | | bidirectional(start, goal, …) | sem peso, 2 frentes | sim (menos arestas) | | flowField(sources, opts) | Dijkstra multi-fonte | campo de custo p/ N agentes | | reachable(start, opts) | alcançáveis | — | | floodFill(start, opts) | região (com gate) | — |

import { aStar } from "@statedelta/graph-core";

const graph = {
  /* ... adjacência ... */
};
const result = aStar("A", "D", {
  neighbors: (n) => graph[n].map((e) => e.to),
  cost: (a, b) => weight(a, b),
  key: (n) => n,
});
result.path; // ["A", …, "D"] ou null

aStar/dijkstra/greedyBestFirst compartilham um core best-first parametrizado pela prioridade f(g,h) (não são implementações separadas), sobre um MinHeap binário com deleção preguiçosa.

Tipos Exportados

import {
  aStar,
  dijkstra,
  greedyBestFirst,
  bfs,
  bidirectional,
  flowField,
  reachable,
  floodFill,
  MinHeap,
} from "@statedelta/graph-core";
import type {
  NodeKey,
  SearchResult,
  PathOptions,
  TraverseOptions,
  BidirectionalOptions,
} from "@statedelta/graph-core";

Roadmap

Algoritmos avançados de grafo: JPS (grid uniforme), Theta* (any-angle), D* Lite (replanning incremental), além de utilitários sobre GraphState (topo-sort, ciclos, componentes).

License

MIT