Infinite Undo

smee, build 2

In build 2 of SMEE I focused primarily on undo functionality. I also went ahead and tossed in some RPG Maker 95 tiles I found floating around on the net. I did not ask for permission to rip the tiles, but it's for a good cause! The poor starving map developers wanted a pretty to look at!

Here's a couple tiles in action.

Before getting down and dirty with the undo functionality, I decided to implement mouse dragging for the tile plotting. This was a very small and easy task.

To hook into mouse dragging, I made MapPanel implements the MouseMotionListener interface (in addition to the MouseListener it was already implementing.) Then I added the mouseMoved() and mouseDragged() methods to meet the requirements of the interface.

At this point I could've copy-and-pasted the code directly from mousePressed() into the mouseDragged() method, but copy-and-paste coding is the bane of all programmer-kind! If you're ever going to have two or more occurrences of a bit of code that's used frequently or is non-trivial, break it out into its own method. Every action you perform should have a definitive representative.

With that in mind, I refactored my plotting code into its own method. Formal refactoring texts have names for all the different types of refactorings you can perform on your code, and this particular refactoring is known as Extract Method. I recommend scouting around for some information on refactoring, maybe even grab yourself a book on the topic!

A lot of the common refactorings are quite simple, and you've undoubtedly performed many of them already. Texts on refactoring simply give us a common vocabulary to work with, and enable a more rapid way of thinking about and discussing refactoring with others.

My simple refactoring and a quick test later show me I'm in business! Flowers sprout up in my cursor's wake as I hold a button down and swish my mouse around, pausing every so often for dramatic impact. What immense capability! It's like clicking, but faster!

Then I got over it. Dragging is so last minute, I told myself. It's time to reach for the stars, go for the gold, and kick off every ass for great justice! It was go time.

Undo functionality. That's where the real party was at. After thinking about it for a little while, I dove in. All I needed was to keep a running list of plots. I could do that in an ArrayList since every time I add() an item, the list grows to accommodate me:

Then in my plot() method I could just add a plot to the list each time I change a tile on the map. But how do I represent plots? What kind of information would be needed to undo a plot?

I came up with this little helper class, which I plopped right inside of MapPanel:

public class Plot {
    int x;
    int y;
    int prevtile;
    int tile;
    Plot(int x, int y, int prevtile, int tile) {
        this.x = x;
        this.y = y;
        this.prevtile = prevtile;
        this.tile = tile;
    }
}

I would need to know where the tile was plotted, and the x and y coordinates account for that. I'd also need to know the previous tile at that location so that when I undid the plot I could revert the tile at that location back to its previous state. And of course I'd need to know what tile I had plotted there in the first place so that I could also redo my action after undoing it. Pretty straightforward.

Now I can make a running list of plots!

ArrayList<Plot> history = new ArrayList<Plot>();

Now every time I changed a map tile I would just save the current tile, plot the new tile, then add a new Plot object with all of this information to my history list.

Time for a test! I dump in a little debug statement that gets written out every time I add a plot to my history.

Upon running my app, I notice that I am indeed adding items to my history. But hmm! This output is a little odd. As I drag my mouse across the map I'm seeing lots of duplicates of the same tile getting added to my history! That's no good! I don't want to have to hit undo half a dozen times just to undo each plot! So I get out the magnifying class and a good pipe and conduct my investigations.

Deftly, I withdrew a match from the folds of my cloak and lit my trusty pipe. "We've a mystery on our hands, Johnson," I proclaimed. My associate (that would be Johnson) nodded in agreement, scratching his head and looking quite perplexed indeed.

"Oh come now, Johnson!" I exclaimed. "This is no time for rubbing one's head. Snap out of it!"

At this, Johnson dropped his hand, looking somewhat uncomfortable. Shaking his head in confusion, he quickly threw it up again. "But how could this happen, Shermock? It's beyond me, really. I daresay, I haven't a clue. Not one."

"Elementary, my dear Johnson!" I informed him. "It is a matter of simple scientific pragmatism." Taking a puff or two, I contemplated aloud.

"We know that we do not call plot() many times in succession ourselves. Ergo, we can only conclude that the method from which the call is made is being triggered successively."

Johnson nodded slowly, a question on his lips. "But it's being called from within mouseDragged(), how..."

"Precisely! In point of fact, plots are ultimately made manifest in terms of tile coordinates. And as any Java novitiate will tell you, mouseDragged() deals in pixel coordinates."

Johnson's eyes widened slightly, his head cocked to one side as the truth began to reveal itself.

"To wit, as the cursor traverses the breadth of a single tile, mouseDragged() will be called upon at every pixel increment. Thus, as coordinates are transformed from pixel to tile, it is readily apparent that many a neighboring pixel should reside within the selfsame tile."

Pausing momentarily, I considered these facts. "We may therefore cure our malady through the application of tiles under provision that they vary in type from that of the tile beneath our cursor."

Nodding in satisfaction, I resumed a steady puffing.

Johnson was beside himself. "Good show, man! Good show! You've done it again, as I knew you would! Not a moment's worry."

Eyeing him askance through the billowing haze, some small amusement in my eyes, I wave my pipe and nod. "Indubitably, Johnson. Indubitably."

So, the culprit was mouseDragged() being called on a per-pixel basis when I was really only interested in new plots on a per-tile basis.

I could keep track of the last set of tile coordinates that was plotted to, but that seems a little more complicated than I want to bother with. Luckily, as Shermock has pointed out, I can simplify the plotting process by the following rule: only plot at the current location if the tile is different than the tile I'm plotting with.

This is very easy to check for, as well as understand, so I go ahead and implement! Then another test. This time around, as I'm dragging I notice items being added to my history, but if I wiggle around inside one tile I don't get a bunch of additional additions to the history. Mah-vellous!

Now that I've got plots in my history, I wanna be able to undo them. This calls for an undo() method! So I drop one into MapPanel and hammer away.

The last action will always be the last item in my history, so I can just remove() the last plot in the list and then use the "previous tile" indicated in the Plot to apply to the map at the correct location. A few tweaks and I'm ready to test.

But I need some way to trigger a call to undo()! As CTRL+Z is the standard (Windows) shortcut for undo operations, I write up a KeyListener that'll detect CTRL+Z, and I place a call to undo() inside the intercepting block.

Upon testing, I can't seem to get CTRL+Z to do anything. I double check my code, and a moment later it dawns on me that I need to call addKeyListener() on my MapPanel in order to install it! Duh. I can't tell you how many times I've forgotten that though. But I'm testing frequently, so it's an easy catch!

I make the fix and run again. Still nothing. In the back of my mind, some random bit of information I remember reading about component focus surfaces. Ah, I probably just need to request focus. I do so and run again. But still nothing!

Turns out JPanels don't accept focus by default! Which I determine after a debug printout of isFocusable(). I proceed to setFocusable(true); and run again. I plot a few tiles and hit CTRL+Z... and my last plot disappears! I hit it again, and another one goes!

In my excitement I hold down CTRL+Z and watch my tiles being to vanish rapidly. I am then I am abruptly met with a large red exception in my Eclipse console, just as the last of them fly into the ether. Ack! What happen!

Examining the stack trace tells me I've got an IndexOutOfBoundsException on my hands. Ahhh, yes. It would help if I made sure my history had some plots in it before I tried to remove them! Another simple fix and I'm merrily on my way.

Now for redo()!

...you know what. I probably shouldn't be removing each action as I undo it. Good one, dude!

I guess I need to keep track of them all so I can move back and forth in the list, undoing and redoing as often as I please. In order to do this, I'll need to grow the history as necessary, but also track my current position in the history. Initially that position will always be at the end. But as soon as I start undoing actions I'll be moving backward toward the head of the history.

I stuff in an int history_position;. That'll do the trick. And pretty soon I'm undoing and redoing like you wouldn't believe. Backwards, forwards, hell I could probably undo what I ain't never done did, if'n I wanted!

After a bunch of testing I realize if I plot a bunch of tiles, then undo them all and plot a new tile, then hit redo... I can still redo almost all of those other tiles I had plotted! That's a little goofy since my first plot after undoing everything has just overwritten the first stored plot in the list (since I don't remove() plots while undoing them now.)

Standard behavior for undo is that if you undo a bunch of stuff, or just some of it, and then perform another undoable action, you can't redo any of the other actions past that point. Might take a minute to grasp, but it's a sound principle. I could do a bunch of checks to help enforce this rule, but the easiest way to enforce this is to whip out remove() again and just zap the rest of the plots from the history, starting at the current position. At that point there's no way you could redo "stale" plots even if you wanted! I implement this and give it the testing it deserves.

Think that just about does it! Only annoying thing is, I've got a bunch of undo code cluttering up my MapPanel class now. Which isn't so bad, but it just feels not quite so creamy. I'd say it's high time for another refactoring of some sort!

An "undo history" should know how to manage itself, so I go ahead and create a separate class to model an undo history, which I name PlotHistory. I go ahead and break out Plot into it's own file too. It isn't dependent on MapPanel or PlotHistory, so there's no reason to have it nested within either class.

About five minutes later I've got all of the undo functionality moved out and into PlotHistory. I've also replaced all the guts of undo history management removed from my MapPanel class and replaced with an instance of PlotHistory and a few calls to it in the appropriate locations.

A small scuffle I ran into after refactoring this code is that my undo and redo keystrokes appear to be producing the correct debug output, but nothing is updating in my viewport! Even after I resize the window to force a full repaint.

The offending code turned out to be at the point I was adding Plot objects to the history. Originally, before refactoring, I would read the previous tile, then overwrite with the new tile. Then I'd pass this info on to the Plot object that I stuff into the history.

However, now that code was moved into a method in PlotHistory, and I would have to pass the previous tile as an argument to its add() method, which takes my arguments and creates a Plot object itself.

For some reason I didn't want to add another argument to the method call at the time, since I like to keep method calls taking as few arguments as necessary, so instead I passed my MapPanel into the constructor of PlotHistory so I could get the panel's Map and query the previous tile at the given location without relying on an argument being passed into add() every time.

Problem is, I get the previous tile and compare it against the new tile in MapPanel where the actual plot takes places. Once I do that check and know the tiles aren't the same, I do the plot. Then I add that plot to the history. So by the time PlotHistory got around to querying the Map for it's previous tile at the given location, it was already set to the new tile. The map was getting repainted, but PlotHistory didn't know any better than to plot the same tiles as were already present!

What hijinix I do get up to! Everything seemed to be well-behaved from that point onward, so now I offer it up for your scrutiny!

Next post will cover the addition of a tile selector so you can actually pick the tiles you're interested in plottting. Won't that be nice.

I'll probably start being a little less verbose. Unless some of you out there appreciate the step by steps. Some are more insightful than others, and it certainly takes a while to cover features in this much detail. I could crank out more code with less yappin', if it is so desired!

Drop a comment in the offering cup and let me know what you think!