What's wrong with reversing an action like this?

Question

I'm working on an undo and redo system map editor and have come across a major issue. If I place a tile down, move right a tile, and then move back to that tile I previously placed everything works fine. Until I try and Undo, Redo, and then Undo again.

This is the state when they're placed:

Executing: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
Executing: 
X: 1
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
Executing: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 

The undo redo stack looks something like:

Unexecuting: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
41
Unexecuting: 
X: 1
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
-1
Unexecuting: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
-1
Executing: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
Executing: 
X: 1
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
Executing: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
Unexecuting: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
-1
Unexecuting: 
X: 1
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
-1
Unexecuting: 
X: 0
Y: 0
Tiles: {X:32 Y:160 Width:32 Height:32}
Previous Tiles: 
41

I don't want this to be a code dump or "debug my code for me". I understand the problem is located at the bottom most segment where it assigns the tile an ID of 41 once again - since that's what it's previous value was. This works the first time - but not the second as seen. I'm confused to why the algorithm fails. If anyone has written something similar, feedback would be appreciated. I don't need code-fixed - just hints as to where I can find a working algorithim or a rational explanationa s to why this happens. It's just a simple pencil tool that should write tiles the grid.

  public new void Execute(GameMap gameMap)
{
    Console.WriteLine("Executing: ");
    PrintState();

    _previousTiles.Clear();

    // Get vertical portion
    var curTexture = MapEditorGlobals.CurrentActiveTexture;

    // We need to loop over the width of the editor
    for (int w = 0; w < SelectedTiles.Width / 32; w++)
    {
        for (int h = 0; h < SelectedTiles.Height / 32; h++)
        {

            var gX = SelectedTiles.X / 32 + w;
            var gY = SelectedTiles.Y / 32 + h;

            var tY = (gY) * curTexture.Width / 32;
            var tX = gX;
            var tileID = tY + tX;

            _previousTiles.Add(gameMap.Layers[Layer].MapTiles[X + w][Y + h].TileId);
            gameMap.Layers[Layer].MapTiles[X + w][Y + h].TileId = tileID;
        }
    }

}

  public new void UnExecute(GameMap gameMap)
        {

            Console.WriteLine("Unexecuting: ");
            PrintState();

            List<int> newTiles = new List<int>();

            // Get vertical portion
            var curTexture = MapEditorGlobals.CurrentActiveTexture;

            // We need to loop over the width of the editor
            for (int w = 0; w < SelectedTiles.Width / 32; w++)
            {
                for (int h = 0; h < SelectedTiles.Height / 32; h++)
                {

                    var gX = SelectedTiles.X / 32 + w;
                    var gY = SelectedTiles.Y / 32 + h;

                    var tY = (gY) * curTexture.Width / 32;
                    var tX = gX;
                    var tileID = tY + tX;

                    newTiles.Add(gameMap.Layers[Layer].MapTiles[X + w][Y + h].TileId);
                    gameMap.Layers[Layer].MapTiles[X + w][Y + h].TileId = _previousTiles.Last();
                    _previousTiles.Remove(_previousTiles.Last());
                }
            }



        }

Answer 1

Don't get overly clever with your storage. For each operation, store the old value, the new value, and what changed. Something like:

class Edit:
  int x
  int y
  tile_t old
  tile_t new

  void apply_undo():
    set_tile_at(x, y, old)

  void apply_redo():
    set_tile_at(x, y, new)

You will want this to store whole (not necessarily rectangular) regions of tiles as any decent tile editor can do operations on multiple tiles. The hardest one, IMO, being "flood fill".

Essentially, each Action should store the delta of the map after applying its corresponding changes as completely but narrowly as possible. That means you need all the information to both apply the action and undo it, such as including the old and new tile values as shown. For other types of edits you could just store a big grid or 2D array of tiles so long as you have a way of marking a particular tile in said grid as "not changed." This ability isn't immediately apparent but it has uses later.

Note that a naive first-draft implementation can just store the entire map at each edit point. You can avoid saving the old map for each edit as it will be given by the previuos edit (the delta is implicit in the edit history). You will need an "initial state" item added to the history in this case. I don't recommend this particular approach, but it can help to visualize what's going on.

You now need to keep a history of your actions, including the level of undo you're at. Every time you do an Undo, apply the current level's undo action then step back one item. When you do a Redo, step forward one and apply the redo action. If you perform a new action, you probably want to truncate the history first to the current undo level and then add the new record (this is what most undo/redo systems do).

class History:
   Action list[]
   int level

   void undo():
     if level > 0:
       level = level - 1
       list[level].apply_undo()

   void redo():
     if level < list.length:
       list[level].apply_redo()
       level = level + 1

   void add(action)
     list.truncate(level)
     list.add(action)
     level = list.length

That simple. Note that depending on how you build and apply your actions, you can just make an Action instance and then call its apply_redo() to do its action for the first time. Some actions like flood fill might generate its undo/redo data while being applied, though, depending on how you implement it.

Some of the harder actions to implement include the aforementioned flood fill, canvas resizes, and the manipulation of non-tile objects in the world. Making Action an abstract interface that you can implement in multiple ways will come in handy as you add more complex operations to your editor and hence need more complex ways to undo/redo things.