Data structures and stuff

[jack]

The premise

I have a tile-based computer adventure game. The current state is represented in memory as a 2d array of tiles representing the play area, each with one (or possibly more) objects on that tile. There is also an "undo" history, tracking recent actions, and the difference (objects moved, removed or added) so the previous or following state can be recreated.

In addition, each object remembers the most recent undo step which affected it, so you can click "undo" on an object and return it to the previous state (also undoing any following actions), not just undo one at a time until you rewind to the appropriate point.

I need to check the code, but as I remember, this is represented by each object having a pointer (well, the python equivalent) to one of the elements of the undo sequence. And when you redo or undo the pointers are updated to refer to the newly-correct object.

Now I'm unsure, but IIRC the undo steps refer to an object by coordinates in the play area, not a pointer to the object (in general, we assume the play area might store game objects as just ids or something, not as ab object in memory).

What happens when we want to save the game

We need to be able to save the game -- indeed, a modern game (especially one where actions aren't irreversible) should just save as it goes along, not require a separate load/save action to do so.

This means my instinctive layout above doesn't work. You can't save "a pointer". The best option is probably to use an index into the undo list which the undo list understands.

That can also cut out other possible bugs. If you have a pointer, it could be anywhere in memory. If you have an index into the undo list, you can choose to have the list check that the dereference is valid (and retain the option to turn those checks off if performance matters).

There's other possibilities but I think that's the best one. It is uncomfortably close to designing our own ORM -- we could alternatively have ALL objects represented by a unique id and index things by that instead (either via some global list of ids or only when we load from disk).

I run into this often when I'm game programming, the best way of 'referring' somehow to another game object -- by value or reference? by game coordinates or pointer to memory? But not in other types of programming. Does this experience ring a bell to anyone else?

But now I'm thinking...

This also reminds me of a problem I ran into when I started thinking about rust's memory models. If you have a class, that creates a bunch of other classes, and those classes want to have pointers to each other, there's no easy way of doing it iirc.

I think you need to rely on reference-counted pointers even though it feels like you shouldn't. That's not a problem in practice -- the "store an index" method above also has an indirection every time you need to access the object. But it feels like, you shouldn't need to. And a similar sort of "I want to refer to one of the classes which this big class is responsible for".

But I'm not sure if there's a way of combining these thoughts.

Comments

[simont]

partly because (a) for a larger game, it feels like that's going to be slow

It's true, of course, that this takes O(N) time to replay the whole game back to the current position. And that doesn't matter much in my puzzles because they tend not to be especially open-ended – people don't keep playing a single instance for months on end, saving and reloading as they go.

But my thought at the time was that any serialisation format that you reload by reading the file from start to end would necessarily take O(size of file) time to reload, so it wasn't actually particularly slow compared to other options! The only way you could avoid that is by making the save file itself an on-disk data structure, so that instead of reading the whole file at load time, you just memory-map it, directly follow pointers to the part of the file representing the current state of the game, and keep going from there, delving into other parts of the file only if and when things in the undo chain are actually needed.

And if you're going to do that, then the pointers vs symbolic references dilemma more or less solves itself, because now the answer is surely that your references between objects take the form of file offsets rather than either memory addresses or abstract object ids. And probably you keep the whole game state in this memory-mapped file right from the word go, which gets you the other feature you mentioned, that you never need an explicit 'save' action in the first place.

(Perhaps a small refinement might be to break up the game data into multiple subfiles, so that a reference between objects now takes the form of a (subfile,offset) tuple. That would give a convenient way to discard very old undo history, if you wanted to bound the ongoing size of the state – just purge sufficiently old subfiles, and then you don't have to have a secondary free-list structure within the still-live ones to reclaim the space.)

[jack]

toothycat on LJ points out that if you save all the relevant objects together, python's pickle *does* magically figure out when there's multiple references to the same object, save it once in the save file, and recreate an objected referenced from multiple places on de-pickle. So that might be the easiest way to actually do this.

But my thought at the time was that any serialisation format that you reload by reading the file from start to end would necessarily take O(size of file) time to reload, so it wasn't actually particularly slow compared to other options!

I think both are O(N) (after all, you played through the game in O(N) time to start with, I guess) but if you're deserialising something like starcraft, it seems like simulating hundreds of units over hundreds of thousands of ticks, it's likely to be slow even if proportional. In practice my game would probably be much less complictaed than starcraft, but more complicated than your puzzles.

Perhaps a small refinement might be to break up the game data into multiple subfiles

As mentioned to green_knight below, I ideally do want infinite-undo, but I might well do something like divide the game into different areas, and save areas you're not in in less detail.

[damerell]

Re slow, one NetHack variant experimented with savefiles being a complete replay; they abandoned it not because it was slow (it wasn't) but because any change to the game would then break savefile compatibility, a nuisance for an actively developed variant.

(That said, that wouldn't work in Crawl, a superficially similar game, because autotravel and the like do take significant CPU... without some thought so that all the shortest-travel calculations were omitted and only the end result, the destination, stored. Sorry about the repeated edits.)

[jack]

Ah, good point. Thank you. I'm not sure if that would affect me or not, but it might do.