Data structures and stuff
May. 4th, 2018 12:00 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackThe 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.
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.
no subject
Date: 2018-05-04 02:15 pm (UTC)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...
no subject
Date: 2018-05-04 02:23 pm (UTC)no subject
Date: 2018-05-04 02:27 pm (UTC)no subject
Date: 2018-05-04 02:31 pm (UTC)no subject
Date: 2018-05-04 02:44 pm (UTC)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!)