   How to implement multiple levels of or unlimited undo/redo?
  I'm working on a tile editor. I want to have more than one level of undo/redo, but I'm not sure what is the best way to go about it.For a single level of undo, I keep a duplicate of the tile map before the current action and with the current action for redo. This works for a single level, but I cannot imagine this is the most efficient way to do this for multiple levels. I certainly don't know how to implement unlimited levels.One option I've thought of would be to keep a record of each user action and every time the redraw the tile map, action by action, until the correct level is reached. Basically creating a pseudo-drawing program. This, however, could wind up being VERY slow. Especially if the user sets hundreds of individual tiles with the pencil tool.How is this typically done? Since this is a painting program, how is this done in a painting program?   
  I find Command Pattern works well (and it's actually mentioned as an example of that wiki page). You'd have something like a base Action class with perform() and rollback() methods. When a user draws/paints/etc. you spawn an action and use it's perform() to do the work, then push it into the undo queue. The undo command then just has to pop the top action off the undo queue and call rollback().The tricky bits are 1. making sure that rollback() restores things to exactly the same state as perform() and 2. deciding how to split your user interaction into atomic actions (ie. whether a series of brush strokes should be lots of individual actions or one big one).   ;  That's exactly how I have attempted to make an undo system before. What you could also do is keep each action as a single Command, as OrangyTang suggested, but instead of rolling back a single Command, rollback a Command Set (simply a list of Commands), so you can still do a long brush stroke as a single Undo command to the user, but under the hood it will be a series of undos.Of course, most of the time each Command Set will consist of only a single Command, but this allows you to really have basic Commands for every single action the user can take, and fill a Command Set, then when you want to Undo, just walk the Command Set in reverse and rollback each command.   ;  You might take a look at sqlite. It is a very light-weight and fast database engine that you can embed in your application. It handles the messy details of transactions which you can leverage off of to easily implement the Command Pattern.   ;Quote:Original post by EndarOf course, most of the time each Command Set will consist of only a single Command, but this allows you to really have basic Commands for every single action the user can take, and fill a Command Set, then when you want to Undo, just walk the Command Set in reverse and rollback each command.You don't need to treat CommandSet any differently - it's just be a regular Command where it's perform() and rollback() would call the corresponding methods in the child Commands.interface Command{ perform(); rollback();}class CommandSet implements Command // or CompositeCommand{  List commands;   perform()  foreach Command c  in commands:   c.perform() rollback()  foreach Command c in commands.reverse():   c.rollback();}Note that you'll have to call rollback() in the reverse order to perform().   ;  How big are these tiles? Programs like paint already implement undo on a pixel by pixel basis, so unless you're working with millions of tiles at a time, you can achieve "unlimited" undo on a modern machine. In practice users won't get to a point where they're likely to run out of RAM. Although it's certainly possible with heavy duty programs like Photoshop.   ;  I posted about undo/redo here a while back.  It's basically along the same lines of what everyone is saying to use commands.  If you're using .NET, then you should definitely follow MJP's example and take advantage of the reflection system to trivially handle undo/redo of just about any property (our GUI editor does this).   ;  Doing it with a command class thing is the right way to do it. The problem with it is that it's hard to implement undo this way after the fact. If you designed your editor from the beginning knowing that you were going to handle undo this way then implementing the command method isn't hard. However, what often happens is that undo/redo isn't in the original spec for the application, or you come into a project that you didn't start, and then when the thing is nearing completion the client or your boss or someone says, "Hey, this editor could really use undo. How long would that take you?". In that situation retrofitting the command pattern can be hard to do. So the easy thing to do in that case is just have your undo and redo stacks contain complete snapshots of the thing being edited. Now, obviously, this isn't practical if the complete state of the thing being edited is huge, but it is 2010 now and machines have lots of memory so unless you're writing photoshop or something, you can often get away with it.   ;Quote:Original post by jwezorekDoing it with a command class thing is the right way to do it. The problem with it is that it's hard to implement undo this way after the fact. If you designed your editor from the beginning knowing that you were going to handle undo this way then implementing the command method isn't hard. However, what often happens is that undo/redo isn't in the original spec for the application, or you come into a project that you didn't start, and then when the thing is nearing completion the client or your boss or someone says, "Hey, this editor could really use undo. How long would that take you?". In that situation retrofitting the command pattern can be hard to do.QFT.  Undo/redo systems are especially difficult to add after the fact (unless you use a brute force approach and save the entire state at each level, which can be problematic for lots of data).  I know from some unfortunate experience [sad]   ;  Command pattern, conceptual stack of commands... if hierarchical command batching is really required, conceptual stack of stack of commands, etc. If what you mean is simply undoing more than the last command, a stack like structure should do. Probably needs to remember "popped" (undone) commands in case of redo, until a new action is performed.   