diff options
| -rw-r--r-- | nodejs/lib/ships.ts | 31 | ||||
| -rw-r--r-- | nodejs/lib/utils.ts | 48 |
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('-'); } |