The infamous 'objects disappearing bug'

Post by **marzo** » Tue Mar 27, 2012 8:38 pm

Given the randomness of schedules, no: the NPC needs to move in just the right way and do just the right actions, at the right time to boot, for it to happen. And it all depends on also moving the avatar in just the right way at the right time. Given that schedule actions aren't preserved during save/load, this adds to the difficulty.

This relatively rare set of circumstances is why the bug is hard to trigger, especially on demand for debugging. It is also why you can return to an earlier save and play through the same portion of the game without triggering it again.

VisElEchNon · Post by **VisElEchNon** » Wed Mar 28, 2012 3:43 pm

Ah, yeah that makes sense then.

paulo · Post by **paulo** » Thu Mar 29, 2012 11:08 am

>> There are "weak" and "strong" smart pointers; so in a sense, yes and no.

I think i see... they're equivalent to a normal allocation in a gc language ... disposed when the last reference that refers to it is deleted, with a counter.

That'd be a solution - i was confused with the "weak" references because i was thinking of a memory leak, not a double delete (which don't exist in gc languages).

paulo · Post by **paulo** » Thu Mar 29, 2012 11:10 am

As a bit of trivia, even gcc had to incorporate a garbage collector in certain parts of their codebase because of problems like these... once you start deleting on more than one place and passing around references it gets sketchy.

paulo · Post by **paulo** » Thu Mar 29, 2012 11:12 am

"memory leak" as they occur on gc languages, doh!

Post by **drcode** » Fri Mar 30, 2012 7:06 pm

Thanks, Marzo, I see now. I thought we were safe because deleted objects go in the 'gamewin->removed' list. But now I see that that list gets purged (and really deleted) at the end of the caching-out code.

Perhaps we could add another object flag, say 'schedule_owned', and avoid removing these until the individual schedule clears the flag. Although having smart pointers would be a more general solution.

I still wonder if I could create a scenario, using your information, for making the bug occur. Otherwise, we'll never know if we've really fixed it.

Crysta the Elf · Post by **Crysta the Elf** » Sun Apr 01, 2012 10:14 pm

So how come nobody has fixed the items NPCs craft to be deleted properly once you've moved a short distance away? Sure it doesn't fix the underlying problem, but its got to be involved. I mean.. I just cleaned up about 200 pairs of shears sitting on the same spot on a table in Moonshade.. if that wouldn't negatively affect how the game runs I don't know what would.

And I forgot my password so new name.. ugh.

Post by **marzo** » Mon Apr 02, 2012 10:49 am

Well, it is exactly those schedules that delete the objects they make that are likely the cause of the disappearing objects bug, so yeah :-p

Crysta the Elf · Post by **Crysta the Elf** » Mon Apr 02, 2012 2:17 pm

So then the best fix would be to.... make it so that the schedules no longer handle deleting them? I mean if the schedules are the problem then making some new sort of code that assigns all items created through npc crafting some sort of "temporary" flag that removes them from memory once the player walks far enough away (in a fashion detached from the schedules, with the deletion part of those simply going unused) would be a viable workaround.

Actually, i've also wondered what's different between the NPC stuff and the teleport storm items for a while now that makes them work fine but the others not. Is it quite simply the NPC interaction doing it? I mean.. the two always seemed to function the same way in the original game, so I always assumed they were programmed to vanish using the same script or something.

And i'm not trying to be rude or anything with the stuff i'm saying.. s'just a combination of curiosity and how I am (artist, not programmer).

Crysta the Elf · Post by **Crysta the Elf** » Tue Apr 03, 2012 5:55 am

I should really clarify that a bit.. what I mean is.. if it is the interaction causing the problem, you need to sever the two functions from each other. Aside from blacksmith schedules that really require it (and barkeeps for plates? cant remember right now), NPCs should have anything that would make them interact with objects they've placed removed, and item deletion should be handled completely seperately. It would remove a few interactions (clothiers picking up and dropping shears for example), but it should remove the problem as well, at least until a total solution can be worked out.

mosinel · Post by **mosinel** » Fri Apr 06, 2012 3:32 pm

I assume it is necessary to "clean up" the npc created objects because currently there would be an infinite number of objects given enough time passed. However, as Crysta mentioned, 200 pairs of shears on a table surely isn't working as intended.

Wouldn't it be better if NPC crafters checked how many of an item already exist in the drop location and then if it is above a predetermined limit (default of 1) and there is no alternate drop location then just move to the next step of the schedule without spawning a new item. e.g. the drop location is a plate and the drop item is food, if there is already food on the plate move to the next plate if there is one else the new item is not created and the script moves to the next step as if the item had been. This way crafters would purely replenish consumed items. Handling it this way would remove any need to destroy NPC crafted items as there would be a hard limit set by the number of possible drop locations. Items would then only need to be destroyed/removed as a result of player actions and being consumed by other NPC schedules. No after the fact GC required.

This seems like a relatively easy change.

Post by **Dominus** » Fri Apr 06, 2012 9:40 pm

It would lessen the chance of the corruption but could still happen. As Marzo explained it's not a question of how many items were created but whether the items get tracked of.

Post by **Colourless** » Fri Apr 06, 2012 10:20 pm

Thinking about this. One fix would be creating a notify list when an object gets deleted. The schedule would add itself to the object delete notify list and when the object is deleted the schedule will know that the item is now gone and to clear any pointers that reference it.

mosinel · Post by **mosinel** » Sat Apr 07, 2012 12:35 pm

As I understand it, from reading this thread, the source of the corruption is thought to be deletion of an object by a second process/thread/schedule which because the original item has already been deleted proceeds to delete a second random object by reusing a stale/bad pointer which was tracking a specific object in the world that is already "gone".

So instead of making a change to schedule mechanics, how about making sure that each object has a truely unique ID .A hash of x/y/z/chunk & creation time perhaps. Any pointers to the object then contain the ID instead of an absolute reference. Requests for deletion pass the ID and if a later duplicate attempt to delete occurs then it aborts because the ID has become invalid.

ffgfd · Post by **ffgfd** » Sat Apr 07, 2012 2:19 pm

good luck reinventing reference counting guys.

Post by **Colourless** » Sun Apr 08, 2012 5:09 am

Trying to think of a way to avoid the problem without significant code modifications. Reference counting would require large amounts of code changes.

mosinel · Post by **mosinel** » Sun Apr 08, 2012 9:46 pm

Reference counting defers deletion of objects until all references to them have been discarded. Currently the code base presumes sole ownership of objects during deletion with the unforseen side effect of possible orphaned references causing bad deletes later on.

Deletion with reference counting would also require an object to be marked as "deleted", prior to the reference count reaching zero, in order to prevent any new interactions with it. This flag would then be inspected prior to any operation on an object in order to check that it isn't pending deletion.

Changing the code to to this extent appears to me to require a lot more work than kludging a check for a valid delete request via object IDs.

paulo · Post by **paulo** » Mon Apr 09, 2012 11:57 am

Ever heard of encapsulation? No? How about refactoring?

paulo · Post by **paulo** » Mon Apr 09, 2012 12:19 pm

Sorry for being rude, but i don't think a "flag" solution is any better basically. There's bound to be bugs and oversights, it's also intrusive (probably more), and it's essentially the same thing.

paulo · Post by **paulo** » Mon Apr 09, 2012 12:25 pm

Saner would be to just never delete memory on locations that didn't allocate it (or on O.O. program lingo "have ownership").

It's my natural strategy even on gc languages. I don't dispose stuff (open files for instance) passed as arguments (though i also don't pass stuff to multiple places normally, so i avoid the hard problem).

Anonymous Coward · Post by **Anonymous Coward** » Wed Apr 11, 2012 12:13 am

Re-implement the code base in a Lisp.

Mortegro · Post by **Mortegro** » Tue Apr 17, 2012 11:16 pm

Exult engine has been in production past 5 years. So my question is... With the knowledge and feed back from all the users. Could you guys maybe rewrite and code the engine again?

Post by **Dominus** » Wed Apr 18, 2012 3:55 am

With the time the devs have atm to spend on Exult... I doubt that this would go anywhere...

Ulf DellbrÃ¼gge · Post by **Ulf DellbrÃ¼gge** » Fri Apr 20, 2012 3:07 pm

Just stopping by, throwing virtual love to all people here at the phorum and an extra portion to the exult team. Thank you for you dedication. I try to imagine how you feel because of this rather serious and quite uncatchable bug. In the event that there is a greater power, i hope he soon triggers that "Aww @!#$, it was THAT all along" moment.

Kind regards

Ulf

Ulf DellbrÃ¼gge · Post by **Ulf DellbrÃ¼gge** » Fri Apr 20, 2012 3:17 pm

* or she (the greater power might be feminine, a comment i have to make, because it would be rather sexist and because it reminds me of life of brain. Know that scene?)

Leo213 · Post by **Leo213** » Fri May 04, 2012 5:13 am

There might be a correlation with the NPC schedules and the bug I just found which results in duplicate world objects to form upon the reloading of a chunk/cell

http://exult.info/forum/viewtopic.php?p=386431#p386431

paulo · Post by **paulo** » Thu May 17, 2012 8:51 pm

From this, it sounds like you need a "robot" class to make a testcase.

manutoo · Post by **manutoo** » Sun May 20, 2012 12:36 pm

Hello,

just in case... Does the Exult engine use floating point calculations ? Or only integer / fixed point calculations ?
If the later, it may be easy to record all inputs ( = mouse position + click, and keyboard keys pressed) on each game process frame, and then create a special "demo" mode which would automatically replay all the game using the recorded input to reach the point where the bug occurs.
For the replay to work correctly, you'd also need to have the initial saved game.
So users meeting the bug would send you that saved game with the recorded input file, and you could reproduce it.

I did that for several of my games, and it proved to be quite useful.

paulo · Post by **paulo** » Mon May 21, 2012 8:01 pm

That's only feasible if your side effects that don't come from user input can have two modes surely?

(ie: random would also need to store, like mouse movements, clicks, keyboard presses).

Post by **Colourless** » Mon May 21, 2012 9:12 pm

Exults use of 'rand' will make this difficult to get to work properly, in addition that Exult doesn't work with a concept of 'frames' so playback could vary depending on the speed of the machine recording and playback. Its a nice idea, but for Exult its more technically difficult then it seems.

manutoo · Post by **manutoo** » Tue May 22, 2012 12:15 am

Hello,

if you use a classic pseudo-random generator, then it's easy to deal with it (it's what I have in my games).
You just have to save the seed at start of recording ; then each successive rand() call should return the exact same value than in the original play.
If you use a more random() generator, ie: based on current time, then it'll be more delicate, but it may still be possible to just save & restore each random() result.

If you have a centralized game process or at least a centralized time handling, then you have something like this, I guess :
DeltaTime = TimeThisFrame - TimeLastFrame
so record DeltaTime for each frame, and restore it on replay, to force the replay to do a identical process, even if the actual speed differs depending of the computer power.

If your system is event based with all entities processing on different rates depending of machine speed, it might get trickier, but you likely have somewhere a central time handler that could be pushed in a replaying state instead of gathering real current time.

The killer thing would be that the rendering influences the gameplay on other things that the DeltaTime. In such case, it'd become a hell of a work to get things in sync : you'd have either to remove the rendering interactions with the gameplay, or save & restore all of them, but in both cases it'd very hard to be sure to have forgotten nothing, and usually if you forget only 1 little thing, it's enough to put your replay out of sync and make it completely useless...

Anyway, I'm just throwing ideas to make you think about a solution, in hope it'll help..!

manutoo · Post by **manutoo** » Tue May 22, 2012 1:37 am

One more note :

In case you do your game logic using something like Timer.CurrentRealTime , then you should replace it by Timer.LastFrameTime , so each gameplay component behavior won't be dependent of the previous components processing time.
Tracking all CurrentRealTime accesses (or calls) to replace them with LastFrameTime might be a bit tedious, but it shouldn't be much error prone (or you could even just simply change the behavior of CurrentRealTime so it'd actually contain the value of LastFrameTime ).

And then you'll be able to replay the game by restoring each Timer.LastFrameTime in the needed place.

Post by **Dominus** » Tue May 22, 2012 2:42 am

In any case this replay feature wouldn't be of too much help in this case. We know what triggers the bug, we also have some ideas on what to do, we only need to find time to do it.
An interesting part, where a demo mode were of possible help, is the reason why some people trigger this bug more often than others. But then U7 is a very lengthy game and watching other peoples playthrough would probably be an agony for people that play tested Exult that many times as we did

Also not sure whether your idea also gives feedback of how often the game was saved and reloaded which might also be one of the culprits.

paulo · Post by **paulo** » Wed May 23, 2012 10:48 pm

I know the location of the bug was pinpointed, but you might want to try this:
http://clang.llvm.org/docs/AddressSanitizer.html

Valgrind is typically much shower than 2x slower.

manutoo · Post by **manutoo** » Sun Jun 03, 2012 6:22 am

Dominus,
if you have an exact 1:1 input replay, then the save/reload cycle will be also reproduced. So it means the initial saved game shouldn't be overwritable during a recording, and if you want to do milestones of saved games with their associated recording (to possibly get quicker to the bug by having the replay only from the last saved game) then you would also have to prevent any other overwriting during the recording.

Anyway, keep this idea in mind, if not for the current bug, it may be useful for something else in the future...

Ralph · Post by **Ralph** » Sat Jun 16, 2012 2:02 pm

If there's heap object management issues, probably the best fix would be to properly convert code to using proper RAII and boost::(shared|weak)_ptr. C++11 would allow for the same without boost headers. This conversion would still require thinking through the lifetime and ownership of objects, but it would certainly be cleaner than reinventing ad-hoc refcounting.

Ralph · Post by **Ralph** » Wed Jun 20, 2012 7:13 pm

Any opinions on incorporating Boost? The license is highly permissible so it shouldn't be a problem to use in Exult.

Jaesun · Post by **Jaesun** » Thu Jun 28, 2012 3:35 pm

So I was playing the original U7 in DOSBox a while ago, and I suddenly seem to have this "my sword will now disappear" bug. Basically I have a sword and shield equipped. I was outside Nicodemus' house. I cast Unlock Magic on his door, and then suddenly my sword will disappear. This is also 100% repeatable, by re-loading the save. Is this also a known bug in the original?

Post by **marzo** » Thu Jun 28, 2012 3:47 pm

If this happens in the original while under DOSBox, then it has nothing to do with the topic at hand -- it is a bug in Exult that causes objects to disappear.

In all likelihood, what you encounter is Nicodemus stealing your sword -- I *think* he is scheduled to do that, but I don't remember for sure.

Paulon · Post by **Paulon** » Thu Jun 28, 2012 6:01 pm

The deranged Nicodemus is a pain when it comes to stealing your gear in the original.

TDI · Post by **TDI** » Thu Jun 28, 2012 9:42 pm

Yeah, on a certain time of day, Nicodemus turns into a sneaky, thieving bastard.

******** minor spoilers ahead *********

**** stop reading or thou shalt become bespoileth *****

Nicodemus is in thief mode when standing outside his house. In the original U7 (probably also in Exult) you can identify thieves by the things they say while stalking around you. They say nice, inconspicuous things like "Nice weather today", "How are you?", etc. Then at some point they move in close and lift an item from your NPCs inventory.

But that is not a game breaking problem. A mighty Avatar can smack'em over the head, open them up, get the item back, and resurrect them in a pinch. The hardest part is to actually find out that something has been stolen.

Ralph · Post by **Ralph** » Tue Jul 03, 2012 7:18 pm

On a friendlier note, is this bug exclusive to BG? I really don't see why it would be, but I don't think I've heard of it happening in SI...

Post by **Dominus** » Tue Jul 03, 2012 7:25 pm

It's harder to trigger in SI because there are fewer item producing NPCs. But it did happen to me on my playthrough of SI.

Post by **drcode** » Sun Aug 19, 2012 5:38 pm

Looks like I'm going to work on this, and I think I'm going to use Colourless' suggestion to have each object have a 'notify list'.

Hopefully, this will solve the problem for two cases I can think of:

1. The schedule creates an object, like 'dough' for the Back_schedule, then deletes it, even though it's been cached out.
2. The schedule found existing items like the table list for waiters. These get cached out, but the schedule continues to reference them.

Post by **Dominus** » Sat Aug 25, 2012 5:32 am

How is the progress? Curiosly I didn't even notice the first committ until Kirben added objclient.o to makefile.common

Please give us a heads up when we should begin playtesting. I'm eager for a BG run

Post by **drcode** » Sat Aug 25, 2012 5:12 pm

I have a few more schedules to do, so I might be done this afternoon.

But here's the catch: If I made any mistakes, or missed something, the game will probably crash instead of corrupting memory. But maybe that's an improvement.

Post by **drcode** » Sat Aug 25, 2012 6:41 pm

Okay, 'done', but without a lot of testing. I have no idea how to verify that I actually accomplished anything.

Post by **Dominus** » Sat Aug 25, 2012 7:36 pm

Wow, thanks. I'll se about playing through BG next week. I hope nothing bad happens

Edit: btw. let me hug you!!!

Post by **Malignant Manor** » Sat Aug 25, 2012 10:27 pm

Thanks Jeff. You inspired me to fix my baking checks since I used quality for checks, and that doesn't save for quality flags items.

smev9 · Post by **smev9** » Sun Aug 26, 2012 10:41 am

I want to test. can i download the new version in the generel download section in "unstable" ? Is there anything i would have to do besides playing and saving to help you with?