]> git.scottworley.com Git - planeteer/blame - planeteer.go
Make DimensionSizes() more resilient against dimension reordering.
[planeteer] / planeteer.go
CommitLineData
d07f3caa
SW
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
18package main
19
20import "flag"
c45c1bca 21import "fmt"
d07f3caa
SW
22import "json"
23import "os"
c45c1bca
SW
24import "strings"
25
26var start = flag.String("start", "",
27 "The planet to start at")
d07f3caa 28
c45c1bca 29var end = flag.String("end", "",
e9ff66cf 30 "A comma-separated list of acceptable ending planets.")
c45c1bca
SW
31
32var planet_data_file = flag.String("planet_data_file", "planet-data",
d07f3caa
SW
33 "The file to read planet data from")
34
e9ff66cf
SW
35var fuel = flag.Int("fuel", 16, "Reactor units")
36
37var hold = flag.Int("hold", 300, "Size of your cargo hold")
c45c1bca
SW
38
39var start_edens = flag.Int("start_edens", 0,
40 "How many Eden Warp Units are you starting with?")
41
42var end_edens = flag.Int("end_edens", 0,
43 "How many Eden Warp Units would you like to keep (not use)?")
44
45var cloak = flag.Bool("cloak", false,
46 "Make sure to end with a Device of Cloaking")
47
e9ff66cf 48var drones = flag.Int("drones", 0, "Buy this many Fighter Drones")
c45c1bca 49
e9ff66cf 50var batteries = flag.Int("batteries", 0, "Buy this many Shield Batterys")
c45c1bca
SW
51
52var visit_string = flag.String("visit", "",
53 "A comma-separated list of planets to make sure to visit")
54
55func visit() []string {
56 return strings.Split(*visit_string, ",")
57}
58
9b3b3d9a 59type Commodity struct {
9b3b3d9a
SW
60 BasePrice int
61 CanSell bool
62 Limit int
63}
12bc2cd7 64type Planet struct {
12bc2cd7
SW
65 BeaconOn bool
66 /* Use relative prices rather than absolute prices because you
67 can get relative prices without traveling to each planet. */
0e94bdac 68 RelativePrices map[string]int
12bc2cd7 69}
d07f3caa 70type planet_data struct {
0e94bdac
SW
71 Commodities map[string]Commodity
72 Planets map[string]Planet
73 pi, ci map[string]int // Generated; not read from file
d07f3caa
SW
74}
75
76func ReadData() (data planet_data) {
c45c1bca 77 f, err := os.Open(*planet_data_file)
d07f3caa
SW
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
c45c1bca
SW
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:
110const (
e9ff66cf 111 // Name Num Size Description
0e94bdac
SW
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
c45c1bca
SW
121
122 NumDimensions
123)
124
125func bint(b bool) int {
0e94bdac
SW
126 if b {
127 return 1
128 }
c45c1bca
SW
129 return 0
130}
131
132func DimensionSizes(data planet_data) []int {
133 eden_capacity := data.Commodities["Eden Warp Units"].Limit
134 cloak_capacity := bint(*cloak)
64d87250
SW
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()))
c45c1bca
SW
145 return dims
146}
147
148func StateTableSize(dims []int) int {
149 sum := 0
150 for _, size := range dims {
151 sum += size
152 }
153 return sum
154}
155
156type State struct {
157 funds, from int
158}
159
160func NewStateTable(dims []int) []State {
161 return make([]State, StateTableSize(dims))
162}
163
164func EncodeIndex(dims, addr []int) int {
165 index := addr[0]
166 for i := 1; i < len(dims); i++ {
0e94bdac 167 index = index*dims[i] + addr[i]
c45c1bca
SW
168 }
169 return index
170}
171
172func 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
5f1a50e1
SW
182/* What is the value of hauling 'commodity' from 'from' to 'to'?
183 * Take into account the available funds and the available cargo space. */
184func TradeValue(data planet_data,
0e94bdac
SW
185from, to Planet,
186commodity string,
187initial_funds, max_quantity int) int {
5f1a50e1 188 if !data.Commodities[commodity].CanSell {
5a1593ab
SW
189 return 0
190 }
5f1a50e1 191 from_relative_price, from_available := from.RelativePrices[commodity]
5a1593ab
SW
192 if !from_available {
193 return 0
194 }
5f1a50e1 195 to_relative_price, to_available := to.RelativePrices[commodity]
5a1593ab
SW
196 if !to_available {
197 return 0
198 }
199
5f1a50e1
SW
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
5a1593ab
SW
203 buy_price := from_absolute_price
204 sell_price := int(float64(to_absolute_price) * 0.9)
5f1a50e1
SW
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
5a1593ab
SW
211}
212
5f1a50e1 213func FindBestTrades(data planet_data) [][]string {
c45c1bca 214 // TODO: We can't cache this because this can change based on available funds.
5f1a50e1 215 best := make([][]string, len(data.Planets))
c45c1bca
SW
216 for from := range data.Planets {
217 best[data.pi[from]] = make([]string, len(data.Planets))
218 for to := range data.Planets {
5a1593ab 219 best_gain := 0
c45c1bca
SW
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
5f1a50e1
SW
223 }
224 for commodity := range price_list {
225 gain := TradeValue(data,
0e94bdac
SW
226 data.Planets[from],
227 data.Planets[to],
228 commodity,
229 10000000,
230 1)
5a1593ab 231 if gain > best_gain {
c45c1bca 232 best[data.pi[from]][data.pi[to]] = commodity
5a1593ab
SW
233 gain = best_gain
234 }
235 }
236 }
237 }
238 return best
239}
240
c45c1bca 241// (Example of a use case for generics in Go)
0e94bdac
SW
242func IndexPlanets(m *map[string]Planet) map[string]int {
243 index := make(map[string]int, len(*m))
c45c1bca
SW
244 i := 0
245 for e := range *m {
246 index[e] = i
247 i++
248 }
249 return index
250}
0e94bdac
SW
251func IndexCommodities(m *map[string]Commodity) map[string]int {
252 index := make(map[string]int, len(*m))
c45c1bca
SW
253 i := 0
254 for e := range *m {
255 index[e] = i
256 i++
257 }
258 return index
259}
260
d07f3caa
SW
261func main() {
262 flag.Parse()
263 data := ReadData()
c45c1bca
SW
264 data.pi = IndexPlanets(&data.Planets)
265 data.ci = IndexCommodities(&data.Commodities)
266 dims := DimensionSizes(data)
267 table := NewStateTable(dims)
0e94bdac 268 table[0] = State{1, 1}
5a1593ab 269 best_trades := FindBestTrades(data)
c45c1bca
SW
270
271 for from := range data.Planets {
272 for to := range data.Planets {
5a1593ab 273 best_trade := "(nothing)"
c45c1bca
SW
274 if best_trades[data.pi[from]][data.pi[to]] != "" {
275 best_trade = best_trades[data.pi[from]][data.pi[to]]
5a1593ab 276 }
c45c1bca 277 fmt.Printf("%s to %s: %s\n", from, to, best_trade)
5a1593ab
SW
278 }
279 }
d07f3caa 280}