1 files changed, 102 insertions, 40 deletions
diff --git a/internal/player/roomset.go b/internal/player/roomset.go
index 3565bb6..d7e1b47 100644
--- a/internal/player/roomset.go
+++ b/internal/player/roomset.go
@@ -2,75 +2,103 @@ package player
 
 import (
 	"encoding/base64"
-	"math/bits"
+	"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 {
-	bits []byte
+	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
 	}
-	byteIdx := roomID / 8
-	if byteIdx >= len(rs.bits) {
-		nb := make([]byte, byteIdx+1)
-		copy(nb, rs.bits)
-		rs.bits = nb
-	}
-	rs.bits[byteIdx] |= 1 << (roomID % 8)
+	rs.ensure()
+	rs.ids[roomID] = struct{}{}
 }
 
 func (rs *RoomSet) Has(roomID int) bool {
-	if roomID < 0 {
+	if roomID < 0 || rs.ids == nil {
 		return false
 	}
-	byteIdx := roomID / 8
-	return byteIdx < len(rs.bits) && rs.bits[byteIdx]&(1<<(roomID%8)) != 0
+	_, ok := rs.ids[roomID]
+	return ok
 }
 
 func (rs *RoomSet) Len() int {
-	n := 0
-	for _, b := range rs.bits {
-		n += bits.OnesCount8(b)
+	if rs.ids == nil {
+		return 0
 	}
-	return n
+	return len(rs.ids)
 }
 
 func (rs RoomSet) IsZero() bool {
-	return len(rs.bits) == 0
+	return len(rs.ids) == 0
 }
 
+// Keys returns the visited room IDs in ascending order.
 func (rs *RoomSet) Keys() []int {
-	var keys []int
-	for byteIdx, b := range rs.bits {
-		if b == 0 {
-			continue
-		}
-		base := byteIdx * 8
-		for bitIdx := 0; bitIdx < 8; bitIdx++ {
-			if b&(1<<bitIdx) != 0 {
-				keys = append(keys, base+bitIdx)
-			}
-		}
+	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 _, k := range rs.Keys() {
-		newK, ok := idMap[k]
+	for id := range rs.ids {
+		newID, ok := idMap[id]
 		if !ok {
-			newK = k
-		} else if newK != k {
+			newID = id
+		} else if newID != id {
 			changed = true
 		}
-		next.Add(newK)
+		next.Add(newID)
 	}
 	return next, changed
 }
@@ -83,13 +111,29 @@ func NewRoomSetFrom(ids ...int) RoomSet {
 	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) {
-	return base64.StdEncoding.EncodeToString(rs.bits), nil
+	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 {
-	if value.Kind == yaml.ScalarNode && (value.Tag == "!!null" || value.Value == "null") {
-		rs.bits = nil
+	rs.ids = nil
+	if value.Kind == yaml.ScalarNode && (value.Tag == "!!null" || value.Value == "null" || value.Value == "") {
 		return nil
 	}
 	var s string
@@ -97,13 +141,31 @@ func (rs *RoomSet) UnmarshalYAML(value *yaml.Node) error {
 		return err
 	}
 	if s == "" {
-		rs.bits = nil
 		return nil
 	}
-	b, err := base64.StdEncoding.DecodeString(s)
+	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 err
+		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)
 	}
-	rs.bits = b
 	return nil
 }