7 Commits

Author	SHA1	Message	Date
VariableVince	eb51853b05	Perf/Fix: spawn and other functions that need closest by unit (#3243) ... ## Description: Performance improvements. - **PlayerImpl**: for _nukeSpawn_, cache config to const. - **Other files**: for nukeSpawn and other functions doing the same, introduce findClosestBy function. - for **TradeShipExecution**, with the move from _distSortUnit_ to _findClosestBy_, also add check if port isActive, !_isMarkedForDeletion_ and !_isUnderConstruction_. These checks should have been there already, so now do it in one go to make use of the predicate isCandidate in findClosestBy. - for **TradeShipExectution.test.ts**, add mock functions for _isMarkedForDeletion_ and _isUnderConstruction_ because of the above. Also, set Unit tiles and Pathfinding node to actual valid TileRefs for the testing map. This prevents NaN as return value from manhattanDist. This problem was already present with the use of distSortUnit, but that function just did NaN - NaN, returned the first and only port unit in the array and called it a day. For findClosestBy we have to make sure the predicate manhattanDist actually returns a number instead of NaN so we need actually valid tiles. We now have a working test instead of a test that actually silently failed like before. - **PlayerImpl**: _warshipSpawn_ and _nukeSpawn_: Make use of the isCandidate predicate of findClosestBy to have warshipSpawn not return ports under construction or (smaller change) inactive. This fixes a bug i have seen right away (where Warship spawns from under construction Port). Same for _nukeSpawn_ silos, don't return inactive silo just to be sure now that we can easily add it to isCandidate predicate anyway. This costs no performance in the _nukeSpawn_ benchmarks actually. This should as a by-effecft fix an edge case bug i have seen, where a nuke is sent from a phantom silo. Some of this goes along with PR #3220 since playerImpl buildableUnits makes use of the underlying spawn functions via canBuild. Just like ConstructionExecution does. But i didn't want to add more to PR 3220 since there's already a lot in there. The new function _findClosestBy_ could also be applied to some other parts of code to benefit of it being faster, so i did that. _findClosestBy_ uses _findMinimumBy_, which is a little more generic in name. I think _findMinimumBy_ could be used by other parts of code, while _findClosestBy_ is more clear naming for what it does now. But we could ditch _findMinimumBy_ and just leave findClosestBy? Examples of synthetic benchmarks (not included in this PR): **BEFORE CHANGES (before Scamiv's PR #3241)** <img width="705" height="91" alt="image" src="https://github.com/user-attachments/assets/d6d91c08-39f1-4387-9ccc-e51951caa539" /> <img width="751" height="101" alt="image" src="https://github.com/user-attachments/assets/80d400ac-3408-4107-aa58-6d2a847311e9" /> **AFTER CHANGES (before Scamiv's PR #3241)**   **BEFORE CHANGES (after Scamiv's PR #3241)**   **AFTER CHANGES (after Scamiv's PR #3241)** <img width="717" height="96" alt="image" src="https://github.com/user-attachments/assets/5b106843-bf6e-4448-a8e8-94448fb30ced" /> <img width="767" height="92" alt="image" src="https://github.com/user-attachments/assets/e6714c7b-26c1-455b-adae-f0060f1cbc7b" /> _Also see more **BEFORE** and **AFTER** in this comment:_ https://github.com/openfrontio/OpenFrontIO/pull/3243#issuecomment-3949060395 _And here a comparison in the flame charts:_ - based on the same replay and tried to get the performance recording going at the same speed and length but always end up with small differences - because of a bug in replays currently, it puts you in with the same clientID/persistantID currently. This means we can also record part of what is normally only recordable with live human input (the playerActions/playerBuildables). **BEFORE** flame chart with nukeSpawn (human player) and maybeSendNuke (Nation players, uses nukeSpawn via canBuild):    **AFTER** flame chart with nukeSpawn (human player) and maybeSendNuke (Nation players, uses nukeSpawn via canBuild):      ## Please complete the following: - [x] I have added screenshots for all UI updates - [x] I process any text displayed to the user through translateText() and I've added it to the en.json file - [x] I have added relevant tests to the test directory - [x] I confirm I have thoroughly tested these changes and take full responsibility for any bugs introduced ## Please put your Discord username so you can be contacted if a bug or regression is found: tryout33	2026-03-23 16:23:49 -07:00
scamiv	c911bfb2d8	Packed unit updates / MotionPlans (#3292) ... ## Description: Reduce per-step `Unit` update traffic by shipping packed motion plans and letting the client advance plan-driven units locally. Changes: - Add packed motion plan records (`packedMotionPlans?: Uint32Array`) to game updates and transfer the buffer worker -> main. - Introduce `src/core/game/MotionPlans.ts` (schema + pack/unpack) for grid + train motion plans. - Extend `Game` with `recordMotionPlan(...)` and `drainPackedMotionPlans()`, and implement buffering/packing in `GameImpl`. - Treat units with motion plans as “plan-driven”: suppress per-tile `Unit` updates on `move()` and advance positions client-side. - Emit motion plans from executions: - `TradeShipExecution`: record/update grid motion plans and `touch()` when changing target after capture. - `TransportShipExecution`: record initial plan and update it when destination changes. - `TrainExecution`: record a train plan on init (engine + cars). - Client: apply motion plans in `GameView` and ensure `UnitLayer` updates sprites for motion-planned units even when no `Unit` updates arrived. ## Please complete the following: - [ ] I have added screenshots for all UI updates - [ ] I process any text displayed to the user through translateText() and I've added it to the en.json file - [ ] I have added relevant tests to the test directory - [ ] I confirm I have thoroughly tested these changes and take full responsibility for any bugs introduced ## Please put your Discord username so you can be contacted if a bug or regression is found: DISCORD_USERNAME	2026-02-27 20:54:42 -08:00
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
Arkadiusz Sygulski	b090f2f624	HPA* Pathfinding (#2815) ... ## 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`	2026-01-08 13:34:18 -08:00
Wraith	26f5d40819	build: migrate build system to Vite and test runner to Vitest & Remove depracated husky usage (#2703) ... - Replace Webpack with Vite for faster client bundling and HMR. - Migrate tests from Jest to Vitest and update configuration. - Update Web Worker instantiation to standard ESM syntax. - Implement Env utility in `src/core` for safe, hybrid environment variable access (Vite vs Node). - Refactor configuration loaders to remove direct `process.env` dependencies in shared code. - Update TypeScript environment definitions and project scripts for the new toolchain. - Remove the [depracated usage of the husky](https://github.com/typicode/husky/releases/tag/v9.0.1). ## Description: migrate build system to Vite and test runner to Vitest & Remove depracated husky usage ## Please complete the following: - [X] I have added screenshots for all UI updates - [X] I process any text displayed to the user through translateText() and I've added it to the en.json file - [ ] I have added relevant tests to the test directory - [X] I confirm I have thoroughly tested these changes and take full responsibility for any bugs introduced ## Please put your Discord username so you can be contacted if a bug or regression is found: wraith4081 --------- Co-authored-by: evanpelle <evanpelle@gmail.com>	2025-12-28 22:10:26 -08:00
DevelopingTom	d3c4cd6620	Record missing stats (#2407) ... ## Description: Some stats are missing from the recorded game stats: - Unit upgrade - Gold from trade and from steal The gold from trade/steal was introduced with [PR 784](https://github.com/openfrontio/OpenFrontIO/pull/784) but was quickly reverted with [PR 927](https://github.com/openfrontio/OpenFrontIO/pull/927), probably involuntarily. ## Please complete the following: - [x] I have added screenshots for all UI updates - [x] I process any text displayed to the user through translateText() and I've added it to the en.json file - [x] I have added relevant tests to the test directory - [x] I confirm I have thoroughly tested these changes and take full responsibility for any bugs introduced ## Please put your Discord username so you can be contacted if a bug or regression is found: IngloriousTom	2025-11-06 15:38:15 -08:00
VariableVince	b850a2f93d	Tradeship performance (#1448) ... ## Description: Small performance improvements for tradeship execution. With the new cap of 100 tradeships in total, the impact is smaller but still there. Also added jlrouillard's (Vivacious Box) test with permission from PR #1449. Tests 100% passed. - Save tradeship owner, destination port owner and tradeship current tile in constants for re-use. - Added check if wasCaptured was already set to true, before comparing origOwner and tradeship owner and setting wasCaptured to true. Currently, wasCaptured is set to true once and never back to false again. This PR keeps it that way but a but faster. - One less call to pathfinder needed: before calling pathfinder, check if current tile is destination port tile, and if so call complete. This is basically the same as pathfinder would do, but less complex without need for e.g. manhattan distance. - case PathFindResultType.Completed: isn't needed anymore because of the above. Kept as fallback. But moved it down in the switch statement, as there's a low(er) chance the case will ever be true. - Test if we need to find a new destination port for captured ship: currently, if this.wasCaptured is true, it will look for a new destination port each tick again and again. With this PR, only do this if destination port isn't owned by capturer, or if that port has become inactive. In tests with thousands of tradeships, went down from 300K+ times setting 'new' port, to only 1250 calls. **Q:** Will this code work for ships that are captured again, after being captured already? **A:** Yes. After wasCaptured is set to true once (after first capture), we only need to check each tick if the destination port is owned by the current tradeship owner, to know if we need to assign a new destination port again. ## Please complete the following: - [x] I have added screenshots for all UI updates - [x] I process any text displayed to the user through translateText() and I've added it to the en.json file - [x] I have added relevant tests to the test directory - [x] I confirm I have thoroughly tested these changes and take full responsibility for any bugs introduced - [x] I understand that submitting code with bugs that could have been caught through manual testing blocks releases and new features for all contributors ## Please put your Discord username so you can be contacted if a bug or regression is found: tryout33	2025-07-16 19:27:28 -04:00