alois/OpenFrontIO
1
0
Fork 0
mirror of https://github.com/openfrontio/OpenFrontIO.git synced 2026-06-22 03:53:49 +00:00
Code Issues Packages Projects Releases Wiki Activity
Files
webgpu-cleaner
OpenFrontIO/tests/pathfinding/playground/public/index.html
T
Arkadiusz Sygulski 85def73bd9 Pathfinding Refinement (#2878) 
# Pathfinding pt. 3

## Description:

This PR introduces final change to the pathfinding - path refinement. It
optimizes Line of Sight refinement by searching with for the best tile
with a binary search instead of linearly. And then spends the recovered
budget on better refinement of the first and last 50 tiles of the
journey - the place where user is most likely to look at. Additionally
this PR re-introduces magnitude check and makes the ships prefer sailing
close to the coast, but not too close.

## 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

## What?

| Before | After |
| :--- | :--- |
| <img width="1097" height="1117" alt="image"
src="https://github.com/user-attachments/assets/4a0b300d-10ef-4151-b6dc-33acfb49f992"
/> | <img width="1093" height="1119" alt="image"
src="https://github.com/user-attachments/assets/cf81c515-c145-40f4-91e5-a4353986907b"
/> |
| <img width="1096" height="1129" alt="image"
src="https://github.com/user-attachments/assets/21b46bce-f961-4259-88f6-fe4a66180270"
/> | <img width="1098" height="1126" alt="image"
src="https://github.com/user-attachments/assets/d92587d1-e6b6-4353-b4a4-1efe71bca43d"
/> |

## Performance

There is actually a severe performance impact of these changes. The path
initial path takes almost 2x as long to generate - this is because pre
processing can only do so much if the initial path is ugly. Luckily in
real gameplay we only need to do this calculation once per edge, so the
actual observed performance impact should be much smaller. Cache FTW.

| | No Cache | Cache |
| :--- | :--- | :--- |
| Before | 277.04ms | 208.58ms |
| After | 498.34ms | 264.27ms |

## DebugSpan

Small utility, it allows any code to be easily instrumented for
performance. The idea is the same as with [OTEL
Spans](https://opentelemetry.io/docs/concepts/signals/traces/). Produce
a span, create sub-spans, measure whatever you need. Works only when
`globalThis.__DEBUG_SPAN_ENABLED__ === true`, otherwise no-op.

Cool stuff, try it out:
```ts
// Convenient wrapper, small performance impact
return DebugSpan.wrap('add', () => a + b)

// Synchronous API, basically free
DebugSpan.start('work')
work()
DebugSpan.end()

// Create sub spans
DebugSpan.wrap('complex', () => {
  const aPlusB = DebugSpan.wrap('add', () => a + b)
  DebugSpan.set('additionResult', () => aPlusB)  // Store data
  return aPlusB * c
})

// Access spans, data and timing
const span = DebugSpan.getLast()
const compelxSpan = DebugSpan.getLast('complex')

console.log(complexSpan.duration, complexSpan.data['additionResult'])
```

These are virtually free and can be enabled on-demand **in production**
and available in the devtools. Under the hood devtools integration is
just a wrapper around [Performance
API](https://developer.mozilla.org/en-US/docs/Web/API/Performance_API).
For clarity data keys not prefixed by `$` are omitted from the
integration. Every key prefixed with `$` must be fully JSON
serializable.

<img width="977" height="799" alt="image"
src="https://github.com/user-attachments/assets/b4d43506-1639-4f78-a611-30e61de12a07"
/>
2026-01-13 12:39:54 -08:00

283 lines
9.9 KiB
HTML
Raw Permalink Blame History

<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Pathfinding Playground - Interactive Visualization</title>
<link rel="stylesheet" href="styles.css" />
</head>
<body>
<!-- Fullscreen map container -->
<div class="canvas-container">
<div class="canvas-wrapper" id="canvasWrapper">
<canvas id="mapCanvas"></canvas>
<canvas id="overlayCanvas"></canvas>
</div>
<!-- Interactive canvas added dynamically outside wrapper -->
</div>
<!-- Welcome screen -->
<div class="welcome-screen" id="welcomeScreen">
<div class="welcome-content">
<h1>Pathfinding Playground</h1>
<p>Interactive visualization for naval pathfinding algorithms</p>
<!-- Map grid -->
<div class="map-grid" id="mapGrid">
<div class="map-card" data-map-index="0">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 1</div>
</div>
<div class="map-card" data-map-index="1">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 2</div>
</div>
<div class="map-card" data-map-index="2">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 3</div>
</div>
<div class="map-card" data-map-index="3">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 4</div>
</div>
<div class="map-card" data-map-index="4">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 5</div>
</div>
<div class="map-card" data-map-index="5">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 6</div>
</div>
<div class="map-card" data-map-index="6">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 7</div>
</div>
<div class="map-card" data-map-index="7">
<img
width="360"
height="180"
src="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' width='360' height='180'%3E%3Crect fill='%23333' width='360' height='180'/%3E%3C/svg%3E"
alt="Loading..."
/>
<div class="map-card-name" style="opacity: 0">Map 8</div>
</div>
</div>
<!-- Dropdown for other maps -->
<div class="welcome-selector">
<label for="welcomeMapSelect">Or select from all maps:</label>
<select id="welcomeMapSelect">
<option value="">Loading maps...</option>
</select>
</div>
</div>
</div>
<!-- Top overlay panel -->
<div class="top-panel">
<h1>Pathfinding Playground</h1>
<div class="scenario-selector">
<select id="scenarioSelect">
<option value="">Loading...</option>
</select>
</div>
<div class="status-section">
<span id="status">Select a scenario to begin</span>
</div>
</div>
<!-- Debug controls panel (left) -->
<div class="debug-panel">
<div class="debug-panel-row">
<button class="toggle-button" id="showInitialPath" data-active="false">
Initial Path
</button>
<button class="toggle-button" id="showUsedNodes" data-active="false">
Used Nodes
</button>
</div>
<div class="debug-panel-row">
<button class="toggle-button" id="showNodes" data-active="false">
Nodes
</button>
<button class="toggle-button" id="showSectorGrid" data-active="false">
Sectors
</button>
<button class="toggle-button" id="showEdges" data-active="false">
Edges
</button>
</div>
</div>
<!-- View controls panel (right) -->
<div class="view-panel">
<div class="zoom-control">
<input type="range" id="zoom" min="0.1" max="5" step="0.1" value="1" />
<span id="zoomValue">1.0x</span>
</div>
<button class="toggle-button" id="showColoredMap" data-active="false">
Colored Map
</button>
<button id="clearPoints" class="clear-button">Clear Points</button>
</div>
<!-- Timings panel (left side) -->
<div class="timings-panel" id="timingsPanel">
<div class="timings-header">Performance</div>
<div class="timing-section">
<div class="timing-label">
<button
class="refresh-icon"
id="refreshHpa"
title="Recompute HPA* path"
>
<span>↻</span>
</button>
HPA* <span class="timing-label-detail" id="hpaTiles"></span>
</div>
<div class="timing-value-large" id="hpaTime">—</div>
<div class="timing-breakdown" id="timingBreakdown">
<div class="timing-item" id="timingEarlyExit" style="display: none">
<span class="timing-name">Early Exit:</span>
<span class="timing-value" id="timingEarlyExitValue">—</span>
</div>
<div class="timing-item" id="timingFindNodes" style="display: none">
<span class="timing-name">Find Nodes:</span>
<span class="timing-value" id="timingFindNodesValue">—</span>
</div>
<div
class="timing-item"
id="timingAbstractPath"
style="display: none"
>
<span class="timing-name">Abstract Path:</span>
<span class="timing-value" id="timingAbstractPathValue">—</span>
</div>
<div class="timing-item" id="timingInitialPath" style="display: none">
<span class="timing-name">Initial Path:</span>
<span class="timing-value" id="timingInitialPathValue">—</span>
</div>
<div class="timing-item" id="timingSmoothPath" style="display: none">
<span class="timing-name">Smooth Path:</span>
<span class="timing-value" id="timingSmoothPathValue">—</span>
</div>
</div>
</div>
<div class="timing-section" id="comparisonsSection" style="display: none">
<div class="timing-label">Comparisons</div>
<div id="comparisonsContainer"></div>
</div>
</div>
<!-- Legend panel -->
<div class="legend-panel">
<div class="legend-header">Legend</div>
<div class="legend">
<div class="legend-item">
<div
class="legend-color"
style="background: #ff4444; height: 8px"
></div>
<span>Start Point</span>
</div>
<div class="legend-item">
<div
class="legend-color"
style="background: #44ff44; height: 8px"
></div>
<span>End Point</span>
</div>
<div class="legend-item">
<div class="legend-color" style="background: #00ffff"></div>
<span>HPA*</span>
</div>
<div class="legend-item">
<div class="legend-color" style="background: #ff00ff"></div>
<span>Initial Path</span>
</div>
<div class="legend-item">
<div
class="legend-color"
style="background: #ffff00; height: 8px"
></div>
<span>Used Nodes</span>
</div>
<div class="legend-item">
<div
class="legend-color"
style="
background: #aaaaaa;
height: 6px;
width: 6px;
border-radius: 50%;
"
></div>
<span>Nodes</span>
</div>
<div class="legend-item">
<div
class="legend-color"
style="background: #777777; height: 2px"
></div>
<span>Sectors</span>
</div>
<div class="legend-item">
<div
class="legend-color"
style="background: #00ffaa; height: 2px"
></div>
<span>Edges</span>
</div>
</div>
</div>
<!-- Error notification (toast) -->
<div id="error" class="error-toast"></div>
<!-- Tooltip -->
<div id="tooltip"></div>
<script src="client.js"></script>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink