summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJulien Dessaux2024-04-07 23:04:38 +0200
committerJulien Dessaux2024-04-07 23:04:38 +0200
commit91d394dfc9bfa18e60031bbe1507e14e017240f3 (patch)
treef41996e7ab7c73e4bfbe5eee7805f58fac74a38a
parent[node] multiple contracting fixes and some more refactoring (diff)
downloadspacetraders-91d394dfc9bfa18e60031bbe1507e14e017240f3.tar.gz
spacetraders-91d394dfc9bfa18e60031bbe1507e14e017240f3.tar.bz2
spacetraders-91d394dfc9bfa18e60031bbe1507e14e017240f3.zip
[node] Implemented multi hops in system navigation
Diffstat (limited to '')
-rw-r--r--nodejs/lib/ships.ts31
-rw-r--r--nodejs/lib/utils.ts48
2 files changed, 68 insertions, 11 deletions
diff --git a/nodejs/lib/ships.ts b/nodejs/lib/ships.ts
index 67dca00..4ae64c7 100644
--- a/nodejs/lib/ships.ts
+++ b/nodejs/lib/ships.ts
@@ -10,6 +10,7 @@ import {
ShipIsStillOnCooldownError,
ShipRequiresMoreFuelForNavigationError,
} from './errors.ts';
+import * as libSystems from './systems.ts';
import {
Agent,
Cargo,
@@ -20,7 +21,11 @@ import {
Registration,
Waypoint,
} from './types.ts';
+import {
+ shortestPath,
+} from './utils.ts';
import * as dbAgents from '../database/agents.ts';
+import * as dbContracts from '../database/contracts.ts';
export async function getShips(): Promise<Array<Ship>> {
const response = await send<Array<Ship>>({endpoint: `/my/ships`, page: 1});
@@ -98,26 +103,32 @@ export class Ship {
return this.cargo.units >= this.cargo.capacity * 0.9;
}
async navigate(waypoint: Waypoint): Promise<void> {
- if (this.nav.waypointSymbol === waypoint.symbol) return;
- // TODO compute fuel consumption and refuel if we do not have enough OR if the destination does not sell fuel?
- await this.refuel();
+ let path = shortestPath(await libSystems.waypoint(this.nav.route.destination.symbol), waypoint, this.fuel.capacity, await libSystems.waypoints(this.nav.systemSymbol));
+ while (path.length > 0) {
+ const next = path.pop();
+ if (next === undefined) break;
+ if (next.fuel > this.fuel.current) {
+ // TODO also refuel if the destination does not sell fuel?
+ await this.refuel();
+ }
+ await this.navigateTo(next.symbol);
+ }
+ }
+ private async navigateTo(symbol: string): Promise<void> {
await this.orbit();
- // TODO if we do not have enough fuel, make a stop to refuel along the way or drift to the destination
- const response = await send<{fuel: Fuel, nav: Nav}>({endpoint: `/my/ships/${this.symbol}/navigate`, method: 'POST', payload: { waypointSymbol: waypoint.symbol }}); // TODO events field
+ const response = await send<{fuel: Fuel, nav: Nav}>({endpoint: `/my/ships/${this.symbol}/navigate`, method: 'POST', payload: { waypointSymbol: symbol }}); // TODO events field
if (response.error) {
switch(response.error.code) {
case 4203: // not enough fuel
+ // This should not happen given the logic in navigate()
const srmffne = response.error.data as ShipRequiresMoreFuelForNavigationError;
- // TODO test if it exceeds our maximum
- // find an intermediate stop to refuel if that is the case
debugLog(response);
+ debugLog(srmffne);
throw response;
- //await refuel(ship);
- //return await navigate(ship, waypoint);
case 4214:
const sicite = response.error.data as ShipIsCurrentlyInTransitError;
await sleep(sicite.secondsToArrival * 1000);
- return await this.navigate(waypoint);
+ return await this.navigateTo(symbol);
default: // yet unhandled error
debugLog(response);
throw response;
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('-');
}