From 5aac233c08567844d6b99afb4d0a1a56725dd6c4 Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Sun, 5 May 2024 00:08:28 +0200 Subject: [node] fix shortest path to only hop through refueling points --- nodejs/automation/selling.ts | 9 +-------- nodejs/lib/ships.ts | 2 +- nodejs/lib/utils.ts | 29 ++++++++++++++++++++++++----- 3 files changed, 26 insertions(+), 14 deletions(-) (limited to 'nodejs') diff --git a/nodejs/automation/selling.ts b/nodejs/automation/selling.ts index 5dee8f7..b17aad0 100644 --- a/nodejs/automation/selling.ts +++ b/nodejs/automation/selling.ts @@ -3,12 +3,9 @@ import * as libSystems from '../lib/systems.ts'; import { categorizeCargo, sortByDistanceFrom, + whatCanBeTradedAt, } from '../lib/utils.ts'; import { Ship } from '../lib/ships.ts'; -import { - CargoManifest, - CommonThing, -} from '../lib/types.ts'; // example ctx { ship: {XXX}, keep: 'SILVER_ORE' } export async function sell(ship: Ship, good: string): Promise { @@ -54,7 +51,3 @@ export async function sell(ship: Ship, good: string): Promise { throw new Error(`Ship {ship.symbol} has found no importing or exchanging market for its cargo in the system`); } } - -function whatCanBeTradedAt(cargo: CargoManifest, goods: Array): Array { - return goods.filter(g => cargo[g.symbol] !== undefined ); -} 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 { - 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(a: Point, points: Array): 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): ShortestPath { +export async function shortestPath(origin: Waypoint, destination: Waypoint, range: number, waypoints: Array): Promise { 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): Array { + return goods.filter(g => cargo[g.symbol] !== undefined ); +} -- cgit v1.2.3