Going back in time is pretty handy. While no one I know of has ever done this in real life, it’s still useful to know how it’s down in software. And it’s actually a really simple concept. I am a fan of concrete examples, so for the rest of the article we are going to assume that we want to implement un-do in a Tile-Editor.

A classical Tilemap Editor (Tiled)

A Tilemap Editor (Tiled)

The Idea

The first step is to know what we want to be able to undo. In a Tile-Editor you place tiles on the canvas to create a map. When you make a mistake you want to revert back before you placed the tiles down. So here, whenever there is a mouse click on the canvas we will store the current state. When the user presses undo, it will just replace the current state with the stored one.

Of course 1 state is not enough, so we will use a list. Every time the user clicks on the map, we store the state and add it to back of the list. When the user wants to undo, you remove the last item of the list and replace the current state with it. As all us data structure enthusiasts know, a Stack is the perfect fit for this case.

Know your data

The only thing we need to store is the tile IDs. If you are not familiar with the concept of tilemaps: basically each tile has a number that represents what it is.

Screen Shot 2016-07-02 at 18.14.01

These numbers/ints are stored in a plain old array. That makes backing them up really easy. We can take a copy of the array (current map state) and push it onto the stack.

Implementation

We assume that the mapData variable holds the current tile-ids. The following is in pseudocode:

Stack<State> undoStack;

class State {
	Array<Int> tileIds;
};
	
void save_state() {
	State state;
	state.tileIds = copy_array(mapData);
	undoStack.push(state);
}

void restore_state() {
	if (undoStack.empty()) return;
	State state = undoStack.pop();
	mapData = state.tileIds;
}

Now whenever the user clicks on the canvas first, we will call save_state() (). When they press Undo we will call restore_state().

Going further

It’s nice to be able to undo your 1-layer-tilemap. In reality you will have multiple layers, maybe some objects and some other items that don’t even fit in an array. That’s okay though, because we can easily extend the foundation we have build.

Let’s say we want to backup 3 layers. A possible solution would be:

Stack<State> undoStack;

class State {
	Array<Int> tileIds1;
	Array<Int> tileIds2;
	Array<Int> tileIds3;
};

void save_state() {
	State state;
	state.tileIds1 = copy_array(mapDataLayer1);
	state.tileIds2 = copy_array(mapDataLayer2);
	state.tileIds3 = copy_array(mapDataLayer3);
	undoStack.push(state);
}

void restore_state() {
	if (undoStack.empty()) return;
	State state = undoStack.pop();
	mapDataLayer1 = state.tileIds1;
	mapDataLayer2 = state.tileIds2;
	mapDataLayer3 = state.tileIds3;
}

While this works, it uses more memory than needed. We could easily optimize this by just storing the layer we are currently editing. The other layers will stay the same anyway so we don’t need to save it.

Stack<State> undoStack;

class State {
	Array<Int> tileIds;
	Int layer;
};

void save_state() {
	State state;
	state.layer = currentLayer;
	if (currentLayer == 0) {
		state.tileIds = copy_array(mapDataLayer1);
	} else if (currentLayer == 1) {
		state.tileIds = copy_array(mapDataLayer2);
	} else if (currentLayer == 2) {
		state.tileIds = copy_array(mapDataLayer3);
	}
	undoStack.push(state);
}

void restore_state() {
	if (undoStack.empty()) return;
	State state = undoStack.pop();
	if (state.layer == 0) {
		mapDataLayer1 = state.tileIds
	} else if (state.layer == 1) {
		mapDataLayer2 = state.tileIds
	} else if (state.layer == 2) {
		mapDataLayer3 = state.tileIds
	}
	mapData = state;
}

Closing Words

And there you go. A fully functional albeit simple undo system. I implemented this system for Condorra, and it took around an hour. If you want to really go all out on optimization you could compress the state data, or just save the difference between the data (or you could buy more RAM).