Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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());
                }
            }



        }
share|improve this question
1  
Maybe you can explain the algorithm - in words? –  Byte56 Aug 7 '13 at 0:49
    
Basically, for each point on mouse down, the map grid should be changed and the state should be stored in such that the action is reversible completely. –  Vaughan Hilts Aug 7 '13 at 0:51
    
The problem comes from when multiple actions are overlapped as soon. –  Vaughan Hilts Aug 7 '13 at 0:52
    
It seems like you got cut off there, "overlapped as soon" as soon as what? Also, please edit the question to include the explanation. –  Byte56 Aug 7 '13 at 1:00

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Bingo - you need to store the data that was affected after the fact and not as I go. Why dosen't rewinidiing by pushing as you go work? –  Vaughan Hilts Aug 7 '13 at 5:56
    
I don't understand your question, sorry. –  Sean Middleditch Aug 7 '13 at 6:42
    
If I place the same tile in the same "group" over the same tile without releasing the moue (I build up a stack and push the action as a group) the action ends up getting over-ridden at some point. Placing singular tiles is fine. But the minute I undo, redo, and then undo again - the tile that was the same that placed in the group doesn't undo itself. It's probably a logic error on my part. –  Vaughan Hilts Aug 7 '13 at 6:46
    
I guess the problem is the transformations are applied AS IS - in sequence - but when they're applied to the state manager they come out as a stack. So when you undo, redo, and then try and undo again - the list is backwards now and dosen't execute as expected. I hope I'm clear? –  Vaughan Hilts Aug 7 '13 at 6:47
    
Do what I showed with the history. Undo is not an all new action. You're simply moving an index backward and applying an undo operation. Redo is simply moving the index forward and applying an operation. I think that's what you've got wrong. –  Sean Middleditch Aug 7 '13 at 6:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.