diff options
Diffstat (limited to '')
| -rw-r--r-- | nodejs/lib/ships.ts | 2 | ||||
| -rw-r--r-- | nodejs/lib/utils.ts | 29 |
2 files changed, 25 insertions, 6 deletions
diff --git a/nodejs/lib/ships.ts b/nodejs/lib/ships.ts index ff38164..74419fc 100644 --- a/nodejs/lib/ships.ts +++ b/nodejs/lib/ships.ts @@ -103,7 +103,7 @@ export class Ship { return this.cargo.units >= this.cargo.capacity * 0.9; } async navigate(waypoint: Waypoint): Promise<void> { - let path = shortestPath(await libSystems.waypoint(this.nav.route.destination.symbol), waypoint, this.fuel.capacity, await libSystems.waypoints(this.nav.systemSymbol)); + let path = await 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; diff --git a/nodejs/lib/utils.ts b/nodejs/lib/utils.ts index c8f3d7f..db39349 100644 --- a/nodejs/lib/utils.ts +++ b/nodejs/lib/utils.ts @@ -1,7 +1,14 @@ +import { + debugLog, +} from './api.ts'; import { PriorityQueue } from './priority_queue.ts'; import { + market, +} from './systems.ts'; +import { Cargo, CargoManifest, + CommonThing, Waypoint, } from './types.ts'; @@ -53,7 +60,7 @@ export function sortByDistanceFrom<T extends Point>(a: Point, points: Array<T>): 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 { +export async function shortestPath(origin: Waypoint, destination: Waypoint, range: number, waypoints: Array<Waypoint>): Promise<ShortestPath> { let backtrace: {[key: string]: Step} = {}; let fuels: {[key: string]: number} = {}; // fuel = distance + 1 per hop let unvisited: {[key: string]: Waypoint} = {}; @@ -69,7 +76,6 @@ export function shortestPath(origin: Waypoint, destination: Waypoint, range: num 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) { @@ -79,13 +85,22 @@ export function shortestPath(origin: Waypoint, destination: Waypoint, range: num const total = step.fuel + f; if (fuels[ws] > total) { fuels[ws] = total; - queue.enqueue({waypoint: w, prev: symbol, fuel: f, total: total}, total); + const nextStep = {waypoint: w, prev: symbol, fuel: f, total: total}; + if (ws === destination.symbol) { + backtrace[ws] = nextStep; + break; + } + if (!w.traits.some(t => t.symbol === 'MARKETPLACE')) continue; + const m = await market(w); + if (whatCanBeTradedAt({"FUEL":1}, m.exports.concat(m.exchange)).length === 0) continue; + queue.enqueue(nextStep, 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}.`; + let step = backtrace[destination.symbol]; + if (step === undefined) throw `Cannot compute shortest path from ${origin.symbol} to ${destination.symbol} with range ${range}.`; + for (; step.waypoint.symbol != origin.symbol; step = backtrace[step.prev]) { result.push({symbol: step.waypoint.symbol, fuel: step.fuel}); } return result; @@ -94,3 +109,7 @@ export function shortestPath(origin: Waypoint, destination: Waypoint, range: num export function systemFromWaypoint(waypoint: string): string { return waypoint.split('-').slice(0,2).join('-'); } + +export function whatCanBeTradedAt(cargo: CargoManifest, goods: Array<CommonThing>): Array<CommonThing> { + return goods.filter(g => cargo[g.symbol] !== undefined ); +} |