mirror of
https://github.com/openfrontio/OpenFrontIO.git
synced 2026-06-22 16:46:38 +00:00
b090f2f624
## Pathfinding with HPA*
Hi! The primary objective of this PR is to replace per-tile A* with
hierarchical pathfinding - HPA*. In practice, this means we create an
abstract graph on top of the actual map with far fewer points and use it
to decide on general path structure. Only then we go back to tile-level
and build path between selected waypoints. This speeds up long distance
pathfinding by over 1000x in some cases. To make the review easier, it
comes with a benchmark and visual playground.
## PREPROCESSING
H part of HPA* means "hierarchical" and requires preprocessing.
This PR includes pre-processing as part inside `new Game()` constructor.
It takes about 135ms for `giantworldmap` on my machine, which increases
the effective initialization from ~95ms to ~230ms. This time could be
reduced in different ways, which are **out of scope** for this PR.
After confirming the initialization time is bearable on low-end devices,
I argue merging this PR as-is is acceptable tradeoff. It creates small
lag at the beginning of a round but pays for itself in the first minute
of the match.
## Nerdy details
**Architecture**
- HPA*-style hierarchical pathfinding
- 32×32 sectors on minimap with gateway nodes on borders
- Gateway graph built via BFS during preprocessing
- Water component optimization skips unreachable gateway pairs
- A* on gateway graph → local A* within sectors → Bresenham path
smoothing
- Minimap upscaling identical to currently used in MiniAStar
**Key Optimizations**
- Typed arrays instead of high-level primitives
- Stamp-based visited tracking (no need to recreate buffers, O(1)
clearing)
- Optional - enabled by default - caching of tile paths between gateways
- Line of sight smoothing for the final path
## Review Focus
Play with included tools, benchmark and visualization. Pathfinding
should be safe to merge as a black box - you do not need to understand
the details. Outcomes can be tested empirically in-game. Visualize (and
share!) edge cases with included playground. Confirm the 100x speedup is
real with benchmark.
If you plan to dive into the code, I suggest the following order:
- Pathfinding abstraction in `src/core/pathfinding/`
- Pathfinding tests in `tests/core/pathfinding/`
- NavMesh in `src/core/pathfinding/navmesh/` + integration with
`Game.ts`
- Benchmark in `tests/pathfinding/benchmark/`
Do not look at playground's code, it has been created with a clanker.
The design is 100% mine and I spent way too long polishing it, but I
haven't even once edited the code manually. There is probably no
abstraction whatsoever, just do not look at the code, let it play.
## Core Changes
#### Pathfinding (`src/core/pathfinding/navmesh/`)
- HPA* + refinement -> three phased pathfinding: A* over the graph ->
naive path -> refinement
- comes with A* and BFS optimized for for specific needs
#### Pre-Processing (`src/core/pathfinding/navmesh/`)
- identify water bodies to avoid pathfinding between disconnected nodes
- create high-level graph of gateways on top of tile map
#### Abstraction (`src/core/pathfinding/`)
- common `PathFinder` interface that can return full path and also act
as state machine (`.next()`)
- adapters for both new and legacy algorithm with fallback to legacy if
navigation mesh not available
#### Benchmark (`tests/pathfinding/benchmark/`)
- `npx tsx tests/pathfinding/benchmark/run.ts` - no guesswork, numbers
- `npx tsx tests/pathfinding/benchmark/run.ts --synthetic` - 1000s of
synthetic paths
- `npx tsc tests/pathfinding/benchmark/generate.ts` - generate more as
needed, test new maps
- includes ONE synthetic scenario to avoid PR bloat, generate more
locally / later
#### Playground (`tests/pathfinding/playground/`)
- `npx tsx tests/pathfinding/playground/server.ts` - visualize paths
with both new and legacy algorithm
## Benchmarks
### Compared with legacy in default - hand picked - scenario:
```
Initialization: 95.95ms -> 227.29ms
Pathfinding: 3038.43ms -> 6.45ms
Distance: 26972 -> 26810 tiles
```
### 42,000 synthetic routes across all maps
```
Running 42 synthetic scenarios with hpa.cached adapter...
✅ synthetic/achiran | Init: 93.42ms | Path: 139.07ms | Dist: 1481630 tiles | Routes: 1000/1000
✅ synthetic/africa | Init: 87.14ms | Path: 155.08ms | Dist: 1829414 tiles | Routes: 1000/1000
✅ synthetic/asia | Init: 57.60ms | Path: 112.55ms | Dist: 1204082 tiles | Routes: 1000/1000
✅ synthetic/australia | Init: 78.18ms | Path: 77.12ms | Dist: 978375 tiles | Routes: 1000/1000
✅ synthetic/baikal | Init: 78.26ms | Path: 152.14ms | Dist: 1600016 tiles | Routes: 1000/1000
✅ synthetic/baikalnukewars | Init: 81.44ms | Path: 165.90ms | Dist: 1699283 tiles | Routes: 1000/1000
✅ synthetic/betweentwoseas | Init: 29.29ms | Path: 114.99ms | Dist: 1338075 tiles | Routes: 1000/1000
✅ synthetic/blacksea | Init: 30.66ms | Path: 93.14ms | Dist: 949217 tiles | Routes: 1000/1000
✅ synthetic/britannia | Init: 74.12ms | Path: 85.62ms | Dist: 866752 tiles | Routes: 1000/1000
✅ synthetic/deglaciatedantarctica | Init: 105.49ms | Path: 192.93ms | Dist: 1574684 tiles | Routes: 1000/1000
✅ synthetic/didier | Init: 81.51ms | Path: 153.70ms | Dist: 1734876 tiles | Routes: 1000/1000
✅ synthetic/eastasia | Init: 49.29ms | Path: 128.63ms | Dist: 1410270 tiles | Routes: 1000/1000
✅ synthetic/europe | Init: 92.55ms | Path: 178.35ms | Dist: 1525216 tiles | Routes: 1000/1000
✅ synthetic/europeclassic | Init: 33.50ms | Path: 104.40ms | Dist: 1209759 tiles | Routes: 1000/1000
✅ synthetic/falklandislands | Init: 63.00ms | Path: 107.41ms | Dist: 1080251 tiles | Routes: 1000/1000
✅ synthetic/faroeislands | Init: 71.91ms | Path: 49.52ms | Dist: 604613 tiles | Routes: 1000/1000
✅ synthetic/fourislands | Init: 45.75ms | Path: 78.91ms | Dist: 937439 tiles | Routes: 1000/1000
✅ synthetic/gatewaytotheatlantic | Init: 81.00ms | Path: 257.06ms | Dist: 2555551 tiles | Routes: 1000/1000
✅ synthetic/giantworldmap | Init: 214.25ms | Path: 220.42ms | Dist: 1976693 tiles | Routes: 1000/1000
✅ synthetic/gulfofstlawrence | Init: 45.16ms | Path: 96.05ms | Dist: 1014604 tiles | Routes: 1000/1000
✅ synthetic/halkidiki | Init: 74.68ms | Path: 149.39ms | Dist: 1546781 tiles | Routes: 1000/1000
✅ synthetic/iceland | Init: 58.72ms | Path: 78.16ms | Dist: 1001554 tiles | Routes: 1000/1000
✅ synthetic/italia | Init: 29.78ms | Path: 139.93ms | Dist: 1412024 tiles | Routes: 1000/1000
✅ synthetic/japan | Init: 161.07ms | Path: 118.65ms | Dist: 1154393 tiles | Routes: 1000/1000
✅ synthetic/lemnos | Init: 52.59ms | Path: 136.69ms | Dist: 1481101 tiles | Routes: 1000/1000
✅ synthetic/lisbon | Init: 49.27ms | Path: 86.53ms | Dist: 1032011 tiles | Routes: 1000/1000
✅ synthetic/manicouagan | Init: 53.74ms | Path: 110.52ms | Dist: 1307630 tiles | Routes: 1000/1000
✅ synthetic/mars | Init: 29.39ms | Path: 80.55ms | Dist: 1091702 tiles | Routes: 1000/1000
✅ synthetic/mena | Init: 26.37ms | Path: 120.09ms | Dist: 1272751 tiles | Routes: 1000/1000
✅ synthetic/montreal | Init: 26.08ms | Path: 106.77ms | Dist: 1187736 tiles | Routes: 1000/1000
✅ synthetic/newyorkcity | Init: 56.60ms | Path: 181.19ms | Dist: 1753875 tiles | Routes: 1000/1000
✅ synthetic/northamerica | Init: 96.29ms | Path: 123.02ms | Dist: 1217221 tiles | Routes: 1000/1000
✅ synthetic/oceania | Init: 52.81ms | Path: 51.96ms | Dist: 482373 tiles | Routes: 1000/1000
✅ synthetic/pangaea | Init: 21.29ms | Path: 56.58ms | Dist: 716189 tiles | Routes: 1000/1000
✅ synthetic/pluto | Init: 53.89ms | Path: 141.62ms | Dist: 1304362 tiles | Routes: 1000/1000
✅ synthetic/southamerica | Init: 85.19ms | Path: 123.03ms | Dist: 1301403 tiles | Routes: 1000/1000
✅ synthetic/straitofgibraltar | Init: 76.68ms | Path: 108.30ms | Dist: 1304592 tiles | Routes: 1000/1000
✅ synthetic/straitofhormuz | Init: 38.97ms | Path: 67.78ms | Dist: 754920 tiles | Routes: 1000/1000
✅ synthetic/surrounded | Init: 95.35ms | Path: 90.18ms | Dist: 1017142 tiles | Routes: 1000/1000
✅ synthetic/svalmel | Init: 60.58ms | Path: 104.75ms | Dist: 1235501 tiles | Routes: 1000/1000
✅ synthetic/twolakes | Init: 62.05ms | Path: 94.54ms | Dist: 1140807 tiles | Routes: 1000/1000
✅ synthetic/world | Init: 41.43ms | Path: 93.42ms | Dist: 873406 tiles | Routes: 1000/1000
Completed 42 scenarios
Total Initialization Time: 2796.32ms
Total Pathfinding Time: 5026.64ms
Total Distance: 53160274 tiles
```
## Playground
**That's the fun part**. Watch NavMesh running circles around legacy
`PathFinder.Mini` in real time. Debug inner workings, test edge cases,
share URLs for debugging.
https://github.com/user-attachments/assets/34e2e3f5-fbc1-4b1f-917d-820766e98d5d
## Discord Tag
`moleole`
263 lines
7.5 KiB
Go
263 lines
7.5 KiB
Go
package main
|
|
|
|
import (
|
|
"encoding/json"
|
|
"flag"
|
|
"fmt"
|
|
"log"
|
|
"os"
|
|
"path/filepath"
|
|
"strings"
|
|
"sync"
|
|
)
|
|
|
|
// mapsFlag holds the comma-separated list of map names passed via the --maps command-line argument.
|
|
var mapsFlag string
|
|
|
|
// maps defines the registry of available maps to be processed.
|
|
// Each entry contains the folder name and a flag indicating if it's a test map.
|
|
//
|
|
// New maps need to be added here in order to allow the map-generator to process them.
|
|
var maps = []struct {
|
|
Name string
|
|
IsTest bool
|
|
}{
|
|
{Name: "africa"},
|
|
{Name: "asia"},
|
|
{Name: "australia"},
|
|
{Name: "achiran"},
|
|
{Name: "baikal"},
|
|
{Name: "baikalnukewars"},
|
|
{Name: "betweentwoseas"},
|
|
{Name: "blacksea"},
|
|
{Name: "britannia"},
|
|
{Name: "britanniaclassic"},
|
|
{Name: "deglaciatedantarctica"},
|
|
{Name: "eastasia"},
|
|
{Name: "europe"},
|
|
{Name: "europeclassic"},
|
|
{Name: "falklandislands"},
|
|
{Name: "faroeislands"},
|
|
{Name: "fourislands"},
|
|
{Name: "gatewaytotheatlantic"},
|
|
{Name: "giantworldmap"},
|
|
{Name: "gulfofstlawrence"},
|
|
{Name: "halkidiki"},
|
|
{Name: "iceland"},
|
|
{Name: "italia"},
|
|
{Name: "japan"},
|
|
{Name: "lisbon"},
|
|
{Name: "manicouagan"},
|
|
{Name: "mars"},
|
|
{Name: "mena"},
|
|
{Name: "montreal"},
|
|
{Name: "newyorkcity"},
|
|
{Name: "northamerica"},
|
|
{Name: "oceania"},
|
|
{Name: "pangaea"},
|
|
{Name: "pluto"},
|
|
{Name: "southamerica"},
|
|
{Name: "straitofgibraltar"},
|
|
{Name: "surrounded"},
|
|
{Name: "svalmel"},
|
|
{Name: "world"},
|
|
{Name: "lemnos"},
|
|
{Name: "twolakes"},
|
|
{Name: "didier"},
|
|
{Name: "amazonriver"},
|
|
{Name: "big_plains", IsTest: true},
|
|
{Name: "half_land_half_ocean", IsTest: true},
|
|
{Name: "ocean_and_land", IsTest: true},
|
|
{Name: "plains", IsTest: true},
|
|
{Name: "giantworldmap", IsTest: true},
|
|
{Name: "world", IsTest: true},
|
|
}
|
|
|
|
// outputMapDir returns the absolute path to the directory where generated map files should be written.
|
|
// It distinguishes between test and production output locations.
|
|
func outputMapDir(isTest bool) (string, error) {
|
|
cwd, err := os.Getwd()
|
|
if err != nil {
|
|
return "", fmt.Errorf("failed to get working directory: %w", err)
|
|
}
|
|
if isTest {
|
|
return filepath.Join(cwd, "..", "tests", "testdata", "maps"), nil
|
|
}
|
|
return filepath.Join(cwd, "..", "resources", "maps"), nil
|
|
}
|
|
|
|
// inputMapDir returns the absolute path to the directory containing source map assets.
|
|
// It distinguishes between test and production asset locations.
|
|
func inputMapDir(isTest bool) (string, error) {
|
|
cwd, err := os.Getwd()
|
|
if err != nil {
|
|
return "", fmt.Errorf("failed to get working directory: %w", err)
|
|
}
|
|
if isTest {
|
|
return filepath.Join(cwd, "assets", "test_maps"), nil
|
|
} else {
|
|
return filepath.Join(cwd, "assets", "maps"), nil
|
|
}
|
|
}
|
|
|
|
// processMap handles the end-to-end generation for a single map.
|
|
// It reads the source image and JSON, generates the terrain data, and writes the binary outputs and updated manifest.
|
|
func processMap(name string, isTest bool) error {
|
|
outputMapBaseDir, err := outputMapDir(isTest)
|
|
if err != nil {
|
|
return fmt.Errorf("failed to get map directory: %w", err)
|
|
}
|
|
|
|
inputMapDir, err := inputMapDir(isTest)
|
|
if err != nil {
|
|
return fmt.Errorf("failed to get input map directory: %w", err)
|
|
}
|
|
|
|
inputPath := filepath.Join(inputMapDir, name, "image.png")
|
|
imageBuffer, err := os.ReadFile(inputPath)
|
|
if err != nil {
|
|
return fmt.Errorf("failed to read map file %s: %w", inputPath, err)
|
|
}
|
|
|
|
// Read the info.json file
|
|
manifestPath := filepath.Join(inputMapDir, name, "info.json")
|
|
manifestBuffer, err := os.ReadFile(manifestPath)
|
|
if err != nil {
|
|
return fmt.Errorf("failed to read info file %s: %w", manifestPath, err)
|
|
}
|
|
|
|
// Parse the info buffer as dynamic JSON
|
|
var manifest map[string]interface{}
|
|
if err := json.Unmarshal(manifestBuffer, &manifest); err != nil {
|
|
return fmt.Errorf("failed to parse info.json for %s: %w", name, err)
|
|
}
|
|
|
|
// Generate maps
|
|
result, err := GenerateMap(GeneratorArgs{
|
|
ImageBuffer: imageBuffer,
|
|
RemoveSmall: !isTest, // Don't remove small islands for test maps
|
|
Name: name,
|
|
})
|
|
if err != nil {
|
|
return fmt.Errorf("failed to generate map for %s: %w", name, err)
|
|
}
|
|
|
|
manifest["map"] = map[string]interface{}{
|
|
"width": result.Map.Width,
|
|
"height": result.Map.Height,
|
|
"num_land_tiles": result.Map.NumLandTiles,
|
|
}
|
|
manifest["map4x"] = map[string]interface{}{
|
|
"width": result.Map4x.Width,
|
|
"height": result.Map4x.Height,
|
|
"num_land_tiles": result.Map4x.NumLandTiles,
|
|
}
|
|
manifest["map16x"] = map[string]interface{}{
|
|
"width": result.Map16x.Width,
|
|
"height": result.Map16x.Height,
|
|
"num_land_tiles": result.Map16x.NumLandTiles,
|
|
}
|
|
|
|
mapDir := filepath.Join(outputMapBaseDir, name)
|
|
if err := os.MkdirAll(mapDir, 0755); err != nil {
|
|
return fmt.Errorf("failed to create output directory for %s: %w", name, err)
|
|
}
|
|
if err := os.WriteFile(filepath.Join(mapDir, "map.bin"), result.Map.Data, 0644); err != nil {
|
|
return fmt.Errorf("failed to write combined binary for %s: %w", name, err)
|
|
}
|
|
if err := os.WriteFile(filepath.Join(mapDir, "map4x.bin"), result.Map4x.Data, 0644); err != nil {
|
|
return fmt.Errorf("failed to write combined binary for %s: %w", name, err)
|
|
}
|
|
if err := os.WriteFile(filepath.Join(mapDir, "map16x.bin"), result.Map16x.Data, 0644); err != nil {
|
|
return fmt.Errorf("failed to write combined binary for %s: %w", name, err)
|
|
}
|
|
if err := os.WriteFile(filepath.Join(mapDir, "thumbnail.webp"), result.Thumbnail, 0644); err != nil {
|
|
return fmt.Errorf("failed to write thumbnail for %s: %w", name, err)
|
|
}
|
|
|
|
// Serialize the updated manifest to JSON
|
|
updatedManifest, err := json.MarshalIndent(manifest, "", " ")
|
|
if err != nil {
|
|
return fmt.Errorf("failed to serialize manifest for %s: %w", name, err)
|
|
}
|
|
|
|
if err := os.WriteFile(filepath.Join(mapDir, "manifest.json"), updatedManifest, 0644); err != nil {
|
|
return fmt.Errorf("failed to write manifest for %s: %w", name, err)
|
|
}
|
|
return nil
|
|
}
|
|
|
|
// parseMapsFlag validates and parses the --maps command-line argument.
|
|
// It returns a set of selected map names or nil if no flag was provided (implying all maps).
|
|
func parseMapsFlag() (map[string]bool, error) {
|
|
if mapsFlag == "" {
|
|
return nil, nil
|
|
}
|
|
|
|
validNames := make(map[string]bool, len(maps))
|
|
for _, m := range maps {
|
|
validNames[m.Name] = true
|
|
}
|
|
|
|
selected := make(map[string]bool)
|
|
for _, name := range strings.Split(mapsFlag, ",") {
|
|
if !validNames[name] {
|
|
return nil, fmt.Errorf("map %q is not defined", name)
|
|
}
|
|
selected[name] = true
|
|
}
|
|
return selected, nil
|
|
}
|
|
|
|
// loadTerrainMaps manages the concurrent generation of all selected maps.
|
|
// It spins up goroutines for each map and aggregates any errors.
|
|
func loadTerrainMaps() error {
|
|
selectedMaps, err := parseMapsFlag()
|
|
if err != nil {
|
|
return err
|
|
}
|
|
var wg sync.WaitGroup
|
|
errChan := make(chan error, len(maps))
|
|
|
|
// Process maps concurrently
|
|
for _, mapItem := range maps {
|
|
if selectedMaps != nil && !selectedMaps[mapItem.Name] {
|
|
continue
|
|
}
|
|
wg.Add(1)
|
|
mapItem := mapItem
|
|
go func() {
|
|
defer wg.Done()
|
|
if err := processMap(mapItem.Name, mapItem.IsTest); err != nil {
|
|
errChan <- err
|
|
}
|
|
}()
|
|
}
|
|
|
|
// Wait for all goroutines to complete
|
|
wg.Wait()
|
|
close(errChan)
|
|
|
|
// Check for errors
|
|
for err := range errChan {
|
|
if err != nil {
|
|
return err
|
|
}
|
|
}
|
|
|
|
return nil
|
|
}
|
|
|
|
// main is the entry point for the map generator tool.
|
|
// It parses flags and triggers the map generation process.
|
|
func main() {
|
|
flag.StringVar(&mapsFlag, "maps", "", "optional comma-separated list of maps to process. ex: --maps=world,eastasia,big_plains")
|
|
flag.Parse()
|
|
|
|
if err := loadTerrainMaps(); err != nil {
|
|
log.Fatalf("Error generating terrain maps: %v", err)
|
|
}
|
|
|
|
fmt.Println("Terrain maps generated successfully")
|
|
}
|