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
|
package player
import (
"encoding/base64"
"encoding/binary"
"fmt"
"sort"
"strings"
"gopkg.in/yaml.v3"
)
// RoomSet is the set of room IDs a character has visited, used for the map
// discovery view.
//
// It is stored sparsely: room IDs are filename-derived and may be large and
// widely spaced (the shipped example rooms run from 1001 to 99999301), so an
// ID-indexed bitset would grow with the *largest* ID rather than the number of
// visited rooms. A sparse map keeps memory proportional to the visited count,
// and the YAML encoding is a sorted, delta-encoded uvarint blob (see
// MarshalYAML) which is a handful of bytes for a typical character regardless
// of how high the IDs run.
//
// The zero value is a valid empty set. Copies share the underlying map, so a
// RoomSet should not be copied after a concurrent mutation (the game layer only
// touches it on the owner goroutine).
type RoomSet struct {
ids map[int]struct{}
}
// roomSetV1Prefix tags the delta-encoded encoding. The colon is safe inside a
// YAML plain scalar: ':' is only a mapping indicator when followed by a space,
// and ':' is not in the base64 alphabet, so the prefix cannot be confused with
// payload bytes.
const roomSetV1Prefix = "v1:"
// roomSetMaxID bounds decoded room IDs. IDs are filename-derived and fit
// comfortably in an int32; rejecting anything larger keeps a corrupt delta
// blob from synthesizing absurd IDs.
const roomSetMaxID = 1<<31 - 1
func (rs *RoomSet) ensure() {
if rs.ids == nil {
rs.ids = make(map[int]struct{})
}
}
func (rs *RoomSet) Add(roomID int) {
if roomID < 0 {
return
}
rs.ensure()
rs.ids[roomID] = struct{}{}
}
func (rs *RoomSet) Has(roomID int) bool {
if roomID < 0 || rs.ids == nil {
return false
}
_, ok := rs.ids[roomID]
return ok
}
func (rs *RoomSet) Len() int {
if rs.ids == nil {
return 0
}
return len(rs.ids)
}
func (rs RoomSet) IsZero() bool {
return len(rs.ids) == 0
}
// Keys returns the visited room IDs in ascending order.
func (rs *RoomSet) Keys() []int {
if len(rs.ids) == 0 {
return nil
}
keys := make([]int, 0, len(rs.ids))
for id := range rs.ids {
keys = append(keys, id)
}
sort.Ints(keys)
return keys
}
// Rekey remaps every visited room through idMap, leaving unmapped IDs in place.
// It returns the new set and whether any ID changed. The receiver is not
// modified.
func (rs *RoomSet) Rekey(idMap map[int]int) (RoomSet, bool) {
var next RoomSet
changed := false
for id := range rs.ids {
newID, ok := idMap[id]
if !ok {
newID = id
} else if newID != id {
changed = true
}
next.Add(newID)
}
return next, changed
}
func NewRoomSetFrom(ids ...int) RoomSet {
var rs RoomSet
for _, id := range ids {
rs.Add(id)
}
return rs
}
// MarshalYAML emits the current encoding: ascending IDs as delta-encoded
// uvarints, base64-encoded behind the "v1:" tag. IDs come from filenames, so a
// small delta usually costs one byte and the total is O(visited).
func (rs RoomSet) MarshalYAML() (any, error) {
if len(rs.ids) == 0 {
return "", nil
}
keys := rs.Keys()
buf := make([]byte, 0, len(keys)*2)
prev := 0
for _, id := range keys {
buf = binary.AppendUvarint(buf, uint64(id-prev))
prev = id
}
return roomSetV1Prefix + base64.StdEncoding.EncodeToString(buf), nil
}
// UnmarshalYAML accepts only the v1 delta encoding (plus null/empty for the
// zero value). There is deliberately no legacy decoding: the game is a
// prototype and character files are recreated rather than migrated.
func (rs *RoomSet) UnmarshalYAML(value *yaml.Node) error {
rs.ids = nil
if value.Kind == yaml.ScalarNode && (value.Tag == "!!null" || value.Value == "null" || value.Value == "") {
return nil
}
var s string
if err := value.Decode(&s); err != nil {
return err
}
if s == "" {
return nil
}
if !strings.HasPrefix(s, roomSetV1Prefix) {
return fmt.Errorf("rooms_visited: unrecognized encoding, want %q prefix", roomSetV1Prefix)
}
return rs.decodeDelta(s[len(roomSetV1Prefix):])
}
func (rs *RoomSet) decodeDelta(encoded string) error {
raw, err := base64.StdEncoding.DecodeString(encoded)
if err != nil {
return fmt.Errorf("rooms_visited: %w", err)
}
prev := 0
for len(raw) > 0 {
delta, n := binary.Uvarint(raw)
if n <= 0 {
return fmt.Errorf("rooms_visited: corrupt delta encoding")
}
raw = raw[n:]
if delta > roomSetMaxID || prev > roomSetMaxID-int(delta) {
return fmt.Errorf("rooms_visited: room ID out of range")
}
prev += int(delta)
rs.Add(prev)
}
return nil
}
|
