Files
Arkadiusz Sygulski 0e3ced3bfa Pathfinding Refactor pt. 2 (#2866)
## Playtest

https://pf-pt-2.openfront.dev/

## Pathfinding Refactor pt. 2

<img width="1536" height="1024" alt="image"
src="https://github.com/user-attachments/assets/9477958e-54b7-4c83-b317-ba789e809e9e"
/>


This is a follow-up to a previous PR introducing pathfinding changes.
This time, it introduces a complete refactor of `pathfinding` directory
and breakdown into composable pieces.

### Unified PathFinder interface

`PathFinder<T>` and `SteppingPathFinder<T>` are introduced to unify
**all** pathfinding across the application. First one exposes complete
path, while stepping variant allows the callee to iterate over the path
by calling `.next`. All pathfinders share this one common interface,
which makes them easy to use in any scenario -
`PathFinding.Water(game).search(from, to)`.

`SteppingPathFinder<T>` extends `PathFinder<T>` with an ability to
iterate over the path. It handles caching, storing current index and
invalidation. This allows the units to not care about the inner workings
of the pathfinder and just call `pf.next(current, target)` and receive
instructions on what to do next.

### Common entry point

All pathfinders are now exposed from common `PathFinding` entrypoint:

- `PathFinding.Water`
- `PathFinding.Rail`
- `PathFinding.Stations`
- `PathFinding.Rail`

Additional entry point is introduced for pathfinders which need to work
both in the worker, but also on the frontend, which lacks `Game`
interface. Currently only `UniversalPathFinding.Parabola` is available.

### Spatial Query

New module has been introduced close to `pathfinding` - `SpatialQuery`.
It aims to resolve any questions game may have about finding tiles
meeting criteria. Currently `SpatialQuery.closestShore(player, target)`
and `SpatialQuery.closestShoreByWater(player, target)` are available -
they help answering questions about naval invasion: "What is the best
landing location from user's click?" and "Which our tile should be used
to launch the transport ship?". Under the hood they use very similar
mechanics to pathfinding, so it felt right to put them close by.

### Modular architecture

Pathfinders now support transformers: `MiniMapTransformer`,
`ShoreCoercingTransformer`, `ComponentCheckTransformer`,
`SmoothingTransformer`. Transformers functions like a middleware in the
pathfinding chain. They wrap around the pathfinder and provide
additional functionality. This allows the pathfinder to focus on
actually finding the path instead of doing unrelated things.

Example chain for simple (A*) water pathfinding:
```ts
static WaterSimple(game: Game): SteppingPathFinder<TileRef> {
  const miniMap = game.miniMap();
  const pf = new AStarWater(miniMap);

  return PathFinderBuilder.create(pf)
    .wrap((pf) => new ShoreCoercingTransformer(pf, miniMap))
    .wrap((pf) => new MiniMapTransformer(pf, game.map(), miniMap))
    .buildWithStepper(tileStepperConfig(game));
}
```

The Pathfinder - here `AStarWater` - does not care about the conversion
between minimap and main map tiles. It also does not care if the source
or destination is a land tile. The transformers take care of that. The
pathfinder gets a set of valid coordinates and produces the path -
that's it.

Modular approach makes working on a particular set of utilities much
easier - for example map upscaling is handled consistently across all
pathfinders. Additionally, the pathfinders are not tied to the
particular map resolution used. Pass them a different map and they will
work the same.

### Algorithms

Algorithms used are neatly organized inside
`src/core/pathfinding/algorithms`. They are prefixed with the algorithm
name and suffixed with the use case. File without suffix exposes generic
version ready to traverse any graph with adapters. Specialized versions
either use an adapter or inline logic when performance is critical -
using adapters leads to 20-30% performance loss.

The directory includes `A*` and `BFS` but also other useful utils, such
as `AbstractGraph` used to generate... an abstract graph on top of the
tile map and `ConnectedComponents` helping to identify whether two tiles
are connected by a path without actually computing the path.

### Playground

The playground have been updated with new algorithms, including tweaked
very greedy `A*`.

<img width="2175" height="1424" alt="image"
src="https://github.com/user-attachments/assets/1f833651-0024-4299-bf86-882f5368358c"
/>

### Tests

Yeah, there are some, a little too many if I say so myself. But there
are no useless tests. I had to ensure refactored code works somehow
reliably. This PR comes with trust me bro guarantee, but I would
appreciate someone confirming **naval invasions, nukes (esp. MIRV) and
warships**.

### Discord
`moleole`

GL & HF
2026-01-11 20:11:14 -08:00

212 lines
5.6 KiB
TypeScript

import compression from "compression";
import express, { Request, Response } from "express";
import { dirname, join } from "path";
import { fileURLToPath } from "url";
import {
clearCache as clearMapCache,
getMapMetadata,
listMaps,
setConfig,
} from "./api/maps.js";
import { clearAdapterCaches, computePath } from "./api/pathfinding.js";
// Parse command-line arguments
const args = process.argv.slice(2);
const noCache = args.includes("--no-cache");
// Configure map loading
if (noCache) {
setConfig({ cachePaths: false });
console.log("Path caching disabled (--no-cache)");
}
const app = express();
const PORT = process.env.PORT ?? 5555;
// Middleware
app.use(compression()); // gzip compression for large responses
app.use(express.json({ limit: "50mb" })); // JSON body parser with larger limit
// Serve static files from public directory
const publicDir = join(dirname(fileURLToPath(import.meta.url)), "public");
app.use(express.static(publicDir));
// API Routes
/**
* GET /api/maps
* List all available maps
*/
app.get("/api/maps", (req: Request, res: Response) => {
try {
const maps = listMaps();
res.json({ maps });
} catch (error) {
console.error("Error listing maps:", error);
res.status(500).json({
error: "Failed to list maps",
message: error instanceof Error ? error.message : String(error),
});
}
});
/**
* GET /api/maps/:name
* Get map metadata (map data, dimensions)
*/
app.get("/api/maps/:name", async (req: Request, res: Response) => {
try {
const { name } = req.params;
const metadata = await getMapMetadata(name);
res.json(metadata);
} catch (error) {
console.error(`Error loading map ${req.params.name}:`, error);
if (error instanceof Error && error.message.includes("ENOENT")) {
res.status(404).json({
error: "Map not found",
message: `Map "${req.params.name}" does not exist`,
});
} else {
res.status(500).json({
error: "Failed to load map",
message: error instanceof Error ? error.message : String(error),
});
}
}
});
/**
* GET /api/maps/:name/thumbnail
* Get map thumbnail image
*/
app.get("/api/maps/:name/thumbnail", (req: Request, res: Response) => {
try {
const { name } = req.params;
const thumbnailPath = join(
dirname(fileURLToPath(import.meta.url)),
"../../../resources/maps",
name,
"thumbnail.webp",
);
res.sendFile(thumbnailPath);
} catch (error) {
console.error(`Error loading thumbnail for ${req.params.name}:`, error);
res.status(404).json({
error: "Thumbnail not found",
message: error instanceof Error ? error.message : String(error),
});
}
});
/**
* POST /api/pathfind
* Compute pathfinding between two points
*
* Request body:
* {
* map: string,
* from: [x, y],
* to: [x, y],
* adapters?: string[] // Optional: which comparison adapters to run
* }
*
* Response:
* {
* primary: { path, length, time, debug: { nodePath, initialPath, timings } },
* comparisons: [{ adapter, path, length, time }, ...]
* }
*/
app.post("/api/pathfind", async (req: Request, res: Response) => {
try {
const { map, from, to, adapters } = req.body;
// Validate request
if (!map || !from || !to) {
return res.status(400).json({
error: "Invalid request",
message: "Missing required fields: map, from, to",
});
}
if (
!Array.isArray(from) ||
from.length !== 2 ||
!Array.isArray(to) ||
to.length !== 2
) {
return res.status(400).json({
error: "Invalid coordinates",
message: "from and to must be [x, y] coordinate arrays",
});
}
// Compute paths
const result = await computePath(
map,
from as [number, number],
to as [number, number],
{ adapters },
);
res.json(result);
} catch (error) {
console.error("Error computing path:", error);
if (error instanceof Error && error.message.includes("is not water")) {
res.status(400).json({
error: "Invalid coordinates",
message: error.message,
});
} else {
res.status(500).json({
error: "Failed to compute path",
message: error instanceof Error ? error.message : String(error),
});
}
}
});
/**
* POST /api/cache/clear
* Clear all caches (useful for development)
*/
app.post("/api/cache/clear", (req: Request, res: Response) => {
try {
clearMapCache();
clearAdapterCaches();
res.json({ message: "Caches cleared successfully" });
} catch (error) {
console.error("Error clearing caches:", error);
res.status(500).json({
error: "Failed to clear caches",
message: error instanceof Error ? error.message : String(error),
});
}
});
// Error handling middleware
app.use((err: Error, req: Request, res: Response, next: any) => {
console.error("Unhandled error:", err);
res.status(500).json({
error: "Internal server error",
message: err.message,
});
});
// Start server
app.listen(PORT, () => {
console.log(`
╔════════════════════════════════════════════════════════════╗
║ Pathfinding Playground Server ║
╚════════════════════════════════════════════════════════════╝
Server running at: http://localhost:${PORT}
Configuration:
- Path caching: ${noCache ? "disabled" : "enabled"}
Press Ctrl+C to stop
`);
});