Undo/Redo

[sunjay]

https://docs.python.org/2/library/turtle.html#turtle.undo

A per-turtle way to support undoing and then potentially redoing the last actions of a given turtle. Since we only have one turtle per drawing right now, it is fine to maintain just a single undo stack, but the idea is that this feature will eventually work well with multiple turtles (#16) as well.

We can also add something called a "save point" to return an identifier to a particular point in the turtle's state. This can be used to undo/redo the drawing back to a particular point. Then, instead of an undo stack, we could even make an undo graph/tree where you can go back and forth to any arbitrary point in history. Modeling it as a graph is probably a much later extension to what can start as a simpler feature.

This undo/redo functionality is related to the Push & Pop functionality added to this L-systems workshop that uses turtle.

[dvberkel]

The L-systems workshop mentioned in this issue is slightly different from the undo/redo functionality. In the example the turtle is extended with a push and pop function. Push pushes the current state of the turtle, i.e. it's position and heading, onto a stack. Pop set the state of the turtle to whatever comes of the stack.

The functionality is shown below

    fn push(&mut self) {
        let position = self.turtle.position();
        let heading = self.turtle.heading();
        let state = State::new(position, heading);
        self.stack.push(state);
    }

    fn pop(&mut self) {
        let state_option = self.stack.pop();
        if state_option.is_some() {
            let state = state_option.unwrap();
            self.turtle.pen_up();
            self.turtle.go_to(state.position);
            self.turtle.set_heading(state.heading);
            self.turtle.pen_down();
        }

[sunjay]

Ah! That makes sense! Undo/redo is definitely different from that. I wonder if a feature like the push/pop you implemented is useful as part of the turtle crate or better as an extension like the one you implemented.

The undo/redo feature described in this issue is still definitely important. I am happy to provide mentoring for anyone interested in working on it. 😄

[dvberkel]

If push/pop is worthwhile is for you to decide 😃

[sunjay]

Yes! I'll have to think about it more. Thanks for clarifying 😄

[buckle2000]

No, don't use push/pop. Record all state changes in append-only history. If you know the speed of the turtle, you can calculate key frames.

For example, if the turtle moves 1 pixel per second, then this code

   | fd 10
   | undo

creates this history

   |  0s: turtle at (0,0)
   | 10s: turtle at (10, 0)
   | 20s: turtle at (0, 0)

To display the turtle at any given time, you can find two nearest key frames and use linear interpolation to calculate precise location.

PoC: https://github.com/buckle2000/turtle-playback

The following struct supports fd, bk, lt, rt, pu, pd.
https://github.com/buckle2000/turtle-playback/blob/a42d5fd1995a80a00a08e9e622c20b829e64b1d3/src/game.rs#L11-L18

[sunjay]

As part of the new architecture in #173, I made it so that each turtle keeps a list of all the drawings it has created. Those lists of drawings will become the foundation upon which we implement undo/redo. Since multiple turtles are all adding to the display list, we can't just remove the last time and hope it was from the right turtle. These lists give us a way to know exactly which drawing primitive should be removed or re-added.

The work involved in this issue is a bit more complicated now, but definitely still doable if anyone is interested in working on it!