]> git.scottworley.com Git - planeteer/blob - planeteer.go
5acf98fd87b3179ec9e1638c7096052f6229dbef
[planeteer] / planeteer.go
1 /* Planeteer: Give trade route advice for Planets: The Exploration of Space
2 * Copyright (C) 2011 Scott Worley <sworley@chkno.net>
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU Affero General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Affero General Public License for more details.
13 *
14 * You should have received a copy of the GNU Affero General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 package main
19
20 import "flag"
21 import "fmt"
22 import "json"
23 import "os"
24 import "strings"
25
26 var start = flag.String("start", "",
27 "The planet to start at")
28
29 var end = flag.String("end", "",
30 "A comma-separated list of acceptable ending planets.")
31
32 var planet_data_file = flag.String("planet_data_file", "planet-data",
33 "The file to read planet data from")
34
35 var fuel = flag.Int("fuel", 16, "Reactor units")
36
37 var hold = flag.Int("hold", 300, "Size of your cargo hold")
38
39 var start_edens = flag.Int("start_edens", 0,
40 "How many Eden Warp Units are you starting with?")
41
42 var end_edens = flag.Int("end_edens", 0,
43 "How many Eden Warp Units would you like to keep (not use)?")
44
45 var cloak = flag.Bool("cloak", false,
46 "Make sure to end with a Device of Cloaking")
47
48 var drones = flag.Int("drones", 0, "Buy this many Fighter Drones")
49
50 var batteries = flag.Int("batteries", 0, "Buy this many Shield Batterys")
51
52 var visit_string = flag.String("visit", "",
53 "A comma-separated list of planets to make sure to visit")
54
55 func visit() []string {
56 return strings.Split(*visit_string, ",")
57 }
58
59 type Commodity struct {
60 BasePrice int
61 CanSell bool
62 Limit int
63 }
64 type Planet struct {
65 BeaconOn bool
66 /* Use relative prices rather than absolute prices because you
67 can get relative prices without traveling to each planet. */
68 RelativePrices map[string]int
69 }
70 type planet_data struct {
71 Commodities map[string]Commodity
72 Planets map[string]Planet
73 pi, ci map[string]int // Generated; not read from file
74 }
75
76 func ReadData() (data planet_data) {
77 f, err := os.Open(*planet_data_file)
78 if err != nil {
79 panic(err)
80 }
81 defer f.Close()
82 err = json.NewDecoder(f).Decode(&data)
83 if err != nil {
84 panic(err)
85 }
86 return
87 }
88
89 /* This program operates by filling in a state table representing the best
90 * possible trips you could make; the ones that makes you the most money.
91 * This is feasible because we don't look at all the possible trips.
92 * We define a list of things that are germane to this game and then only
93 * consider the best outcome in each possible game state.
94 *
95 * Each cell in the table represents a state in the game. In each cell,
96 * we track two things: 1. the most money you could possibly have while in
97 * that state and 2. one possible way to get into that state with that
98 * amount of money.
99 *
100 * A basic analysis can be done with a two-dimensional table: location and
101 * fuel. planeteer-1.0 used this two-dimensional table. This version
102 * adds features mostly by adding dimensions to this table.
103 *
104 * Note that the sizes of each dimension are data driven. Many dimensions
105 * collapse to one possible value (ie, disappear) if the corresponding
106 * feature is not enabled.
107 */
108
109 // The official list of dimensions:
110 const (
111 // Name Num Size Description
112 Edens = iota // 1 3 # of Eden warp units (0 - 2 typically)
113 Cloaks // 2 2 # of Devices of Cloaking (0 or 1)
114 UnusedCargo // 3 4 # of unused cargo spaces (0 - 3 typically)
115 Fuel // 4 17 Reactor power left (0 - 16)
116 Location // 5 26 Location (which planet)
117 Hold // 6 15 Cargo bay contents (a *Commodity or nil)
118 NeedFighters // 7 2 Errand: Buy fighter drones (needed or not)
119 NeedShields // 8 2 Errand: Buy shield batteries (needed or not)
120 Visit // 9 2**N Visit: Stop by these N planets in the route
121
122 NumDimensions
123 )
124
125 func bint(b bool) int {
126 if b {
127 return 1
128 }
129 return 0
130 }
131
132 func DimensionSizes(data planet_data) []int {
133 eden_capacity := data.Commodities["Eden Warp Units"].Limit
134 cloak_capacity := bint(*cloak)
135 dims := make([]int, NumDimensions)
136 dims[Edens] = eden_capacity + 1
137 dims[Cloaks] = cloak_capacity + 1
138 dims[UnusedCargo] = eden_capacity + cloak_capacity + 1
139 dims[Fuel] = *fuel + 1
140 dims[Location] = len(data.Planets)
141 dims[Hold] = len(data.Commodities)
142 dims[NeedFighters] = bint(*drones > 0) + 1
143 dims[NeedShields] = bint(*batteries > 0) + 1
144 dims[Visit] = 1 << uint(len(visit()))
145 return dims
146 }
147
148 func StateTableSize(dims []int) int {
149 sum := 0
150 for _, size := range dims {
151 sum += size
152 }
153 return sum
154 }
155
156 type State struct {
157 funds, from int
158 }
159
160 func NewStateTable(dims []int) []State {
161 return make([]State, StateTableSize(dims))
162 }
163
164 func EncodeIndex(dims, addr []int) int {
165 index := addr[0]
166 for i := 1; i < len(dims); i++ {
167 index = index*dims[i] + addr[i]
168 }
169 return index
170 }
171
172 func DecodeIndex(dims []int, index int) []int {
173 addr := make([]int, len(dims))
174 for i := len(dims) - 1; i > 0; i-- {
175 addr[i] = index % dims[i]
176 index /= dims[i]
177 }
178 addr[0] = index
179 return addr
180 }
181
182 /* What is the value of hauling 'commodity' from 'from' to 'to'?
183 * Take into account the available funds and the available cargo space. */
184 func TradeValue(data planet_data,
185 from, to Planet,
186 commodity string,
187 initial_funds, max_quantity int) int {
188 if !data.Commodities[commodity].CanSell {
189 return 0
190 }
191 from_relative_price, from_available := from.RelativePrices[commodity]
192 if !from_available {
193 return 0
194 }
195 to_relative_price, to_available := to.RelativePrices[commodity]
196 if !to_available {
197 return 0
198 }
199
200 base_price := data.Commodities[commodity].BasePrice
201 from_absolute_price := from_relative_price * base_price
202 to_absolute_price := to_relative_price * base_price
203 buy_price := from_absolute_price
204 sell_price := int(float64(to_absolute_price) * 0.9)
205 var can_afford int = initial_funds / buy_price
206 quantity := can_afford
207 if quantity > max_quantity {
208 quantity = max_quantity
209 }
210 return (sell_price - buy_price) * max_quantity
211 }
212
213 func FindBestTrades(data planet_data) [][]string {
214 // TODO: We can't cache this because this can change based on available funds.
215 best := make([][]string, len(data.Planets))
216 for from := range data.Planets {
217 best[data.pi[from]] = make([]string, len(data.Planets))
218 for to := range data.Planets {
219 best_gain := 0
220 price_list := data.Planets[from].RelativePrices
221 if len(data.Planets[to].RelativePrices) < len(data.Planets[from].RelativePrices) {
222 price_list = data.Planets[to].RelativePrices
223 }
224 for commodity := range price_list {
225 gain := TradeValue(data,
226 data.Planets[from],
227 data.Planets[to],
228 commodity,
229 10000000,
230 1)
231 if gain > best_gain {
232 best[data.pi[from]][data.pi[to]] = commodity
233 gain = best_gain
234 }
235 }
236 }
237 }
238 return best
239 }
240
241 // (Example of a use case for generics in Go)
242 func IndexPlanets(m *map[string]Planet) map[string]int {
243 index := make(map[string]int, len(*m))
244 i := 0
245 for e := range *m {
246 index[e] = i
247 i++
248 }
249 return index
250 }
251 func IndexCommodities(m *map[string]Commodity) map[string]int {
252 index := make(map[string]int, len(*m))
253 i := 0
254 for e := range *m {
255 index[e] = i
256 i++
257 }
258 return index
259 }
260
261 func main() {
262 flag.Parse()
263 data := ReadData()
264 data.pi = IndexPlanets(&data.Planets)
265 data.ci = IndexCommodities(&data.Commodities)
266 dims := DimensionSizes(data)
267 table := NewStateTable(dims)
268 table[0] = State{1, 1}
269 best_trades := FindBestTrades(data)
270
271 for from := range data.Planets {
272 for to := range data.Planets {
273 best_trade := "(nothing)"
274 if best_trades[data.pi[from]][data.pi[to]] != "" {
275 best_trade = best_trades[data.pi[from]][data.pi[to]]
276 }
277 fmt.Printf("%s to %s: %s\n", from, to, best_trade)
278 }
279 }
280 }