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

[themidnightgirl]

Can I suggest that your fundamental problem is that you've got a bad level of abstraction here?

Also, it seems the wrong way around - what you have is a sequence of moves that change the state of the game board. You can undo or redo, which moves you along that sequence. Each move could then either be represented as the complete state of the game board, or as a delta on the previous state, whichever is easier. Then you can move freely forwards and backwards, either replacing the gameboard with the right one, or with reversing or re-applying the delta. Your game save then becomes straightforward.

[jack]

Thank you to everyone who commented, just talking it through is helpful.

Can I suggest that your fundamental problem is that you've got a bad level of abstraction here?

That seems very likely :) But I need to think through that a little before I come back to comment.

[jack]

I think I follow you but I'm not sure, is what you mean covered by what Simon added below?

[simont]

In case an alternative perspective is useful to you, my puzzle collection supports saving a game including the whole undo chain, by a method that requires no serialisation of references at all:

Every 'move' the player can make (defined as precisely those UI actions that append a state to the undo chain) has a string encoding. The saved game file consists of a description of the pristine state of the game board, followed by a list of all those move strings. Loading the game consists of replaying the moves one by one to reconstruct the undo chain.

To avoid this being an endless source of subtle bugs that only show up if you happen to save/load a game containing some particular rare move type, the process of ordinary gameplay works by generating and immediately decoding these move strings. There's a function interpret_move which takes a UI event as input and optionally returns a move string to be appended to the chain, and execute_move which takes a move string and constructs the game state structure describing how things look after it. So normal gameplay calls execute_move whenever interpret_move returns a string, whereas game loading just loops round on execute_move. Hence, if any move string encoding is not correctly decoded by execute_move, you'll notice that the first time you test making that move in normal gameplay, long before you worry about saving and reloading.

This completely avoids the need for the save format to store references between in-memory version of the game state. If there are any, then they were originally put there by a call to execute_move during play, and the corresponding call to execute_move during loading will set up the same reference between the new set of game state structures.

(In fact, my puzzle collection doesn't support your notion of 'undo to the last action that affected this particular game element', but if it did, I think I wouldn't have to change anything about this basic structure.)

[ptc24]

Which reminds me of the Starcraft replay we once watched, where evidently the replay was going through our click history, and at some point one thing got missed. At first there was a "hang on, didn't we win that battle?" moment, followed by things increasingly diverging from what we remembered. The AI, it seems, continued to react to what was really happening in the replay, but our troops got orders from an increasingly divergent alternative timeline that made less and less sense.[1] Ultimately the computer wiped the floor with us, despite us having won the game it was a replay of.

[1] If you've read Jingo by Terry Pratchett, like that.

[jack]

Yeah, it's fascinating when that happens, and if anything hard to avoid it, without either (a) ignoring the inputs, but recording all the resultants destructions, movements, etc or (b) as Simon says, running the whole game through the replay logic when you play it normally.

[simont]

I've heard that story before (though sadly I wasn't one of the people who saw that replay), but I don't think it's ever previously struck me that there are actually two ways that bug could have happened.

One, as you say, is that the replay missed or misinterpreted something in the recorded stream of UI actions, so that the simulated human behaved differently and the AI code responded sensibly to the modified stream of inputs.

But the other is that the AI was the first to diverge, by not quite meeting the guarantees of determinism that this replay-saving strategy depends on, so that in the replay it responded differently to the same inputs.

Now I think about it, the latter sounds much more plausible, just on the grounds that the AI strategy code must be more complicated than the UI action interpreting code...

[ptc24]

Possibly there's a third way - the game state diverging. I think there's something where shots fired uphill have a chance to miss. If the replay is done properly the RNG should stay in sync between the main game and the replay, but maybe some glitch could desynchronise the two, and that's enough to get things diverging.

[simont]

Oh yes, you're right. I forgot Starcraft 1 had that element of randomness. SC2 got rid of it – shots fired uphill hit reliably, provided you've got a way to get vision on the target unit to fire at it in the first place.

[jack]

Oh yes, excellent point. I'm actually quite surprised it *did* rely on re-running the AI rather than just recording both the player's and the AI's moves and replaying both. OTOH, I'm not surprised that e.g. a move might have had a slightly different outcome (if anything is insufficiently deterministic, e.g. they accidentally used a non-simulated time for somehting etc).

[simont]

The mysterious Starcraft 1 replay incident that I remember – a different game from the one ptc24 describes – was related to a rarely used game feature.

SC1 had a really strange custom game mode in which you could choose to start off with your starting building and workers not all from the same race, e.g. a Terran command centre, two SCVs, a Zerg drone and a Protoss probe. Provided the 'foreign' workers (by which I mean the ones that can't be rebuilt from the building you have) didn't get killed first, you could use them to establish expansion bases once you had the minerals, and then build further foreign buildings and climb the other tech trees, ending up with a mixed army of two races or of all three. This led to some amusingly game-breaking effects: firstly, supply was tracked separately per race, so you could increase the usual supply cap of 200 to 600 by maxing out all three races, and secondly, some cross-race unit combinations are absurdly overpowered, like Zealots being healed by Medics.

Unfortunately, the replay file didn't preserve the vital piece of starting data that said some of your workers weren't the same race as the initial base building. So when we tried to watch a replay of a co-op humans vs computers game played in that mode, the human side in the replay started off with the wrong set of units, which promptly invalidated all the control inputs, so the replay consisted of the human side never doing anything whatsoever, and just having the initial four SCVs waiting passively by their command centre for the enemy to come and kill them. That made it totally obvious that the AI was re-computed – it never responded to any of the things we'd done in the real game, it just did what it would naturally have done against a totally passive opponent.

(Which, it turned out, involved a leisurely expansion over half its side of the map before it even thought about coming to look for us. No early rush tactics at all, or even exploratory scouting!)

[jack]

Thank you, yeah hearing a comparison from someone who's actually implemented something like this is very helpful. That's a v helpful description.

Yeah, I agree, if loading replays the whole undo string, that basically resolves all of the problems, and is an effective/elegant way of doing it.

But I'm not sure that's *the* answer, partly because (a) for a larger game, it feels like that's going to be slow and (b) I feel like I've had the same sort of problem in other circumstances (although I agree, localising it to the save/load system in this way may resolve it).

my puzzle collection doesn't support your notion of 'undo to the last action that affected this particular game element', but if it did, I think I wouldn't have to change anything about this basic structure

Yeah, I think it would work equally well.

[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.

[green_knight]

I hope I'm envisioning this right, but my solution for so many problems has been to give items unique IDs. (A leftover from my database days). So if each entry on the undo stack has a unique ID, you can just save that. (You could just traverse the undo stack from the end until you get to an entry for your object, no pointer necessary).

Some of this depends on how large your undo stack is: it's good (and necessary) to have one undo, great to have 20, but beyond that, it becomes a bit ridiculous, and a puzzle might be better off having a 'start from beginning' feature.

[jack]

Yeah, I was considering that, and I'm nervous about some aspects of it, but it also may be a very sensible approach (and better than anything to do with pointers :))

Some of this depends on how large your undo stack

I have a hidden motive here. I'm not sure if this is the game I'll end up making (if any), but I have this idea for an adventure game with an undo and a redo all the way through the game that can 'rebase' the redo on top of other actions.

So you can do things like:

Room 1: Player escape prison cell
Room 893: Player needs hacksaw to defeat final boss
Player: rewinds to room 1
Player: searches more thoroughly, finds hacksaw hidden in cake
Player: fast-forwards to final room
Room 893: Victory!

The point being, that sort of puzzle is staggeringly unfair if you can only progress linearly, and even in Lucas-arts style games, it often constrains the design a lot if you can't throw things off a cliff if you might use them later, or can't offend a character you need. But if you can try things out without penalty, you can create puzzles that interlock much more, with a philosophy of "anything can happen".

I may not actually do that, but I'd like the engine to support it :)

[simont]

an undo and a redo all the way through the game that can 'rebase' the redo on top of other actions.

Yes! And not just adventure games, either. I always used to want that feature in puzzle games of the XOR family (which also include the 'Enigma' game on my web page, and the spiritual sequel 'Chroma' by its original designer). Those too have the property that you get 700 moves into the game and then realise that if only you'd done something slightly differently in room 1 and then done the rest of your current solution unchanged, you could make progress.

I never got round to it, but I always quite wanted to try to build a rebasing UI for Enigma. I felt it might well be tractable in UI terms because it wouldn't make sense to rebase a move sequence from parent state A to state B unless the player character's location was the same between A and B, which would mean that when you selected a chunk of moves and tried to drag them, the UI would be able to narrow down to quite a small number of positions that it would even make sense to rebase them to, and mark them / auto-snap to them / generally make it easy to land on the right one.

(I think one reason I never got round to it is because those games depend critically on human-designed levels, and there's a finite supply of those, so once you've solved them all yourself, your motivation to design and implement an elaborate UI to make your own life easier suddenly vanishes...)

[jack]

Ah! Yes, that would make sense.

[green_knight]

(I'm currently working on a game engine, so these thoughts are super-relevant to me; I haven't reached the point where this is actually a thing I'm implementing, but I've thought about it. Had to go away and wrestle other things for a bit.)

One part of my solution to this problem is that I'm dividing the story into zones - and if you cannot get back from B to A, you'll need all of the Quests/QuestObjects before you can proceed.

In your case, I'm not sure that 'undo' is the right metaphor.

I'm also not happy with the game not offering manual saves, because sometimes I want to unroll to a certain save point. And if your game does not offer me an interface, I'm likely to find the location of the save file in the library and back it up manually and curse a lot. (Looking at you, Shadows of Mordor.)

But the other point is that you seem to know exactly where your game-breaking objects are located, so you could just take the character back to that place and let them search again, applying any other gains to their current status, and then continue the game from where they were - a 'revisit' rather than 'undo'.

But mainly, I wish people would stop putting breaking actions into their games, because playing 40h to find that you've made a mistake right at the start is a dealbreaker for me: not only will I despair, run around aimlessly and look under every rock, eventually google, and find the 'gotcha' the designers put in, I will put down the game, walk away, and tell everybody what a rotten piece of shyte that game is.

Basically, designers *literally* create the world, so when they print all the cards and then mock you that your hand sucks, I do not enjoy myself. If there's something I need to find, give me a clue. (I'm currently and for the foreseeable future playing ESO: Tamriel, and those markers are ridiculously obvious, and there's still a lot of gameplay and sneaking around trying in to find things.) I'd love to see more games where hints increase gradually: you can find it yourself, you get subtle and not-so-subtle hints, and if you made it through to room 893, there's a pedlar outside flogging hacksaws for exorbitant prices.

After a certain level of searching, I am no longer playing, I am googling solutions, and the more tedious you make it, the less I enjoy myself.

So... I'm not sure that the rewind would work for me. 'I will make you play this until you get it right' doesn't feel like gameplay to me.

At the same time I get the 'wanting to give players options' because that's one aspect of puzzle-type games that annoys me: you cannot improvise and use the items in your inventory in an innovative manner, you have to second-guess the designers. Which I find tedious.

[jack]

Oh, cool, I'm interested in what you're building -- I know it's not finished, but for what sort of game?

[green_knight]

The app is called WorldWalker and right now, you can create scenes, connect them, and move from one scene to the next.

Once upon a time (1984, IIRC), there was a Mac app called 'WorldBuilder'. It had two windows - an 2bit image where you could click on things, and a text window where you could type N/E/S/W and play twenty questions with the dictionary. You could equip two weapons and decide which one to swing when you - inevitably - encountered monsters, and have a really good time.

With the advent of PowerPCs, WorldBuilder no longer ran. At that point I'd used it for seven years, created dozens of apps with it, including exam preparation, and mourned its demise.

And ever since, I kept thinking 'I wish there was a tool like that'. Eventually, I realised I'd have to write it myself.

I'm keeping the image-and-text concept, I will let users choose from a menu of responses instead of making them guess keywords, but otherwise, I'm aiming for that kind of experience: scene-based, and story-driven.

Here's some concept art from the early days:



Almost any problem you have as a designer, I have squared: I not only need to think about what I want, but how it can be abused. And while I cannot stop anyone from being a dick to their players, I am working very hard at making good gameplay the default option, the easy path.

Ideally, I want this to replace WorldBuilder as a tool: a way for people without a lot of programming experience to make fun games; a way to think your way through a complex idea and go 'how would this flow' even if in the end you'll choose a different engine.

[jack]

Oh, that's cool!

[jack]

Agh, complicated reply. Basically, all of your rant is where I started, but my reaction was not "stories should never contain irreversible actions" but "how can they be incorporated into a game which is actually fun."

My idea was that always requiring that characters have an in-world way of reversing mistakes and finding objects has quite a lot of constraints on the plot -- it means that if the character ever moves from one place to another, or enters some dangerous situation, they either need to be required to have picked up all relevant objects and taken relevant actions before then, or have some way of leaving the current situation to do so now.

However, if you take the point of view that, near the end of the game, you can teleport back in space *and time* to do the thing you missed, and then teleport forward again to finish the climax, you have a lot more flexibility to add interesting interactions between objects and events. For clarity, I don't mean in-universe teleport, I just mean that the player can select a place (or equivalently, an earlier point in time) and do a thing, and then go back to the furthest point they reached.

To me that's the opposite of forcing them to replay it repeatedly, because they don't have to retake all the actions inbetween, they just click one button and go straight to the end of the game. But I'm aware, this is an idea I haven't really tested, so if people who have the same basic starting point as me are put off by it, I should reconsider if it's actually desirable.

What I like about it is that there's LOTS of puzzles that would be utterly unfair in a normal game, that work fine if the character has the option of exploring other areas to find a solution, even if those areas wouldn't logically be available to the character at that point in time. Random ideas like, you have a cell, you're breaking out, it strains credibility that if you do it wrong you can do it again without anyone getting suspicious, but that's what lots of games require, but this game wouldn't. And you have a bunch of actions you can take to do so, but the puzzle is getting them in the right order. Or it's often logical that you can *throw something away*. Most games prevent that (or you just lose if you throw away the necessary plot item). That means you can't have any puzzles that involve throwing something in the sea or whatever, unless the character immediately announces that doing so is relevant simply by letting you do so. This game you could easily do that, because you can undo that single action (either immediately, or rewind that one action individually much later on in the game).

[andrewducker]

I've been thinking of this from a Blockchain/Git point of view. You can either save the state-changes, or the states. State-changes at each point are probably smaller, so long as you don't need to worry about an RNG (and keeping that in sync). States are simpler though, as you don't need to worry about the same changes moving you to the same new state.

Obviously, saving all of the states would take up more space - but it's possible that compression would work well on this. Particularly if you were breaking up your world into lots of pieces, most of which weren't changing very often.

[jack]

Yeah, I think that's a good way to think of it. I think I'll end up storing one or two states (say, the current one), and changes. I avoided going full-git, although if I follow through on some of my ideas (see replies to GK) I will need the equivalent of rebase.