From 1b59961ce2385252e3346ea6107b15a2c1feafe6 Mon Sep 17 00:00:00 2001 From: kboz Date: Sun, 27 Sep 2026 22:36:34 +0200 Subject: feat(backend): port route-planning backend to Go Add a Go implementation mirroring the Python pipeline (loader, graph, pathfinder, arbitrage, market, route, manager) under internal/core, with ESI client/API integration and setup endpoints. Reuses backend/src as the working directory so existing data/cache paths keep working. --- backend-go/internal/core/route.go | 434 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 434 insertions(+) create mode 100644 backend-go/internal/core/route.go (limited to 'backend-go/internal/core/route.go') diff --git a/backend-go/internal/core/route.go b/backend-go/internal/core/route.go new file mode 100644 index 0000000..1a8b862 --- /dev/null +++ b/backend-go/internal/core/route.go @@ -0,0 +1,434 @@ +package core + +import ( + "container/heap" + "log" + "sort" +) + +const ( + MaxCapital = 100000000000.0 // 100B + MaxTradesToConsider = 200 // Keep bound so we don't evaluate forever, python doesn't effectively bound it +) + +type Action struct { + ActionType string `json:"action_type"` // "buy" or "sell" + Item string `json:"item"` + TypeID int `json:"type_id"` + Quantity int `json:"quantity"` + Price float64 `json:"price"` +} + +type RouteStep struct { + ID int `json:"id"` + LocationID int `json:"location_id"` + Location string `json:"location"` + LocationType string `json:"location_type"` + SystemID int `json:"system_id,omitempty"` + SystemName string `json:"system_name,omitempty"` + StationName string `json:"station_name,omitempty"` + Security float64 `json:"security,omitempty"` + RegionID int `json:"region_id,omitempty"` + Actions []Action `json:"actions"` +} + +type RouteInfo struct { + ProfitRate float64 `json:"profit_rate"` + Risk float64 `json:"risk"` + Capital float64 `json:"capital"` + TransportTime float64 `json:"transport_time"` + GrossProfit float64 `json:"gross_profit"` + NetProfit float64 `json:"net_profit"` +} + +type RoutePlan struct { + Route []RouteStep + Info *RouteInfo + OptimizedTrades []Trade + Path []int + RawOffsets []int +} + +type Ship struct { +TaxRate float64 `json:"tax_rate"` +ProfitThreshold float64 `json:"profit_threshold"` +MaxCapital float64 `json:"max_capital"` +SnipeThreshold float64 `json:"snipe_profit_threshold"` +Location int `json:"location"` +Cargo float64 `json:"cargo"` +MaxWarpSpeed float64 `json:"max_warp_speed"` +MaxSubwarpSpeed float64 `json:"max_subwarp_speed"` +GankersAreas map[string]float64 `json:"gankers_areas"` +PlayerCost float64 `json:"player_cost"` +RiskCost float64 `json:"risk_cost"` +ShipCost float64 `json:"ship_cost"` +} + +type tradeDensityHeap struct { + trades []Trade +} +func (h tradeDensityHeap) Len() int { return len(h.trades) } +func (h tradeDensityHeap) Less(i, j int) bool { + // Reverse sorted by profit density + di := h.trades[i].GrossProfit / h.trades[i].Cargo + dj := h.trades[j].GrossProfit / h.trades[j].Cargo + return di > dj +} +func (h tradeDensityHeap) Swap(i, j int) { h.trades[i], h.trades[j] = h.trades[j], h.trades[i] } +func (h *tradeDensityHeap) Push(x any) { h.trades = append(h.trades, x.(Trade)) } +func (h *tradeDensityHeap) Pop() any { + old := h.trades + n := len(old) + x := old[n-1] + h.trades = old[0 : n-1] + return x +} + +func tradeCapitalEfficiency(t Trade) float64 { + invested := t.FromPrice * float64(t.Quantity) + if invested > 0 { + return t.GrossProfit / invested + } + return 0.0 +} + +func minInt(vars ...int) int { + m := vars[0] + for _, v := range vars[1:] { + if v < m { + m = v + } + } + return m +} + +func maxFloat(vars ...float64) float64 { + m := vars[0] + for _, v := range vars[1:] { + if v > m { + m = v + } + } + return m +} + +func buildRankedTriplets(trades []Trade, shipLoc int) [][3]int { + // Sort by capital efficiency descending + sorted := make([]Trade, len(trades)) + copy(sorted, trades) + sort.Slice(sorted, func(i, j int) bool { + return tradeCapitalEfficiency(sorted[i]) > tradeCapitalEfficiency(sorted[j]) + }) + + var ranked [][3]int + seen := make(map[[3]int]bool) + + for _, t := range sorted { + trip := [3]int{shipLoc, t.FromStation, t.ToStation} + if !seen[trip] { + seen[trip] = true + ranked = append(ranked, trip) + } + } + return ranked +} + +func buildStationPairIndex(trades []Trade) map[[2]int][]Trade { + index := make(map[[2]int][]Trade) + for _, t := range trades { + pair := [2]int{t.FromStation, t.ToStation} + index[pair] = append(index[pair], t) + } + for k := range index { + sort.Slice(index[k], func(i, j int) bool { + di := index[k][i].GrossProfit / index[k][i].Cargo + dj := index[k][j].GrossProfit / index[k][j].Cargo + return di > dj + }) + } + return index +} + +func selectTrades(routeStations [3]int, tradesByPair map[[2]int][]Trade, ship Ship) []Trade { + var candidatePairs [][2]int + for i, fromStation := range routeStations { + for _, toStation := range routeStations[i+1:] { + pair := [2]int{fromStation, toStation} + + // ensure unique pairs + exists := false + for _, cp := range candidatePairs { + if cp == pair { + exists = true + break + } + } + if !exists { + candidatePairs = append(candidatePairs, pair) + } + } + } + + // merge candidates into max heap based on profit density + h := &tradeDensityHeap{} + heap.Init(h) + for _, pair := range candidatePairs { + if ts, ok := tradesByPair[pair]; ok { + for _, t := range ts { + heap.Push(h, t) + } + } + } + + usedOrders := make(map[int]int) + var optimized []Trade + var cargo, capital float64 + + for h.Len() > 0 { + t := heap.Pop(h).(Trade) + + fromRemaining, ok := usedOrders[t.FromOrderID] + if !ok { + fromRemaining = t.Quantity + } + toRemaining, ok := usedOrders[t.ToOrderID] + if !ok { + toRemaining = t.Quantity + } + + maxQtyCargo := int((ship.Cargo - cargo) / (t.Cargo / float64(t.Quantity))) // rough item volume + itemVol := t.Cargo / float64(t.Quantity) + if itemVol == 0 { + itemVol = 0.01 // avoid divide by zero just in case + maxQtyCargo = t.Quantity + } else { + maxQtyCargo = int((ship.Cargo - cargo) / itemVol) + } + + maxQtyCapital := int((MaxCapital - capital) / t.FromPrice) + + maxQty := minInt(t.Quantity, fromRemaining, toRemaining, maxQtyCargo, maxQtyCapital) + + if maxQty <= 0 { + continue + } + + cargo += itemVol * float64(maxQty) + capital += t.FromPrice * float64(maxQty) + + usedOrders[t.FromOrderID] = fromRemaining - maxQty + usedOrders[t.ToOrderID] = toRemaining - maxQty + + updated := t + updated.Quantity = maxQty + updated.Cargo = itemVol * float64(maxQty) + if t.Quantity > 0 { + updated.GrossProfit = t.GrossProfit * (float64(maxQty) / float64(t.Quantity)) + } else { + updated.GrossProfit = 0 + } + + optimized = append(optimized, updated) + + if cargo >= ship.Cargo || capital >= MaxCapital { + break + } + } + return optimized +} + +func calculatePeakCapital(locationIDs []int, trades []Trade, shipCost float64) float64 { + if len(trades) == 0 { + return shipCost + } + + remainingLocs := make(map[int]bool) + for _, l := range locationIDs { + remainingLocs[l] = true + } + + committed := shipCost + for _, t := range trades { + if !remainingLocs[t.FromStation] { + committed += t.FromPrice * float64(t.Quantity) + } + } + + peak := committed + for _, loc := range locationIDs { + // sell + for _, t := range trades { + if t.ToStation == loc { + committed -= t.FromPrice * float64(t.Quantity) + } + } + committed = maxFloat(shipCost, committed) + + // buy + for _, t := range trades { + if t.FromStation == loc { + committed += t.FromPrice * float64(t.Quantity) + } + } + peak = maxFloat(peak, committed) + } + + return peak +} + +func buildRouteInfo(locationIDs []int, trades []Trade, ship Ship, time, risk float64) *RouteInfo { + if len(trades) == 0 { + return nil + } + + capital := calculatePeakCapital(locationIDs, trades, ship.ShipCost) + + var gross float64 + for _, t := range trades { + gross += t.GrossProfit + } + + net := gross - risk*capital + rate := 0.0 + if time > 0 { + rate = net / time + } + + return &RouteInfo{ + ProfitRate: rate, + Risk: risk, + Capital: capital, + TransportTime: time, + GrossProfit: gross, + NetProfit: net, + } +} + +func RouteOptimizer(trades []Trade, graph *Graph, ship Ship, legMetrics map[[2]int]*LegMetrics) *RoutePlan { + if len(trades) == 0 { + return &RoutePlan{Route: []RouteStep{}, OptimizedTrades: []Trade{}, Path: []int{}, RawOffsets: []int{}} + } + + rankedTriplets := buildRankedTriplets(trades, ship.Location) + tradesByPair := buildStationPairIndex(trades) + + if legMetrics == nil { + legMetrics = BuildTradeLegMetrics(graph, ship.Location, trades) + } + + var bestRate float64 + var bestInfo *RouteInfo + var bestStations []int + var bestTrades []Trade + + limit := MaxTradesToConsider + if len(rankedTriplets) < limit { + limit = len(rankedTriplets) + } + + for _, trip := range rankedTriplets[:limit] { + optimized := selectTrades(trip, tradesByPair, ship) + if len(optimized) == 0 { + continue + } + + sLeg, sOk := legMetrics[[2]int{trip[0], trip[1]}] + dLeg, dOk := legMetrics[[2]int{trip[1], trip[2]}] + if !sOk || !dOk || sLeg == nil || dLeg == nil { + continue + } + + risk := sLeg.Risk + dLeg.Risk + time := sLeg.Time + dLeg.Time + + locs := []int{trip[0], trip[1], trip[2]} + info := buildRouteInfo(locs, optimized, ship, time, risk) + if info == nil { + continue + } + + if info.ProfitRate > bestRate { + bestRate = info.ProfitRate + bestInfo = info + bestStations = locs + bestTrades = optimized + log.Printf("New best profit rate: %.2f/hr", bestRate*3600) + } + } + + if bestStations == nil || bestTrades == nil { + return &RoutePlan{Route: []RouteStep{}, OptimizedTrades: []Trade{}, Path: []int{}, RawOffsets: []int{}} + } + + // Reconstruct path + sRes := graph.ShortestPath(bestStations[0], bestStations[1]) + dRes := graph.ShortestPath(bestStations[1], bestStations[2]) + + var path []int + if len(sRes) > 0 { + path = append(path, sRes[:len(sRes)-1]...) + path = append(path, dRes...) + } else { + // fallback + path = append(path, dRes...) + } + + // Formatted route (this needs more detailed graph metadata merging, we'll build a simplified version) + formatted, offsets := graph.FormattedRouteWithOffsets(path) + + // Set Actions + actionsRoute := setActions(formatted, bestTrades) + + return &RoutePlan{ + Route: actionsRoute, + Info: bestInfo, + OptimizedTrades: bestTrades, + Path: path, + RawOffsets: offsets, + } +} + +func setActions(route []RouteStep, trades []Trade) []RouteStep { + bought := make(map[int]bool) + for _, t := range trades { + for i := range route { + if t.FromStation == route[i].LocationID { + route[i].Actions = append(route[i].Actions, Action{ + ActionType: "buy", + Item: t.ItemName, + TypeID: t.TypeID, + Quantity: t.Quantity, + Price: t.FromPrice, + }) + bought[t.TypeID] = true + } + + if t.ToStation == route[i].LocationID && bought[t.TypeID] { + route[i].Actions = append(route[i].Actions, Action{ + ActionType: "sell", + Item: t.ItemName, + TypeID: t.TypeID, + Quantity: t.Quantity, + Price: t.ToPrice, + }) + } + } + } + + // Sort actions + for i := range route { + sort.Slice(route[i].Actions, func(a, b int) bool { + al := route[i].Actions[a] + bl := route[i].Actions[b] + if al.ActionType != bl.ActionType { + return al.ActionType == "sell" // sell comes before buy (0 vs 1 in python logic) + } + if al.Item != bl.Item { + return al.Item < bl.Item + } + return al.Price < bl.Price + }) + } + + return route +} -- cgit v1.3