Cataclysm-dda: Persistent IDs for game objects

[Coolthulhu]

The more I deal with monster-related code, the more obvious it is that a persistent ID system for creatures is mandatory for any sensible behavior to happen. Without it, the creatures can't be remembered, which means that "grab" status has to be a broken hack, creatures (and NPCs) can't remember their targets except by position meaning no "attack this" orders are possible, monsters can't be vehicle passengers and so on.

For items, this means there is a lot of extra code to keep track of items (active items, for example), missions regarding specific items are impossible without hacks, persistent (more than one "moment" - less than a single move) multi-item interactions are impossible without turning the items into one or relying solely on their types, and it is impossible for creatures to address items - for example, grappling with player's helmet to pull it off (except doing it all in one move).

Vehicles wouldn't benefit much, but we could still have creatures actually aggro on turreted vehicles if we had IDs here.

So, what does an ID system NEED to work?

• Is long long good enough or do we need something like generated UUID or bigint?
• Do they need to be persistent across "sessions" or is it fine if the IDs are reality-bubble only?
• What should happen when ID conflict arises due to save corruption or bugs?

Previous attempts:

• Monsters #15682
• Items #16791

[mutability]

Vehicle-related actions would benefit from having a vehicle ID, currently they do horrible stuff with stashing the vehicle position and assuming it's still there later.

[saneman226]

Let's take a character in a world surrounded by zombies, and one grabbed onto you before you save and quit. When you reload that save, all of those zombies will be in the same location, as soon as the first tick happens, all of those zombies will regain the exact status they had before. This is because each zombie calculates who they want to go after on a turn-by-turn basis. The grab can simply be a status saying that the zombie has "grabbed" whatever tile around them (similar to the way that the engine determines if a player was in a vehicle when they saved). This portion is completely fine and doesn't need any fixing in the area you are talking about.

Now addressing the multi-item interactions, this is most definitely possible (given they are done on different ticks). I can't think of any reason to require multiple items to be moved on the same tick. From what I gather from what you said, this is similar to the way the player moves large quantities of items from one spot to another, using ticks.

Creatures addressing items can also be done since you know that they can't interact with anything farther than 1 tile away. The creature just has to check the area around them to determine what to do with their environment (say pick something up). If the creature is within range of the player, the creature already has the ability to "pickup" items from the player, but the player will obviously resist that action. Now for your example of grabbing the players helmet, this can be done the same way that the players "resumes" a task they were previously doing. Make the zombie require 450 ticks of the "task" to remove the helmet, and if the "task" is broken (similar to the player stopping their own "task"), then the tick counter can be reset or be made to resume.

For vehicles, the zombies should aggro on anything damaging them that they can see. I haven't tested this but it should work so that the zombie tries to break the portion of the vehicle containing the turret.

Overall, I don't see any real benefit or feature that would be added by having an ID associated with everything.

[Coolthulhu]

This portion is completely fine and doesn't need any fixing in the area you are talking about.

All nearby zombies automatically grab you when one does. You break all those grabs at once. A zombie that grabs the player is unaffected - the grab only affects the player. A single zombie can grab as many targets as there are free adjacent spots.

Grab only superficially looks like it is working.

Overall, I don't see any real benefit or feature that would be added by having an ID associated with everything.

I explicitly listed some. NPCs keeping their targets for one - a hack that would handle it without IDs would be utterly horrible.

I haven't tested this but it should work so that the zombie tries to break the portion of the vehicle containing the turret.

Unless the vehicle moves, in which case the zombie - that only reacts to sound - will go to its former position.

[mutability]

I played around a little with vehicles IDs, which have a much simpler set of requirements than items/creatures.

It seems sufficient there to just use a "long"; the scheme I used for assigning IDs and avoiding save corruption was:

• assign IDs sequentially
• store the next-to-be-allocated ID at the top level of the savefile, restore on load
• when loading, validate each ID: it must be less than the saved "next ID"; if not, debugmsg() and assign a brand new ID
• after loading is done, set the next ID to max(next ID, system-clock-derived counter)

The only place that needed to use vehicle IDs initially was the activity serialization for vehicle interaction, which is infrequent enough that you can just brute-force scan all vehicles in the reality bubble when needed. If more frequent access was required then something along the lines of weak_ptr would work (have a refcounted control block that holds the pointer to the real object, have the real object invalidate that pointer when it is destroyed, everything that wants long-lived access holds a reference to the control block and falls back to looking up by ID if it has no CB reference or if the CB pointer was invalidated)

[saneman226]

The zombies grabbing in more then one location is easily fixed by an "isGrabbing" bool.

As for the npcs not keeping their target, I already stated that a single tick later they would regain that attraction. It would be silly to make a variable to keep unneeded information.

As for the vehicles, the zombie will go to the cause of the noise, and since this game is turnbased, you will never be able to relisticly get the zombie to follow the car perfectly.

So I still dont see any real reason why making the save file larger is a good idea.

[mugling]

So I still dont see any real reason why making the save file larger is a good idea.

A whole series of byzantine hacks to save a tiny amount of space is insanity

[mugling]

I played around a little with vehicles IDs, which have a much simpler set of requirements than items/creatures.

The same system for all objects would be preferable for consistency

[mutability]

I don't know why it would be useful for vehicle IDs and monster IDs to be interchangable. They can certainly share some infrastructure.

[mutability]

Saying that the code should have been implemented a different way in the past is not very useful; it is what it is, now let's fix it.

[Coolthulhu]

The zombies grabbing in more then one location is easily fixed by an "isGrabbing" bool.

Hacked around*
It doesn't work with multiple grab targets - one grabbing zombie could grab 3 NPCs and the player at once.
It would require more hacking around to find who is the zombie grappling, meaning abilities like "grapples well (grappling zombies -20% speed)" would be ugly and hard to maintain code.
Plus, it prevents any more serious implementation of grappling.

The time it takes to process something as small as this would save so much space for all the IDs you plan to create. I can only see most of this issue as fixing what already works (and it already works good).

It's not about the time (even though that's wrong too - most of the performance gains in the game come from caches to avoid recalculations), it's about being able to actually refer to things in a sane way.

It is impossible to refer to specific creatures right now.
You can't order a NPC to attack a specific zombie from the crowd, you can't have animals get pissed at specific targets only (cue rampaging moose switching from zombies to player), you can't have creatures remember their targets instead of just attacking the nearest target every time.

What exactly is the purpose of this entire goal if everything can be calculated on the fly and corrected in little time?

That's the whole deal: it can't.

If the game requires that IDs be kept to utilize these features in the first place, how come it wasn't implemented sooner?

Because it isn't easy.

Besides, the grabbing mechanic should never have had this major of a bug in the first place.

There are two sane ways to fix this: removing grab or adding IDs.
Grabbing is one of the worst implemented major features in the game.

[mugling]

@saneman226 could you drop out of this thread please. I'm not aware of you having read the code base nor made any contributions to it so arguing with @Coolthulhu and @mutability isn't adding much to the conversation. We do need to work out a system for persistent ID and the purpose of this is to determine the requirements.

@mutability yes, ID's should be typed (monster OR vehicle etc) but should be generated and assigned via the same system. I'm not sure if we need anything more sophisticated than a hash or binary tree? Huge databases function perfectly well using indexes? It's tempting to suggest a BRIN index (see postgres) which would have the advantage that most objects from the same submap would be clustered in the same page of the index

[mutability]

Part of the reason I started with vehicles is that the ID would be so
infrequently looked up initially and the number of vehicles in the bubble
is so small that you don't even need an index, just use map::get_vehicles
and iterate..

I will put together a handle template that does the ID/weakptr stuff and
delegates to a lookup factory for unresolved IDs, it is always a bit easier
to discuss implementation when you have a starting point

[mugling]

it is always a bit easier to discuss implementation when you have a starting point

Agreed. Consider opening a PR and we can discuss actual code. An actual implementation is always more useful than endless discussion especially considering how nasty the current vehicle hacks are

[Coolthulhu]

It seems like the game would require saving unnecessary IDs when we could just attach the pointer of the object the zombie is looking at.

Pointers change all the time and operating on invalid pointer is an instant crash.

[mugling]

@mugling The reason I'm commenting is to gain knowledge on the subject,

You need to lurk for some time and read the code base before you try and participate in such discussions. Otherwise the developers consume time replying to you as opposed to dealing with the issue at hand. If you need the concept of pointers explaining to you by @Coolthulhu then your not yet qualified to have an opinion

Pointers change all the time and operating on invalid pointer is an instant crash.

Pedantic: Only if your lucky :smile:

[kevingranade]

Ideally use an existing uuid/guid generator, this is very hard to get
right, and the benefits of e.g. a slightly smaller representation isn't
worth spending time debugging a custom system. this might turn out to be
impractical due to the fact that most uuid generators are tightly coupled
to the OS. If we do end up with a custom solution it either needs to be
guid based (computer identity plus timestamp plus program counter) or
namespaced by world and game session.

Don't attach uuids to every instance of an entity, attach them to establish
an association such as 'ignored', 'grabbed/grabbing' etc. This makes
relationships explicit and eliminates any potential save bloat issue.

Don't make a 'smart uuid' class, just make a simple wrapper to handle
construction, serialization and equality checking. uuids should never
mutate.

[mugling]

Ideally use an existing uuid/guid generator, this is very hard to get right,

C++11 atomics?

[kevingranade]

On Dec 3, 2016 12:24 PM, "mugling" [e-mail] wrote:

Ideally use an existing uuid/guid generator, this is very hard to get right,

C++11 atomics?

In process sync is trivial since we aren't multithreaded. What I mean is:

The simplest custom uuid I'd be OK with would be something like:
Version: Probably 4 bits or so, minimum one bit. Bumped if we figure out
we missed something.
Session id: Incremented each time we start a game session, shared by all
game sessions in a given game world. Needs to be big enough to not roll
over ever, probably 16 bits or so.
Entity id: this would increment every time we issue a uuid, and would
likely take the rest of however much we allocate, likely something like 40
bits.

Optional:
World id: big enough to uniquely identify every game world ever, required
to move entities between game world's.
We could have a scheme where if entity id rolls over the game just grabs
another session id, if we did this we'd make session id huge and entity id
just large enough to not roll over constantly.

Why so paranoid? because uuid collision errors would be impossible to
reproduce or debug, so this needs to work right forever.

[mugling]

Multiple concurrent games are impossible according to CAP theorum. Extra complexity in an identifier to try and suppor this isn't a good idea on the basis that we could never succeed. The current already implementation has a lot of bugs and inconsistencies and has minimal to no usage for that reason.

Also UUID's are only a good design where completely different systems are unable to synchronise which isn't the case here. There is no realistic chance that a 64-bit integer could overflow, even in the pathological case. Lets say you played the game continuously for a thousand years - that still provides sufficient space to generate over a billion identifiers per second.

Atomics are ideal as we are ready for multithreading if we later go down that route otherwise we can trivially switch to single-threading if there is a demonstrable performance concern.

[kevingranade]

On Dec 7, 2016 3:44 AM, "mugling" [e-mail] wrote:

Multiple concurrent games are impossible according to CAP theorum.

I don't see how CAP theorem applies here, as no one said anything about
distributing the game over a network. Additionally CAP just states that you
have to make tradeoffs, not that any particular system is impossible.

The extra complexity isn't a good idea on that basis as it's something we could never successfully support. The current implementation has a lot of bugs and inconsistencies which can never be resolved.

Do you mean merging game worlds (which I agree would be prohibitively
complex to support) or concurrent games in the same game world? We
currently support the latter and there is no reason to stop doing so. There
are certainly inconsistencies that arise in this mode, but I'm not aware of
any additional bugs.

Also UUID's are only a good design where completely different systems are unable to synchronise.

This is an absurd statement, the functionality you are asking for is a
uuid, rejecting that as a solution is premature optimization.

There is no realistic chance that a 64-bit integer could overflow, even in the pathological case. Lets say you played the game continuously for a thousand years - that still provides sufficient space to generate over a billion identifiers per second.

Overflow isn't the issue, collisions due to concurrent instances of the
game are the problem.

Atomics are ideal as we are ready for multithreading if we later go down that route otherwise we can trivially switch to single-threading if there is a demonstrable performance concern.

We never want threading in core game code, if you think threading is a
solution for any of our problems you need to learn more about threading.
We certainly aren't going to start sprinkling synchronization statements
throughout the code on the off chance that we might start spawning threads
at some indeterminate point the future.

We, literally you and I, have had this conversation before. if you want
further detail consult
https://github.com/CleverRaven/Cataclysm-DDA/pull/16791 for the most recent
and detailed discussion.

To reiterate, the version/session/id is the minimal acceptable identifier,
and a real system uuid would also suffice.

[mutability]

the version/session/id is the minimal acceptable identifier

What does this give us that a single sequence maintained as part of the top-level save state doesn't?

[mugling]

Additionally CAP just states that you have to make tradeoffs, not that any particular system is impossible.

Yes it states that providing all three guarantees are impossible - citatation

In theoretical computer science, the CAP theorem, also named Brewer's theorem after computer scientist Eric Brewer, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees

Do you mean merging game worlds (which I agree would be prohibitively complex to support) or concurrent games in the same game world? We currently support the latter and there is no reason to stop doing so. There are certainly inconsistencies that arise in this mode

I mean concurrent games and this is your consistency problem with CAP theroum. If user A consumes an item what is user B supposed to do about this. The only solution to this is explicit synchronisation after each and every player action (giving up on partition tolerance).

We, literally you and I, have had this conversation before.

Yes and as I recall you twice said you had an implementation that was nearly ready but nothing ever appeared.

We never want threading in core game code, if you think threading is a solution for any of our problems you need to learn more about threading.

Try and keep the tone civil. There isn't any need for ad hominem attacks.

[kevingranade]

the version/session/id is the minimal acceptable identifier

What does this give us that a single sequence maintained as part of the top-level save state doesn't?

Depending on what you mean by "top-level" either each player save or each
game world save maintains the counter.

If it's the player save, the numbers are subject to collision when there
are multiple game instances concurrently creating ids since they are
iterating over the same range and then writing the results to the game
world state (by serializing it to the map).

If it's the game world save, concurrently executing clients must
synchronize their accesses to this counter, doing so on each I'd creation
would be ridiculous.

The solution then is to have the game instances synchronize on a shared
session id counter and then independently iterate their own id. the
resulting I'd is simply the concatenation of the two.

[mutability]

>

If it's the game world save, concurrently executing clients must
synchronize their accesses to this counter, doing so on each I'd creation
would be ridiculous.

Yes, I mean in the game world save.

Are you saying that concurrently running copies of C:DDA using the same
game world is something that needs to be supported? That seems crazy.

[kevingranade]

On Dec 7, 2016 9:54 AM, "mugling" [e-mail] wrote:

Additionally CAP just states that you have to make tradeoffs, not that any particular system is impossible.
Yes it states that providing all three guarantees are impossible - citatation https://en.wikipedia.org/wiki/CAP_theorem

Yes I know what CAP theorem is thanks. You seem to be taking the position
that we cannot relax C or A, which is odd because that's exactly what we
do. Consistency is violated by having the map state handled by "last writer
wins" and Availability is violated because we only load map data
periodically, so we will not immediately see the effects of a nearby player.

This is the status quo and I frankly outside the scope of the uuid
discussion other than to note that it is a use case we support.

Uuid generation is a special case where CAP is trivially worked around
using either traditional uuid generation or an application aware scheme
like I outlined.

Do you mean merging game worlds (which I agree would be prohibitively complex to support) or concurrent games in the same game world? We currently support the latter and there is no reason to stop doing so. There are certainly inconsistencies that arise in this mode

I mean concurrent games and this is your consistency problem with CAP theroum. If user A consumes an item what is user B supposed to do about this. The only solution to this is explicit synchronisation.

As I outlined above, it is not the only solution nor the one we implement.
In practice both can consume the same item and that's not a big deal.
CAP theorem is triggered by having high latency and or unreliable
communication between instances, we could easily have a solution that
allows an arbitrary amount of concurrency between instances, but it's
undesirable because keeping time progression in sync between instances is
an intractable problem based on the structure of the game. those would
render most further effort around finer grained consistency between
instances moot.

We, literally you and I, have had this conversation before.

Yes and as I recall you twice said you had an implementation that was nearly ready but nothing ever appeared.

Yes that happened, but it doesn't change the requirements of the game. The
status quo is better than a broken global identifier implementation.

We never want threading in core game code, if you think threading is a solution for any of our problems you need to learn more about threading.

Try and keep the tone civil. There isn't any need for ad hominem attacks.

You're right, my bad. I stand by the content but the phrasing is
unnecessarily agressive.

More nuanced argument:
The lowest common denominator systems we support are single core.
My highest priority with respect to performance is keeping the game
playable on lowest common denominator systems.
Multithreading makes single core systems slower.
QED

[mugling]

If it's the game world save, concurrently executing clients must
synchronize their accesses to this counter, doing so on each I'd creation
would be ridiculous.
Yes, I mean in the game world save.

Are you saying that concurrently running copies of C:DDA using the same
game world is something that needs to be supported? That seems crazy.

Yes, I think that is what is being proposed. I think there was even talk previously of using flock and such mechanisms. I don't think we have any realistic chance of supporting that and I'm not aware of anyone playing the game in such a manner. One player per world would allow for a lot of simplification and given the lack of developers could be a helpful reduction in scope.

Multithreading makes single core systems slower.

It does depend. For example currently vehicle::idle is called for every vehicle in existence each tick. This obviously gets slower the more the player explores. Updating vehicles could easily be done in parallel per submap and this would wrap very nicely onto a threadpool without being slower on single core systems.

It's the same problem as dwarf fortress - as the complexity of the simulation continually increases we need to eventually consider how we might parallelize the work

[kevingranade]

On Dec 7, 2016 2:22 PM, "mugling" [e-mail] wrote:

If it's the game world save, concurrently executing clients must synchronize their accesses to this counter, doing so on each I'd creation would be ridiculous.
Yes, I mean in the game world save.

Are you saying that concurrently running copies of C:DDA using the same game world is something that needs to be supported? That seems crazy.

Yes, I think that is what is being proposed. I think there was even talk previously of using flock and such mechanisms. I don't think we have any realistic chance of supporting that and I'm not aware of anyone playing thegame in such a manner.

This is not a proposal, this is a use case that has been supported for
years and used by a large number of players.

Multithreading makes single core systems slower.

It does depend. For example currently vehicle::idle is called for every vehicle in existence each tick. This obviously gets slower the more the player explores. Updating vehicles could easily be done in parallel per submap and this would wrap very nicely onto a threadpool without being slower on single core systems.

This system would be slower on single core systems. I don't know what
makes you think it would be faster. What you're describing also very much
sounds like a bug, why aren't these vehicles being pruned out of the
vehicle list once they leave the reality bubble?

If you want low priority background tasks to eventually process, make a
simple task queue that executes while the game is waiting on player input.
Anything you could safely offload to a separate thread on a single core
system could also be handled by such a system, and it would have no impact
on time to handle an update tick, unlike a multithreaded approach. Also it
suffers from none of the horrible synchronization issues you encounter with
threads.

I was going to do this for map load and save, but it turns out the overhead
of this operation seems to be immeasurably small, so I never got around to
it. When I have time to dust off the hordes code I'll almost certainly be
implementimg something like that.

[mutability]

Sorry, I just have to be absolutely clear about this because it seems so insane:

This is not a proposal, this is a use case that has been supported for
years and used by a large number of players.

We have a large number of players who are running more than one copy of C:DDA at the same time referencing the same world, and this is a setup that we need to support?

So any part of the world data could change under you while running (not over a save/load cycle) and any changes you save might get clobbered (or be clobbered by) the other process at unpredictable times?

How on earth can you support such a thing without direct cooperation between the processes (of which there is currently none)?

I can understand supporting "more than one active character in a single world", so long as only one is actively being played at a time. But not what is described above.

[mugling]

This is not a proposal, this is a use case that has been supported for years and used by a large number of players.

I'm not aware of this. Who is playing more than one character per world simultaneously?

I don't know what makes you think it (threads) would be faster

The simulation is CPU bound and we could exploit more than one core using threads. Most recent (~5 years) cpu's are multicore and pretty much everything in the future is going to be.

How on earth can you support such a thing without direct cooperation between the processes (of which there is currently none)?

CAP theorem does apply if you have multiple nodes (binaries) using the same data (world) and it states the above is impossible without abandoning partition tolerance which would mean implementing explicit synchronisation and locking.

EDIT: I'm not sure we even have locking to prevent concurrent read/write of the same file by different processes let alone any higher level consistency

[kevingranade]

On Dec 7, 2016 4:08 PM, "mugling" [e-mail] wrote:

This is not a proposal, this is a use case that has been supported for
years and used by a large number of players.

I'm not aware of this. Who is playing more than one character per world
simultaneously?

Specifically the use case is one person runs a "shared world" server and
other people log on to that server to play, which can be concurrent. A
number of people have run such servers over the years, to the extent of
writing launch wrappers around the program and embedding access controls in
the game to prevent users from accessing each other's save files or editing
world options.

I don't know what makes you think it (threads) would be faster

The simulation is CPU bound and we could exploit more than one core using
threads. Most recent (~5 years) cpu's are multicore and pretty much
everything in the future is going to be.

I already addressed this, minimum requirements for the game do not include
multicore systems, so we assume a single core system.

[mugling]

Specifically the use case is one person runs a "shared world" server and other people log on to that server to play, which can be concurrent

I share @mutability's concerns that this isn't feasible.

A number of people have run such servers over the years

I'm not aware of any presently existing at all. It sounds more like a feature you'd like to support but not one that is practical given our codebase.

embedding access controls in the game to prevent users from accessing each other's save files or editing world options.

That code doesn't get any testing and is in all probability currently broken. Maintaining such code is difficult in any case. We have so many obvious vulnerabilities and no system for announcing them that encouraging anyone to install such code and offer that as a public service is irresponsible.

I already addressed this, minimum requirements for the game do not include multicore systems, so we assume a single core system.

Which can quite capably run threaded code. A good real world example was the original Apache server.

[mutability]

Things that seem obviously broken in the current code if concurrent processes is a thing now:

• artifacts
• concurrent loading and saving of a submap

(that was from 10 mins of skimming through code; there's likely to be more)

edit: more things:

• anything involving the turn counter (probably broken for sequential play in a single world too) e.g. decay, funnels, crops
• missions

[mugling]

We're going to need to abandon this idea of concurrent games. I'm not aware of any actual real-world usage and @mutability's list is almost certainly non-exhaustive. Even if we somehow found the time to rewrite the entire game core to use synchronization primitives the performance would be horrible. We cannot simply hand-wave away synchronization - it's an absolute requirement for concurrency.

Asides from the infeasability there also aren't any volunteers to write nor maintain such a system.

[Zireael07]

"Shared world" servers have been attempted a couple of times and usually players got bored with them after seeing the usual shenanigans (items disappearing from your base because the other player picked them up, loading your game a week later only to find the town totally looted by the other players etc.)

I think the idea of concurrent games has to be abandoned, yeah.

[kevingranade]

You seem to be either misunderstanding or not listening, this feature
currently exists in the codebase, and I will not accept changes that
intentionally break it, including a naive persistent ID implementation.

[mugling]

You seem to be either misunderstanding or not listening

I have the majority viewpoint here, both in this and previous threads.

this feature currently exists in the codebase

It's broken and used by nobody. To correctly implement it we would need to rewrite the entire game to use synchronization primitives.

and I will not accept changes

Straight up answer (no political bluster): Meritocracy of developers of dictatorship?

[Coolthulhu]

Does the world sharing feature actually work? Has anybody tested it recently?
Or even better: actually used it.

The problems with concurrence already exist in the game. NPCs have their ID system which isn't synchronized, meaning that both static and random NPCs can get duplicate IDs.

this feature currently exists in the codebase, and I will not accept changes that intentionally break it, including a naive persistent ID implementation

You mean you want to keep this feature working at all costs or are just against breaking it without properly obsoleting it first?

The latter is understandable: to not remove the existing implementation would lead to horrible bitrot and mess in the code.

But the former would be trading the future of the game (many features depend on IDs or could get greatly enhanced by them) for a very minor feature almost no one uses. Or even knows about.

[kevingranade]

Straight up answer (no political bluster): Meritocracy of developers of
dictatorship?

Dictatorship, I've never said otherwise.

On Dec 19, 2016 5:38 AM, "Coolthulhu" [e-mail] wrote:

Does the world sharing feature actually work? Has anybody tested it
recently?
Or even better: actually used it.

I've certainly used the degenerate case of it recently by accidentally
opening a second dda and loading a game in an already active game world.
If we had "disabled" this feature, this would have triggered a pointless
load error.

As for what the users are doing, none of us have any real idea, we only get
feedback from a tiny slice of them. All I can say is I've seen people
expressing interest in this feature and reporting use of it sporadically
for years.
Avoiding breaking that use case is easy enough that those anecdotes are
enough justification for me.

The problems with concurrence already exist in the game. NPCs have their ID
system which isn't synchronized, meaning that both static and random NPCs
can get duplicate IDs.

Valid point, I would expect weird mission handling errors to occasionally
occur in shared worlds. Correct uuids would fix this.

this feature currently exists in the codebase, and I will not accept
changes that intentionally break it, including a naive persistent ID
implementation

But the former would be trading the future of the game (many features
depend on IDs or could get greatly enhanced by them) for a very minor
feature almost no one uses. Or even knows about.

Please look at the full context, all I'm insisting on here is a slightly
more general uid with a single point of synchronization between shared
worlds (or a uuid).

[mugling]

Dictatorship, I've never said otherwise.

Whilst this model is practiced in open source it does necessitate that either the dictator writes >50% of the code and/or has consensus with >50% of the active developers. The reasons for this are self-evident and backed by nearly two decades of the histories of various similar projects.

@Coolthulhu, @mutability and myself are all experienced developers who have made significant and sustained contributions to the codebase and the most likely author of any implementation. The consensus here is against concurrency so it would fall to you to provide an implementation (which is unarguably a huge undertaking) or close the issue as WONTFIX.

[kevingranade]

On Dec 19, 2016 10:12 AM, "mugling" [e-mail] wrote:

Dictatorship, I've never said otherwise.

Whilst this model is practiced in open source it does necessitate that
either the dictator writes >50% of the code and/or has consensus with >50%
of the active developers. The reasons for this are self-evident and backed
by nearly two decades of the histories of various similar projects.

That statement gets a huge [citation needed] label, but you don't really
need to bother with sources since it's also irrelevant.

I don't know what you mean by consensus (is that per issue, an approval
rating, something else?), but in reality it boils down to, "can I attract
and keep a critical mass of contributors engaged enough in the project to
stick around".
The ratios don't matter, it's just a large number of "stay vs go" decisions
made by individuals and repeated over time.

If I make terrible technical decisions, contributors will leave, if I'm a
big jerk, contri utors will leave. Also of course events outside my
control will also cause contributors to leave.
My track record over the past ~4 years is mostly one of keeping people
happy with the project.

My 'strategy' for this is to generally be helpful and responsive to the
best of my ability, drive consensus via discussion whenever possible, and
only insist on a particular design/implementation/whatever when I feel that
it has a large impact, such as breaking a feature (uids vs concurrent
games), breaking game mechanics (gun skills for reloading, furniture
modifying crafting distances), making the project support fewer systems
(graphics libraries, multithreading), or breaking the development process
(long-term hard feature freezes, too-large PRs, breaking backwards
compatibility).

These issues do come up though, and when they do my last resort is to say
no to a change. I don't do so lightly, and when I do there is always a
chance that contributors will leave over it, but there are things I simply
can't compromise on.

The consensus here is against concurrency

Based on the discussion as a whole and my understanding of the code, this
consensus seems to be built on a fundamental misunderstanding about how
this concurrency works. I don't know what else I can say to clarify it
though.

so it would fall to you to provide an implementation (which is unarguably
a huge undertaking) or close the issue as WONTFIX.

An implementation of what? The extant support for concurrent games? It
works now. The concurrency aware uid? It's trivial.

I can only assume you're talking about some kind of system that would keep
instances in sync on a turn-by-turn basis, i.e. actual multiplayer, which
is unnecessary and undesirable since the game logic issues around turn
progression are in fact insoluble.

I'm not talking about a system like that, I'm talking about a system where
map state is synchronized by simply writing to the same underlying files.
Other than some very lightweight file locking which already exists, there's
nothing to implement.

[mutability]

@kevingranade: can you explain what is meant to work and what is expected to be broken with concurrent games? Lots of stuff seems to be broken (start with my list above; there is also the obvious "NPCs/vehicles/creatures/items will be duplicated or destroyed fairly arbitrarily") and it is not clear to me whether you consider those bugs or correct behaviour. We at least need to know what is considered a bug before progress is possible. If the current inconsistencies are acceptable, what's the problem with having a persistent ID system that is also inconsistent when maps are shared?

[kevingranade]

artifacts

Probably broken, also horrifically broken in general, this code is so terrible that no one touches it more than absolutely necessary. I'd honestly be fine with it going away. That having been said, addressing the concurrency issues requires synchronization when creating new artifacts, that's it.

concurrent loading and saving of a submap

This is already synchronized, see mapbuffer.cpp:201:
ofstream_wrapper_exclusive fout( filename );
That's all that is required to prevent corruption. Merging map data after concurrent access is another thing entirely but is an acceptable artifact to enable concurrent games at all.

anything involving the turn counter (probably broken for sequential play in a single world too) e.g. decay,
funnels, crops
missions

Yes there are artifacts that occur if you load games with different dates, I'm not aware of a good solution to these other than only allowing a single player to inhabit a world ever. As you note they occur with concurrent play, alternating play, and sequential play. There is no possibility that we'll prevent this kind of play in order to force game worlds to be consistent. The most I can see doing is disabling it as a default option and having a note that enabling it can cause these effects. As sequential play is the norm for a very large number of players, possibly the majority, I really don't anticipate doing even that. Alternating play allows for people to explore scenarios like having a small group of survivors instead of a single one.

[mutability]

[submap saving] is already synchronized

The current locking provides mutual exclusion between writers but does nothing to prevent readers from seeing a partial file as far as I can tell.

edit: and it's a no-op on anything that's not Linux

[kevingranade]

oops, forgot to answer

If the current inconsistencies are acceptable, what's the problem with having a persistent ID system that is also inconsistent when maps are shared?

The difference is the kind of error, current inconsistencies appear as valid but inconsistent data, or at worst as missing data. UID duplication errors would frequently appear as impossible to reproduce crashes.

The current locking provides mutual exclusion between writers but does nothing to prevent readers from seeing a partial file as far as I can tell.

Correct, the locking is incomplete.

[mutability]

UID duplication errors would frequently appear as impossible to reproduce crashes.

That would be a bug. Why would a UID duplication result in a crash?

If the code has to handle UID inconsistencies, then duplication is just another inconsistency. You could, for example, pick the first object in the reality bubble that you find and renumber any others.

[mutability]

note that if we're assigning IDs to anything that is saved in a submap file, then we are going to have to handle ID duplication _anyway_, regardless of how the IDs are first assigned, because map sharing can result in duplicated objects.

[kevingranade]

On Dec 19, 2016 11:18 PM, "Oliver Jowett" [e-mail] wrote:

UID duplication errors would frequently appear as impossible to reproduce
crashes.

That would be a bug. Why would a UID duplication result in a crash?

By bad for imprecise language, I mean collisions not duplication.
Duplication is relatively benign.
Collision means you might attempt to act on an entity that is incompatible
with your operation, and the likelihood of making the operation
consistently robust against that is very low since uid collisions would be
extremely rare.
In short making collisions extremely rare but not impossible makes your
code fragile.

If the code has to handle UID inconsistencies, then duplication is just
another inconsistency. You could, for example, pick the first object in the
reality bubble that you find and renumber any others.

You don't have to do the renumbering if you associate uids with events and
not entities, then the duplicate is just a tiny data leak.

note that if we're assigning IDs to anything that is saved in a submap
file, then we are going to have to handle ID duplication anyway,
regardless of how the IDs are first assigned, because map sharing can
result in duplicated objects.

Again, this implication was my fault, duplications are rather benign,
you're still acting on the intended entity, just not a duplicate of it.

[mutability]

You don't have to do the renumbering if you associate uids with events and not entities, then the duplicate is just a tiny data leak.

I don't understand what you are suggesting, can you explain? Associating UIDs with events (I guess you mean things like "is grabbing") seems very limiting; how would you represent a long-term association that might cross submaps? For example: a "recently attacked by" list for aggression targeting, or two vehicles that are jumpered together.

[mutability]

To summarize your objection to a simple assignment system, if I understand correctly you are concerned by the case where

• map sharing is happening
• two processes happen to assign the same ID to different objects
• there is a bug in code that uses the ID where it does not revalidate the suitability of the object linked to the ID at the point of use; and/or we want to avoid the extra inconsistency that the collision causes.

I question the wisdom of designing around a hypothetical bug in code that doesn't exist yet, but regardless, a simple approach that doesn't require the complexity of a full UUID is to keep the ID counter in a separate file, and lock/read/update/unlock when allocating a new ID. If map sharing becomes a compile-time option (IMO it should) then the atomic update can be a no-op for normal builds.

[kevingranade]

On Dec 20, 2016 11:13 AM, "Oliver Jowett" [e-mail] wrote:

I don't understand what you are suggesting, can you explain? Associating
UIDs with events (I guess you mean things like "is grabbing") seems very
limiting; how would you represent a long-term association that might cross
submaps? For example: a "recently attacked by" list for aggression
targeting, or two vehicles that are jumpered together.

If a monster is grabbing a player, the monster gets a, "is grabbing: uid"
field, and the player gets a, "grabbed by: uid" field. The uids would be
the same. If the player needs to know if it is being grabbed by a monster,
it can call a "is_grabbing (uid)" predicate supplied by the monster and
pass the uid found in its own "grabbed by" field. Similarly you can have
"grab()" and "release()" actions that add and remove these fields.

This does not work for jumpered together vehicles, uids are not helpful for
that use case since you need to maintain the links between the vehicles
continously. Also we already have a working solution for it.

This is limiting, by design. This provides a mechanism for establishing
identity without polluting every game entity with a uid or suggesting that
simply stashing a uid locally is a good idea. In particular i want to
avoid situations where we search based on uid. It also circumvents issues
around cloning entities, obviously only one of the clones would maintain
the original relationship.

To summarize your objection to a simple assignment system, if I understand
correctly you are concerned by the case where

• map sharing is happening
• two processes happen to assign the same ID to different objects
• there is a bug in code that uses the ID where it does not revalidate
  the suitability of the object linked to the ID at the point of use; and/or
  we want to avoid the extra inconsistency that the collision causes.

I question the wisdom of designing around a hypothetical bug in code that
doesn't exist yet,

You outlined the specific failure mode, but it really boils down to, if
you're making an identifier you are going to rely on to be unique, it had
better be actually unique because collisions are going to be produced
chaotically and are nearly impossible to reproduce. In other words a
mostly unique identifier is completely useless.

but regardless, a simple approach that doesn't require the complexity of a
full UUID is to keep the ID counter in a separate file, and
lock/read/update/unlock when allocating a new ID.

Two weeks ago I said:

The simplest custom uuid I'd be OK with would be something like:
Version: Probably 4 bits or so, minimum one bit. Bumped if we figure
out we missed something.
Session id: Incremented each time we start a game session, shared by all
game sessions in a given game world. > Needs to be big enough to not roll
over ever, probably 16 bits or so.
Entity id: this would increment every time we issue a uuid, and would
likely take the rest of however much we allocate, likely something like 40
bits.

I changed my mind since and now I think the session field should have most
of the space and the entity id can be relatively small, down to one byte or
so. The tradeoff is that the smaller the entity id field is, the more
often we have to acquire a new session id.

File i/o around every increment would be horrendous, especially with
locking. Also we must have a versioning field because you cannot migrate to
a new identifier scheme without processing an entire world save.

If map sharing becomes a compile-time option (IMO it should) then the
atomic update can be a no-op for normal builds.

A default off compile option does not exist for all intents and purposes.
Not to mention, excluding clients requires locking too. We support this
use case means we support it in release builds.

[mutability]

OK, I think what I've been designing solves a completely different set of problems to what you see persistent IDs solving. Not much point discussing the design further since we're trying to do different things. I look forward to your implementation.

[AMurkin]

I think DB with transactions is the obvious solution.

[Coolthulhu]

Every time I think about creature AI, it becomes immediately obvious that IDs are necessary for any complex inter-creature behaviors.
The one role that absolutely must be realizable for AI to ever be good is being able to locate a creature of given ID, if one exists within reality bubble.

What would be the simplest implementation that could get in?
Would something like this be enough:

• 64-bit ID
• First 16 bits correspond to ID of the player character who triggered generation (thus ensuring that there is no collision except if someone manages to load same character twice at the same time, which would be a bug anyway)
• The rest is individual critter ID

[kevingranade]

On Feb 16, 2017 11:36 PM, "Coolthulhu" [e-mail] wrote:

Every time I think about creature AI, it becomes immediately obvious that
IDs are necessary for any complex inter-creature behaviors.
The one role that absolutely must be realizable for AI to ever be good is
being able to locate a creature of given ID, if one exists within reality
bubble.

What would be the simplest implementation that could get in?

Still this:
Version: Probably 4 bits or so, minimum one bit. Bumped if we figure out
we missed something.
Session id: Incremented each time we start a game session, shared by all
game sessions in a given game world. Needs to be big enough to not roll
over ever, probably 44bits or so.
Entity id: this would increment every time we issue a uuid, and would
likely take the rest of however much we allocate, likely something like 16
bits.
In case it's not obvious, if entity id runs out, we'd grab a new session id.
The exact numbers don't matter, just the existence of the subfields and
them having sensible sizes. Make the whole thing 128 bit if you like and
use a 64 bit for session, 60 for entity, and 4 for version.

There's no reason to have something so central have a dependency on the
player class, hence the session id instead of a player id.

[Coolthulhu]

Does this mean starting a new game session should immediately save the master.gsav to bump the numbers for all other possible sessions?

[kevingranade]

On Feb 17, 2017 12:06 AM, "Coolthulhu" [e-mail] wrote:

Does this mean starting a new game session should immediately save the
master.gsav to bump the numbers for all other possible sessions?

Ideally it would bump the number in a new file since master.gsav doesn't
need to be synchronized otherwise.

[kolsurma]

Version: Probably 4 bits or so, minimum one bit. Bumped if we figure out
we missed something.
Session id: Incremented each time we start a game session, shared by all
game sessions in a given game world. Needs to be big enough to not roll
over ever, probably 44bits or so.
Entity id: this would increment every time we issue a uuid, and would
likely take the rest of however much we allocate, likely something like 16
bits.
In case it's not obvious, if entity id runs out, we'd grab a new session id.
The exact numbers don't matter, just the existence of the subfields and
them having sensible sizes. Make the whole thing 128 bit if you like and
use a 64 bit for session, 60 for entity, and 4 for version.

oh holy crap, 44 bits for the session ID is extreme. you're talking 17,592,186,044,416, that's 17 trillion, characters PER WORLD before you overflow. If you create a new character every second it would take 557,462 YEARS to fill it. 64 bits for the session is even more crazy. I would be surprised if a world saw more than a few hundred sessions, but even as low as 24 bits you're talking 16 million characters in a single world.

60 bits for the entity would only make sense if you never recycle them (and never make another world, and keep playing till you're 1000. Talk about a world you can hand down to your kids!) For the most part, the only entities we would care about tracking long term are either unique or named creatures.

We shouldn't really care that NPC#1553 killed zombi#999999999 two hundred years ago (in game time) just that it killed x number zombies. Once the entity is permanently dead (pulped or butchered, etc.. ) any tracked ids associated with it could probably be disposed of and reused.

[kevingranade]

I understand your concern, but it's really simple.
32 bits is not enough once you take out a few bits for versioning and
partition the rest. Say you divide like 4 bits version, 20 bits session,
and 8 bits entity. Right at a million sessions might seem like a lot, but
with only 256 entities per session, you're going to eat through multiple
sessions in short order, consuming hundreds to thousands of sessions at a
sitting, at that pace those millions of sessions aren't going to last
long. I want this solution to work even if people change my mind and we
end up applying one of these things to every entity in the game. If we do
that we'll be consuming thousands of uids in mapgen a second when exploring
new areas.

My recommendation is for a 64 bit identifier, this yields sufficient total
identifiers for far beyond the expected lifespan of a game world, which is
what we want. If for some reason Coolthulu prefers a 128 bit identifier, I
was just pointing out I would not oppose it, I'd far prefer to be too
robust rather than too parsimonious with the identifier.

60 bits for the entity would only make sense if you never recycle them
(and never make another world, and keep playing till you're 1000. Talk
about a world you can hand down to your kids!) For the most part, the only
entities we would care about tracking long term are either unique or named
creatures.

We shouldn't really care that NPC#1553 killed zombi#999999999 two hundred
years ago (in game time) just that it killed x number zombies. Once the
entity is permanently dead (pulped or butchered, etc.. ) any tracked ids
associated with it could probably be disposed of and reused.

You don't seem to understand what these identifiers are for. The idea is
you create the numbers in such a way that you never worry about having a
collision, because code to handle revocation is far more complicated and
error prone and expensive than just making the number bigger. Also you can
never assert that you don't care about a particular collision, because you
can never predict what numbers will collide, maybe it's some random thing
you don't care about, but it also might be something that crashes the game
or causes save corruption. You never, ever recycle uids.

[kolsurma]

You don't seem to understand what these identifiers are for. The idea is
you create the numbers in such a way that you never worry about having a
collision, because code to handle revocation is far more complicated and
error prone and expensive than just making the number bigger. Also you can
never assert that you don't care about a particular collision, because you
can never predict what numbers will collide, maybe it's some random thing
you don't care about, but it also might be something that crashes the game
or causes save corruption. You never, ever recycle uids.

Yeah you were right, at the time I had just read your and Coolthulhu's posts and not anything previous to this year. I was reading it like this would be an item reference not a globally unique ID.

Questions:
How will this UID be stored? A new class that all entities now inherit from?

Where will it be accessed from? That is, will this be touching all potential code that deals with entities? If so, it should probably wait till 0.D (assuming 0.D releases relatively soon).

How many entities UIDs should be loaded? The reality bubble, the 9 surrounding overmap tiles, the entire game?

How will this effect savegames? Adding another 128 bits per entity surely isn't going to speed up save/loads, especially on the first load of an old savegame where it has to generate UIDs for all items.

[kevingranade]

On Feb 17, 2017 7:17 PM, "Surma" [e-mail] wrote:

You don't seem to understand what these identifiers are for. The idea is
you create the numbers in such a way that you never worry about having a
collision, because code to handle revocation is far more complicated and
error prone and expensive than just making the number bigger. Also you can
never assert that you don't care about a particular collision, because you
can never predict what numbers will collide, maybe it's some random thing
you don't care about, but it also might be something that crashes the game
or causes save corruption. You never, ever recycle uids.

Yeah you were right, at the time I had just read your and Coolthulhu's
posts and not anything previous to this year. I was reading it like this
would be an item reference not a globally unique ID.

Questions:
How will this UID be stored? A new class that all entities now inherit from?

It's just a big number, there will be new code in charge of creating uids
that other classes call if they need a uid, I very much do not want a uid
added to every entity in the game.

Where will it be accessed from? That is, will this be touching all
potential code that deals with entities? If so, it should probably wait
till 0.D (assuming 0.D releases relatively soon).

No, uids should be created to track specific things, like labelling a
monster as having been ignored by the player recently, or labelling a
creature as having a grab on another creature.

How many entities UIDs should be loaded? The reality bubble, the 9
surrounding overmap tiles, the entire game?

Generally they'd just be a part of other objects and follow the load/save
logic for the object they are a part of.

How will this effect savegames? Adding another 128 bits per entity surely
isn't going to speed up save/loads, especially on the first load of an old
savegame where it has to generate UIDs for all items.

As above, most objects don't get a uid, so impact should be minimal.

[Coolthulhu]

I very much do not want a uid added to every entity in the game.

Adding another 128 bits per entity surely isn't going to speed up save/loads, especially on the first load of an old savegame where it has to generate UIDs for all items.

UID per item, per creature and per vehicle would not significantly increase memory usage, computation time nor save/load time, not even if they were 128 bits.

A NPC is player-sized. Actually bigger than that. UID wouldn't be noticeable here - not in memory nor in saves.

A typical vehicle is made of 30+ items. Rest of the data is an order of magnitude smaller than those items.

A typical item has 9+ int values (most not stored in save), of which two could be dropped if the item had a UID. Then 3 pointers, 2 doubles, 2 vectors, a set and a map. Even if it was densely packed, we're looking at 24*32 bits, so that 4 extra words is just a bit above 10%. That's on 32 bit builds, assuming perfectly small vectors and 128 bit UIDs (in practice it would be less than 5% increase).
Generating a UID for a UID-less object would be just a couple of 64 bit shifts and bit-ops. It will probably be faster than parsing a string with said UID.

The only thing that would actually increase in size is saves. A typical item has just a type ID, birthday, and one field (a tag, note, rot or charges).
It wouldn't be comparable to size of overmaps (those are absolutely giant because monster group syntax is incredibly redundant - 200+ identical groups that only differ in position and population could easily be changed into a list of pairs [position, population] attached to a set of parameters), but it could be noticeable.

It could be optimized by only generating item UIDs on demand. Multi-player access sounds like a problem, but it actually isn't one: an item only exist in one bubble at a time (right? if it wasn't the case, items could be cloned), so the first player who "claims" the item for some UID-requiring purpose should be fine to "name" it.
I can't think of a counterexample here.

[mutability]

an item only exist in one bubble at a time (right?

This is not true if we allow map sharing.

[kevingranade]

I don't oppose uids on every game entity because I'm being parsimonious
with memory, I oppose it because uids are not a good general purpose lookup
method. Uids should be generated on demand when called for, not before,
and certainly not automatically for every entity just in case they are
needed later.

Just to repeat myself, I am not merging a change that adds uids to any of
the core game objects.

[Coolthulhu]

Just to repeat myself, I am not merging a change that adds uids to any of the core game objects.

Wait, so how would they be checked then?
Or do you mean "any" as in "every instance of"?

I oppose it because uids are not a good general purpose lookup method

What are the alternatives and why aren't we using them in the game?
I'd be fine with anything that allows quickly locating any given object and verifying that it is that exact object, just so that I don't need to go through the utterly horrible, untrackable and unmaintainable hacks; trying to locate objects by their physical positions or non-unique characteristics.

[kevingranade]

On Feb 18, 2017 11:16 PM, "Coolthulhu" [e-mail] wrote:

Just to repeat myself, I am not merging a change that adds uids to any of
the core game objects.

Wait, so how would they be checked then?
Or do you mean "any" as in "every instance of"?

I mean "every instance of", what I meant was don't add them to the
definition of the class.

I oppose it because uids are not a good general purpose lookup method

What are the alternatives and why aren't we using them in the game?
I'd be fine with anything that allows quickly locating any given object

This is not what uids are for, we are not adding a gigantic hash map of
every game entity in the reality bubble (maintaining it would easily be
more expensive than the value it to would provide). They're for identity,
not lookup. When an entity needs to be looked up fast, you need to arrange
your data structures to make it fast, not try to force fast lookup with
another handle.

and verifying that it is that exact object

This is what they can do, and it's all we really need.

[Coolthulhu]

I mean "every instance of", what I meant was don't add them to the definition of the class.

Where then? A separate map of id->object?

This is not what uids are for, we are not adding a gigantic hash map of every game entity in the reality bubble (maintaining it would easily be more expensive than the value it to would provide).

Doing it for items could be an overkill, but doing it for creatures would actually SAVE on processing power - possibly significantly so (and certainly would not slow things down).
Inter-creature vision is a significant part of the execution time. By caching the last target, it would not only get more sensible, but also faster.

When an entity needs to be looked up fast, you need to arrange your data structures to make it fast, not try to force fast lookup with another handle.

But we are already doing the latter, just badly: game::mon_at looks up creatures in a position map. So creatures are remembered by their positions, then looked up. This adds a layer of useless storing+mapping while also making it clunky and prone to bugs.

[kevingranade]

On Feb 19, 2017 12:06 AM, "Coolthulhu" [e-mail] wrote:

I mean "every instance of", what I meant was don't add them to the
definition of the class.

Where then? A separate map of id->object?

Add it to the properties map when needed.

This is not what uids are for, we are not adding a gigantic hash map of
every game entity in the reality bubble (maintaining it would easily be
more expensive than the value it to would provide).

Doing it for items could be an overkill, but doing it for creatures would
actually SAVE on processing power - possibly significantly so (and
certainly would not slow things down).

If you have something in mind we can discuss the tradeoffs, but an initial
introduction of uids isn't a great place to do that kind of thing.

More context, when I say please don't add uids to the class definition, I
mean not for the first set of prs, and not in order to support a feature
that doesn't require it like tracking grabs or tracking that the player has
ignored a particular monster.

Inter-creature vision is a significant part of the execution time. By
caching the last target, it would not only get more sensible, but also
faster.

How many lookups a tick is this and how expensive is that lookup? (Gives an
upper bound on performance benefit)

How large is the structure for tracking creatures to allow lookup by uid?
How many updates a tick are required to keep it updated and how expensive
are those updates? (Gives the overhead of trying to optimize the lookup).

Alternative with a uid for id but not lookup: store last seen location and
uid, spiral search with a small radius for a monster with a matching uid.
Simpler code, nearly same lookup speed, no secondary structure to update.

This is the kind of discussion we need to have before adding uids to every
instance of a class by default, but in detail.

When an entity needs to be looked up fast, you need to arrange your data
structures to make it fast, not try to force fast lookup with another
handle.

But we are already doing the latter, just badly: game::mon_at looks up
creatures in a position map. So creatures are remembered by their
positions, then looked up. This adds a layer of useless storing+mapping
while also making it clunky and prone to bugs.

Let me clarify, there's a pattern where you overhaul your entire object
model to make all your objects fit in a global table keyed by uid. This is
the kind of thing I find problematic.

[Coolthulhu]

How many lookups a tick is this and how expensive is that lookup? (Gives an upper bound on performance benefit)

Upper bound would be: number_of_critters * number_of_critters * cost_of( map::sees ).
Creature vision usually only cares about closest target. Since last turn's target is a very good start, we could skip most sight checks that way.
The real benefit would be much smaller than upper bound because the actual number of sight checks per critter would be unlikely to grow faster than ln(number_of_critters), but it would still be noticeable in a big zombie vs ants or zombie vs fungi skirmishes.

How large is the structure for tracking creatures to allow lookup by uid? How many updates a tick are required to keep it updated and how expensive are those updates? (Gives the overhead of trying to optimize the lookup).

Like creature_tracker's position map, except unordered and with uint64/128 keys instead of tripoint. A tiny bit bigger because it would also contain NPCs and player, but also smaller because of smaller keys.
The actual creatures would most likely be stored as pointers, in the same way it is done in the position map (monsters reside in vector, map only holds pointers).
It would not be updated during typical turn. Updates would be required in an event that gives creature an ID, load of creature with an ID, or unload of creature with an ID (including death).

Alternative with a uid for id but not lookup: store last seen location and uid, spiral search with a small radius for a monster with a matching uid.

That would work, but it would be quite an overhead for maintenance - subtle bugs and weird behaviors, especially in 3D movement and teleportation. The performance would also drop quite a bit, since last time I profiled it, all the code that checks multiple adjacent tiles is pretty high in overall CPU usage, even simple stuff like stumbling.

Another alternative would be to create a map of "moved last turn to". That is, map<tripoint,tripoint> cleared on the start of the turn, with value added when creature changes position (position changing is already tracked for purposes of updating position map). It would need to contain only the endpoints, to avoid bugs when critters cross path. If desired, it could be used to implement annoying "bumping" animations like in ToME4.

Still, either of those methods would be more trouble than tracking IDs, while also being less flexible.

Let me clarify, there's a pattern where you overhaul your entire object model to make all your objects fit in a global table keyed by uid. This is the kind of thing I find problematic.

Oh
No, I just wanted a simple way to find an unique object within bubble, if it exists there.
A global table would probably cause problems with "infinite" worlds, so the biggest table I'd consider would be overmap-sized (like for NPCs).