CONSIDER - Track every room a player has visited

[Volte6]

Currently rooms track what players have visited them recently, and this is purged every so often.

The goal of this task is to investigate efficient ways to track every room a player has visited, to enable more sophisticated features that rely on whether players are aware of a room.
Example: Only revealing rooms a player is aware of when mapping.

As room count increases, so does the number of rooms tracked. If we have 10240 rooms that is a minimum of 81kb being stored for a character. Not "end of the world" stuff but feels very wasteful.

Some basic options:

• Track rooms visited in another structure that doesn't get copied around with the character data.
• Compress tracked data with lz4 or similar to minimize memory overhead.
• Track rooms by zone for faster lookup/sharding.
• When every room in a zone is visited, clear the tracked rooms and track a completed boolean.
  • Problematic if new rooms are added after the fact.

[Jasrags]

We could use a bitset to track room visits, using the room's VNUM as the bit index. This could either be a single global bitset or a map of per-zone bitsets to support more localized tracking.

One open question is whether we expect players to eventually “forget” rooms they’ve visited. If so, a bitset may not be ideal.

[Jasrags]

I did some initial research into compression strategies for tracking visited rooms and found the following relevant packages:
bits-and-blooms/bitset
pierrec/lz4

To evaluate feasibility, I ran a simple benchmark on my laptop to measure uncompressed size, compressed size, and duration for LZ4 compression.

All Bits Set

Bitfield Size: 100       | Raw: 34     | Compressed: 49     | Duration: 792µs   | 144.12% (expansion)
Bitfield Size: 1,000     | Raw: 186    | Compressed: 133    | Duration: 4.69ms  | 71.51%
Bitfield Size: 10,000    | Raw: 1,690  | Compressed: 880    | Duration: 1.17ms  | 52.07%
Bitfield Size: 100,000   | Raw: 16,686 | Compressed: 8,221  | Duration: 7.78ms  | 49.27%
Bitfield Size: 1,000,000 | Raw: 166,682| Compressed: 72,792 | Duration: 2.59ms  | 43.68%

Half of the Bits Set

Bitfield Size: 100       | Raw: 34     | Compressed: 49     | Duration: 631µs   | 144.12% (expansion)
Bitfield Size: 1,000     | Raw: 186    | Compressed: 83     | Duration: 4.35ms  | 44.62%
Bitfield Size: 10,000    | Raw: 1,690  | Compressed: 469    | Duration: 672µs   | 27.75%
Bitfield Size: 100,000   | Raw: 16,686 | Compressed: 4,493  | Duration: 4.87ms  | 26.92%
Bitfield Size: 1,000,000 | Raw: 166,682| Compressed: 46,889 | Duration: 8.11ms  | 28.13%

Takeaways
Very small bitfields (like size 100) don’t compress well and even expand in size—this is expected.
At scale, compression results are strong, especially with sparsity—bitfields with only 50% of bits set saw compression down to ~27%.
Compression time is minimal even for large bitfields, making this viable for real-time or on-save scenarios.

If we go this route, I’d suggest supporting a configurable bitfield length with a reasonable default (e.g., per zone or world segment). This would give us flexibility without locking us into a one-size-fits-all structure.

[Volte6]

Not bad - we may be able to even avoid the lzw compression depending on how it's stored. Any idea of that bitset library has any sort of marshalling/encoding default?

There are some caveats here though - a zone may have linear numeric room ID set, but a later addition would blow it out. For example, if you return to a zone and add the 100,000th room to the mud, that zone would now have room #100000, which is problematic in terms of partitioning by zone.

That may be a deal breaker unless a major refactor that limits room ID ranges is put in place, which unless there's much greater justification than room tracking I'm not sure is worth doing.

Lets continue to think on this, though.

Another option is to quantize the room id (VNUM) and partion based on ranges within that, so each bitset range is known, and it can grow organically as new room id's are added or discvoered by the player:

0-999
1000-1999
2000-2999
etc.

No new bitset needs to be created or allocated until at least one room within the range is visited.

[edit]

To clarify - we would offset the discrete bitsets position based on the quantized position - so while all of these have 1000 rooms they track, 2000-2999 would only track 0-999, assumed offset by 2000

[Jasrags]

After doing some reading I agree, the quantized approach combined with offsetting makes a lot of sense.

Simple example

vnum := 2345
offset := 2000 
offsetVnum := vnum - offset

b := bitset.New(uint(1000))
b.Set(uint(offsetVnum))

[Volte6]

Okay we're agreed on that - there's still one more hurdle - How do we know when all rooms in a particular zone are visited by a player?

At the moment, all I can think of is looping through all RoomId's and checking them in the bitset list until we encounter a miss.

Of course once we know they've fully explored a zone we can save a flag for that (recalcluated anew each login, probably)

[Jasrags]

For the all rooms visited issue, if we use "github.com/bits-and-blooms/bitset" that i did my testing with it has a helper function for that.

// All returns true if all bits are set, false otherwise. Returns true for
// empty sets.
func (b *BitSet) All() bool {
	panicIfNull(b)
	return b.Count() == b.length
}

[Volte6]

Bits for a zone may be spread over multiple bitsets, depending on room creation order when building... RoomId (VNUM) is incremented globally, not per-zone.

So we'd need to calculate (probably with a loop) and cache it.

We can probably do a little intelligent caching, such as keeping track of how many rooms in a zone they know about vs. the maximum number of rooms in a zone, and increment it when new rooms are tracked, etc... but it's just something to keep in mind.

[JeremyDOwens]

What if there were a bitmask for a zone?

zoneA := 0b0001111000010
zonesVisited := 0b0001101001010

visitedAllZoneA := zoneA == zoneA & zonesVisited 

[Volte6]

A bitmask works but has limitations - only so many zones can be supported, and they "sort of" have to be known/hard coded (can be worked around with a LUT).

Zone have a fairly limited quantity, so even tracking every zone in a map or array is almost free, but rooms are the tricky part - knowing every room someone visits when there could be a million rooms, and being memory efficient about it is tough.

I think the bitset strategy could work really well, and once a zone is 100%'d we can mark the zone as "complete" and release the memory for individual rooms, assuming we don't care if new rooms are added later.

Or we can just use the chunk based approach and never worry about the memory usage, possibly offloading it to a secondary memory/file structure for as-needed loading.

I think this is a surmountable problem... it's a matter of just getting it started and it'll all fall into place really quickly.

If bitsets are the answer, I think reducing the chunk size to something like 256 vs. 1000 makes more sense.