/
multifill.go
219 lines (194 loc) · 5.62 KB
/
multifill.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
package randomizer
import (
"container/list"
"math/rand"
"sort"
"strings"
)
// a route struct with additional information for multiworld shuffle
type multiRoute struct {
ri *routeInfo
local map[*node]bool
checks map[*node]*node
}
// returns true iff a given slot/item can be multiworld shuffled
func isMultiEligible(mr *multiRoute, slot, item *node) bool {
return !mr.local[slot] && !strings.Contains(item.name, " ring") &&
!strings.HasSuffix(item.name, "small key") &&
!strings.HasSuffix(item.name, "boss key") &&
!strings.HasSuffix(item.name, "dungeon map") &&
!strings.HasSuffix(item.name, "compass") &&
item.name != "slate"
}
// picks a random multiworld-eligible check from a route
func randomMultiCheck(src *rand.Rand, mr *multiRoute) (*node, *node) {
i, slots := 0, make([]*node, 0, len(mr.checks))
for slot, item := range mr.checks {
if isMultiEligible(mr, slot, item) {
slots = append(slots, slot)
i++
}
}
sort.Slice(slots, func(i, j int) bool {
return slots[i].name < slots[j].name
})
slot := slots[src.Intn(len(slots))]
return slot, mr.checks[slot]
}
func shuffleMultiworld(
ris []*routeInfo, roms []*romState, verbose bool, logf logFunc) {
mrs := make([]*multiRoute, len(ris))
src := ris[0].src
swapCounts := make(map[*node]int)
swaps := 0
for i, ri := range ris {
// mark graph nodes as belonging to each player
for _, v := range ri.graph {
v.player = i + 1
}
// accumulate checks in a sane way
mrs[i] = &multiRoute{
ri: ri,
checks: getChecks(ri.usedItems, ri.usedSlots),
local: make(map[*node]bool, ri.usedItems.Len()),
}
for slot, item := range mrs[i].checks {
mrs[i].local[slot] = roms[i].itemSlots[slot.name].localOnly
if isMultiEligible(mrs[i], slot, item) {
swapCounts[slot] = 0
}
}
}
// swap some random items ???
consecutiveMisses := 0
for consecutiveMisses < 1000 {
slot1, item1 := randomMultiCheck(src, mrs[src.Intn(len(mrs))])
slot2, item2 := randomMultiCheck(src, mrs[src.Intn(len(mrs))])
// skip if slots are from the same player, or either of the treasures
// aren't present in the other game, or the swapped treasures don't fit
// in their new slots
if slot1.player == slot2.player ||
roms[slot1.player-1].treasures[item2.name] == nil ||
roms[slot2.player-1].treasures[item1.name] == nil ||
!itemFitsInSlot(item2, slot1) ||
!itemFitsInSlot(item1, slot2) {
continue
}
// only bother making swaps where at least one slot has yet to swap.
// this is also used as a metric to determine when we've probably
// reached about the maximum number of possible swaps
if swapCounts[slot1] != 0 && swapCounts[slot2] != 0 {
consecutiveMisses++
continue
}
consecutiveMisses = 0
if verbose {
logf("swapping {p%d %s <- p%d %s} with {p%d %s <- p%d %s}",
slot1.player, slot1.name, item1.player, item1.name,
slot2.player, slot2.name, item2.player, item2.name)
}
// swap parents
item1.removeParent(slot1)
item2.removeParent(slot2)
item1.addParent(slot2)
item2.addParent(slot1)
// test whether seeds are still beatable w/ item placement
success := true
for _, ri := range ris {
ri.graph.reset()
}
for _, ri := range ris {
ri.graph["start"].explore()
}
for _, ri := range ris {
if !ri.graph["done"].reached {
success = false
break
}
}
// make sure no player has to wait too long on progression from another
mrs[slot1.player-1].checks[slot1] = item2
mrs[slot2.player-1].checks[slot2] = item1
for i, ri := range ris {
ri.usedItems, ri.usedSlots = list.New(), list.New()
for slot, item := range mrs[i].checks {
ri.usedItems.PushBack(item)
ri.usedSlots.PushBack(slot)
}
}
mrs[slot1.player-1].checks[slot1] = item1
mrs[slot2.player-1].checks[slot2] = item2
if playerHasConsecutiveEmptySpheres(ris, 2) {
success = false
}
// update check maps
if success {
mrs[slot1.player-1].checks[slot1] = item2
mrs[slot2.player-1].checks[slot2] = item1
swaps++
swapCounts[slot1]++
swapCounts[slot2]++
} else {
item1.removeParent(slot2)
item2.removeParent(slot1)
item1.addParent(slot1)
item2.addParent(slot2)
if verbose {
logf("route no longer viable")
}
}
}
if verbose {
logf("made %d successful swaps", swaps)
}
// reconstruct used item and slot lists
for i, ri := range ris {
ri.usedItems, ri.usedSlots = list.New(), list.New()
for slot, item := range mrs[i].checks {
ri.usedItems.PushBack(item)
ri.usedSlots.PushBack(slot)
roms[i].itemSlots[slot.name].player = byte(item.player)
}
}
}
// returns true iff any of the players have >= limit empty spheres *before*
// they're finished.
func playerHasConsecutiveEmptySpheres(routes []*routeInfo, limit int) bool {
g, _, spheres, _ := getAllSpheres(routes)
// clean up getAllSpheres master graph
for _, ri := range routes {
ri.graph["start"].removeParent(g["start"])
g["done"].removeParent(ri.graph["done"])
}
// figure out what the final sphere for each player is
finalSpheres := make([]int, len(routes))
for i, sphere := range spheres {
for _, check := range sphere {
if i > finalSpheres[check.player-1] {
finalSpheres[check.player-1] = i
}
}
}
// number of consecutive empty spheres a player has had
drought := make([]int, len(routes))
// check whether any player has an empty sphere before their final one
for i, sphere := range spheres {
playerLoop:
for j, route := range routes {
if i > finalSpheres[j] {
continue
}
for _, node := range sphere {
if route.slots[node.name] == node {
drought[j] = 0
continue playerLoop
}
}
drought[j]++
if drought[j] >= limit {
return true
}
}
}
return false
}