From 91d394dfc9bfa18e60031bbe1507e14e017240f3 Mon Sep 17 00:00:00 2001
From: Julien Dessaux
Date: Sun, 7 Apr 2024 23:04:38 +0200
Subject: [node] Implemented multi hops in system navigation

---
 nodejs/lib/utils.ts | 48 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 47 insertions(+), 1 deletion(-)

(limited to 'nodejs/lib/utils.ts')

diff --git a/nodejs/lib/utils.ts b/nodejs/lib/utils.ts
index 480e7a4..c8f3d7f 100644
--- a/nodejs/lib/utils.ts
+++ b/nodejs/lib/utils.ts
@@ -1,4 +1,9 @@
-import { Cargo, CargoManifest } from './types.ts';
+import { PriorityQueue } from './priority_queue.ts';
+import {
+	Cargo,
+	CargoManifest,
+	Waypoint,
+} from './types.ts';
 
 export type CategorizedCargo = {
 	wanted: CargoManifest;
@@ -45,6 +50,47 @@ export function sortByDistanceFrom<T extends Point>(a: Point, points: Array<T>):
 	return result;
 }
 
+type Step = {waypoint: Waypoint, prev: string, fuel: number, total: number};
+type ShortestPath = Array<{symbol: string, fuel: number}>;
+
+export function shortestPath(origin: Waypoint, destination: Waypoint, range: number, waypoints: Array<Waypoint>): ShortestPath {
+	let backtrace: {[key: string]: Step} = {};
+	let fuels: {[key: string]: number} = {}; // fuel = distance + 1 per hop
+	let unvisited: {[key: string]: Waypoint} = {};
+	waypoints.forEach(function(w) {
+		fuels[w.symbol] = Infinity;
+		unvisited[w.symbol] = w;
+	});
+	fuels[origin.symbol] = 0;
+	let queue = new PriorityQueue();
+	queue.enqueue({waypoint: origin, prev: origin.symbol, fuel: 0, total: 0}, 0);
+	while(!queue.isEmpty()) {
+		let step = queue.dequeue() as Step;
+		const symbol = step.waypoint.symbol;
+		if (!(symbol in unvisited)) continue;
+		backtrace[symbol] = step;
+		if (symbol === destination.symbol) break;
+		const prev = unvisited[symbol];
+		delete unvisited[symbol];
+		for(const ws in unvisited) {
+			const w = unvisited[ws];
+			const f = distance(prev, w) + 1;
+			if (f > range) continue;
+			const total = step.fuel + f;
+			if (fuels[ws] > total) {
+				fuels[ws] = total;
+				queue.enqueue({waypoint: w, prev: symbol, fuel: f, total: total}, total);
+			}
+		}
+	}
+	let result: ShortestPath = [];
+	for (let step = backtrace[destination.symbol]; step.waypoint.symbol != origin.symbol; step = backtrace[step.prev]) {
+		if (step === undefined) throw `Cannot compute shortest path from ${origin.symbol} to ${destination.symbol} with range ${range}.`;
+		result.push({symbol: step.waypoint.symbol, fuel: step.fuel});
+	}
+	return result;
+}
+
 export function systemFromWaypoint(waypoint: string): string {
 	return waypoint.split('-').slice(0,2).join('-');
 }
-- 
cgit v1.2.3