Storing Changes for Persistent Zones

[wire_hall_medic]

So I'm laying out my new project.  There is an overworld, and several dungeons; all are at the same scale.  However, the player will have ways of interacting with the environment; destroying walls, burning trees, opening chests, etc.  To make the zones persistent, I plan on simply saving the seeds.  However, I also need to save the changes the player made to the environment.

The best way I see is as follows:
Have a class ChangedTile which has variables xLocation, yLocation, and changeType.  ChangeType would be an enumerator for things like OPENED, CLOSED, DESTROYED, FLOODED_WITH_ACID, or whatever.
Have a class called ZoneChanges which has a list of ChangedTiles of dynamic length, for each tile that has been changed.
Have a list of ZoneChanges corresponding to the number of zones in the game.

But this feels hideously inelegant to me; I feel like there must be a better way.  I'm going to have 5 main dungeons of 5-7 zones, a final dungeon of 13 zones, perhaps 10 optional dungeons of 2-4 zones, and an overworld of probably 15x15 zones; if this proves too crowded, I might wind up with as much as a 20x20 overworld, though it doesn't need to be square.  All in all, I'm looking at several hundred zones.  Thankfully each changed tile is only three shorts, and I'm only loading or writing one zone at a time, but it's still a lot of information.

Does anyone have any experience with something like this, or just have a slicker idea than what I've got in mind?

[reaver]

A really simple/(simplistic?) version that I have been thinking:

Run a 'diff' over the seed generated map, and see how many cells have changed.
if more than X% of the cells are different
    store the map as is
else
    store the seed and a mapping of altered cell positions to cell content:
        e.g. changes[(32,13)] = blah
               changes[(45,12)] = bleh
   

[Krice]

What is the actual problem you have? Is it the size of save files? I think you could have good results with some kind of packing method, depending on the structure of maps and objects. It's easier than keep track of individual changes in tiles.

[Omnivore]

Store the random generator's state and a list of player inputs from level start.    This gives both a persistent state and a recording that can be played back. 

I'd think about including a time factor though, not because of save game sizes, but to help immersion.  The idea being that the levels aren't 'frozen' when the player leaves - things still happen.  Abstract this by applying random changes based on the length of game time that has passed. 

At some point the passage of time will be sufficient that you could degrade the store to just the seed and time stamp.  Time has erased the effects of the player's passage.  Maybe just hang on to a few player induced changes for effect.

One way to achieve this might be to create a 'weathering' process with inputs of random generator state, time span, and player action record.  You might want a fourth input - the 'weathering' process seed - so that there is consistency on reloads.

[Cfyz]

To make the zones persistent, I plan on simply saving the seeds.  However, I also need to save the changes the player made to the environment.

Your game will feature several dungeons and a few dozen of 'zones' -- it should be hard to finish in one go. Most likely you will have to support saving the game (and its world) to a disk anyway. In this case, it might be easier to just save permanent zones in the same way you will be saving the whole world. My point is, you'll probably get permanent zones as a byproduct of implementing an integral feature.

[wire_hall_medic]

This stems from an expectation that the player will double back with some frequency.  A quick test shows that a .txt document with 400 zones, each with a seed value and 20 changes (each of which is two two-digit numbers and a character) runs 60 kb.  This is assuming an unexpectedly large number of changes.  An acceptable size, but I feel like there should be a better way.

This will be much more important later on when more features are added, but for the initial build I want to make sure this feature is in place.

@Reaver: The problem is the player is likely only going to make a few changes.  Opening chests, destroying a few walls; if he hits a dead-end and doubles back, the rocks he moved as a barrier shouldn’t have disappeared.

@Krice: My problem is one of relative inexperience.  Since I'm not a professional programmer, there are some significant gaps in my knowledge.  I have a solution, but I figured I'd ask the community if there were a better data structure than what I had planned.

@Cfyz: I’m using the term ‘zone’ instead of map or level.  For example, a dungeon with five floors has five zones; I want to avoid using map because this has specific programming connotations, and I didn’t want to use level because there are different types; dungeon level, experience level, etc.  There will be several hundred zones, because the overworld is a grid of them.

[reaver]

@Reaver: The problem is the player is likely only going to make a few changes.  Opening chests, destroying a few walls; if he hits a dead-end and doubles back, the rocks he moved as a barrier shouldn’t have disappeared.

Hmm sorry I was unclear, modified above what I said (addition in bold)

[Krice]

I have a solution

Eh, no, you have a problem. You just don't seem to know exactly what it is. But when you want to save the seed and changes it seems to be some kind of problem with save file size. Do you want to optimize the save file size and if so, for what reason? If there is no reason, you can simply save everything.

[ahnlak]

Do you want to optimize the save file size and if so, for what reason? If there is no reason, you can simply save everything.

That was my immediate thought too; sure, 20 years ago file space was precious and it was worth putting in the extra work to keep them small, but these days the filesizes involved in saving the entire map are pretty insignificant.

It'd certainly be neater to save a bunch of diffs instead, and if you want the fun of that programming challenge then go for it - but every hour you spend coding something utterly internal like this is an hour lost on code that actually affects gameplay.

[wire_hall_medic]

Do you want to optimize the save file size and if so, for what reason? If there is no reason, you can simply save everything.

That was my immediate thought too; sure, 20 years ago file space was precious and it was worth putting in the extra work to keep them small, but these days the filesizes involved in saving the entire map are pretty insignificant.

It'd certainly be neater to save a bunch of diffs instead, and if you want the fun of that programming challenge then go for it - but every hour you spend coding something utterly internal like this is an hour lost on code that actually affects gameplay.

Those are both reasonable, despite how this itches at my brain; I'll just save everything.  If it winds up being a problem, I'll do something slicker.

[Kyzrati]

Do you want to optimize the save file size and if so, for what reason? If there is no reason, you can simply save everything.

That was my immediate thought too; sure, 20 years ago file space was precious and it was worth putting in the extra work to keep them small, but these days the filesizes involved in saving the entire map are pretty insignificant.

It'd certainly be neater to save a bunch of diffs instead, and if you want the fun of that programming challenge then go for it - but every hour you spend coding something utterly internal like this is an hour lost on code that actually affects gameplay.

Those are both reasonable, despite how this itches at my brain; I'll just save everything.  If it winds up being a problem, I'll do something slicker.

I would totally save everything. Not saving everything and implementing some other crazy solution would downright tear at my brain every time it broke. Don't ask for trouble unless your goal is to carry out an experiment rather than make a game

[Rickton]

Yeah, 60kb is nothing these days. Almost literally nothing, depending on how many decimal places you round to.
Unless you're writing something that's actually intended for something with severely limited disk space, just save everything. It may not be the most "elegant" solution, but nobody playing the game is going to care how "elegant" the saving is, they just care if it works. Spend the time you would have spent coding up a fancy saving solution on the game itself instead.