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-11 07:21 pm (UTC)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.
no subject
Date: 2018-05-13 01:41 pm (UTC)no subject
Date: 2018-05-14 03:40 pm (UTC)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.
no subject
Date: 2018-05-14 09:56 pm (UTC)no subject
Date: 2018-05-13 02:08 pm (UTC)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).