Stuck at creating undo functionality in C#/XNA Game

Question

So I want a undo functionality for a MapEditor I am working on in my game. I got it partly working. When I click on the map, it stores both the old and the new tile in seperate lists. When I press Ctrl + Z, it will undo the last action and so on.

My problem is when you undid some actions, and then add a new action to the lists. What should happen then? Should I just add the new action at the end of the lists, or should I remove everything from the current position in the lists till the end, and then add the new action to the list.

My problem is that I can't wrap my head around this. I've tried multiple things, but they all were kind of broken when this situation occurred.

So again, I need to know how to proceed when adding the new actions to the undo list.

My current code when adding to the undo list:

private void UpdateCorrectedTiles(Dictionary<TileSide, Tile> correctedTiles, bool saveEditedTiles)
{
    List<Tile> tmpUndoTilesList = new List<Tile>();
    List<Tile> tmpRedoTilesList = new List<Tile>();

    foreach (Tile tile in tiles)
    {
        foreach (KeyValuePair<TileSide, Tile> correctedTile in correctedTiles)
        {
            if (tile.GetTilePosition() == correctedTile.Value.GetTilePosition())
            {
                if (correctedTile.Key == TileSide.Clicked && saveEditedTiles
                    && Tile.IsTileChanged(previousClickedTile, correctedTile.Value))
                {
                    Tile undoTile = Tile.CreateCloneTile(previousClickedTile);
                    Tile redoTile = correctedTile.Value;

                    tmpUndoTilesList.Add(undoTile);
                    tmpRedoTilesList.Add(redoTile);
                }

                TileInfo info = correctedTile.Value.GetTileInfo();
                Vector2 frames = correctedTile.Value.GetCurrentFrame();

                tile.SetTileInfo(info);
                tile.SetCurrentFrame(frames);
            }
        }
    }

    if (saveEditedTiles && tmpUndoTilesList.Count > 0 && tmpRedoTilesList.Count > 0)
    {
        undoTilesList.Add(tmpUndoTilesList);
        redoTilesList.Add(tmpRedoTilesList);

        currentUndoRedoIndex = undoTilesList.Count - 1;
    }
}

What this code does is in the Foreach, it will loop through all the tiles that have been corrected. If the corrected tile is the clicked tile and it has actually changed, it will add it to the Undo and Redo List. You should ignore the Redo list for now, since the redo functionality is not inplemented yet. i want to get the undo function working first.

So in the last part of the function, I add the new actions to the lists, but again, I think I need to do something else then adding when you are somewhere in the list and not at the end.

Hope you understand what I want.
Thanks!

Answer 1

Generally speaking, you should have a Stack of IMapChange, where IMapChange looks something like this:

public interface IMapChange
{
    //Performs the change on a TileMap
    Boolean PerformChange(TileMap map);

    //Reverts the change on a TileMap
    Boolean RevertChange(TileMap map);
}

You should have a method that is called to make changes:

public void SetTile(Vector2 position, int tileId)
{
    Tile oldTile = Map.GetTile(position);

    Tile newTile = new Tile(position, tileId);

    MapChange change = new MapChange(oldTile, newTile);

    //Only push to cahngestacks if successfull    
    if (change.PerformChange(Map))
    {
        ChangeStack.Push(change);

        //We don't want you to be able to "redo" anymore if you do something new.
        RedoStack.Clear();
    }
}

public void RemoveTile(Vector2 position)
{
    Tile oldTile = Map.GetTile(position);

    Tile newTile = null;

    MapChange change = new MapChange(oldTile, newTile);

    //Only push to changestacks if successfull    
    if (change.PerformChange(Map))
    {
        ChangeStack.Push(change);

        //We don't want you to be able to "redo" anymore if you do something new.
        RedoStack.Clear();
    }
}

Undo can look like this:

public void Undo()
{
    var lastChange = ChangeStack.Pop();

    //Try to revert. If revert fails, put the change back in the stack
    if (!lastChange.RevertChange(Map))
        ChangeStack.Push(lastChange);
    else
        RedoStack.Push(lastChange);
}

and undo like this:

public void Redo()
{
    var lastChange = RedoStack.Pop();

    //Try to perform. If successfull, put back in ChangeStack
    if (lastChange.PerformChange(Map))
        ChangeStack.Push(lastChange);
    else
        RedoStack.Push(lastChange);
}

PerformChange and RevertChange are basicly:

Perform:
- if oldTile is not null, try to remove it from map.
- insert newTile into map.

Revert:
- if newTile is not null, tro to remove it from map
- insert oldTile into map.

Answer 2

The standard expected behavior for Undo is you can Undo an action, then Redo to go back to before you used Undo...unless you perform a new action! The new action deletes all the redo ability.

To help conceptualize (parens shows the current state):

Act1 -> Act2 -> (Act3)

Undo twice gives...

(Act1) -> Act2 -> Act3

Now you could Redo at this point if no new action is taken. Now if the user does a NewAction we get:

Act1 -> (NewAct2)

...and that's it! Act3 is just forgotten now, discarded like yesterday's garbage. The alternative is just too difficult to implement and terribly unintuitive to use!. Like what if you create a tile, change a color, then undo back before tile creation and create a tile somewhere else. If you Redo, does that new tile change color? Does the old tile reappear in the new color? If you undo again, will redo return the first set of edits instead of the last? Yuck!

This is how even complex programs like Photoshop work, so it would be unreasonable to expect a map editor to behave any other way. Many programs don't even support Redo, so it's up to you if you even want to support that! This is just one of those times where one makes things harder on oneself than they are.

Basically, you seem to be good to go as is!