summaryrefslogtreecommitdiff
path: root/nodejs/lib
diff options
context:
space:
mode:
authorJulien Dessaux2024-05-05 00:08:28 +0200
committerJulien Dessaux2024-05-05 00:08:28 +0200
commit5aac233c08567844d6b99afb4d0a1a56725dd6c4 (patch)
tree337d883da98b020d4652b612eaa2d06fd9a1f5d5 /nodejs/lib
parent[node] crudely handle tradevolume limit while selling (diff)
downloadspacetraders-5aac233c08567844d6b99afb4d0a1a56725dd6c4.tar.gz
spacetraders-5aac233c08567844d6b99afb4d0a1a56725dd6c4.tar.bz2
spacetraders-5aac233c08567844d6b99afb4d0a1a56725dd6c4.zip
[node] fix shortest path to only hop through refueling points
Diffstat (limited to '')
-rw-r--r--nodejs/lib/ships.ts2
-rw-r--r--nodejs/lib/utils.ts29
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 );
+}