5 ms·

This is cool, but I don't understand the justification for why a more traditional "just store a sequence of events" undo system wasn't possible. As the author s

by catern 5y ago

This is cool, but I don't understand the justification for why a more traditional "just store a sequence of events" undo system wasn't possible. As the author says in the post on the scripting system, the game scripts access virtual interfaces. Those could just record the methods called before forwarding them on - doesn't matter that the scripts make arbitrary method calls. It seems to me that there's nothing inherent to "the level script is arbitrary code rather than a list of commands as data" that makes that style of undo impossible.

qsort 5y ago
Well, yes, it does matter, because there's no guarantee that you can safely compute and execute the inverse operation. Same reason debuggers don't have a "step back" button. Strictly from a computation theory point of view, you could obviously store a list of executed opcodes and undo by replaying up to the (N-1)th operation, but I think they want to avoid the overhead.
- johnday 5y ago
  "Forward replay" was actually the mechanism that Tabletop Simulator originally used for its undo system. After around 30 minutes of playing games in the simulator, pressing "Undo" would hang the client and likely disconnect most people connected to the server. It's not a great way to implement undo.
royjacobs 5y ago
It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. This then grows more complex if items have parent-child relationships and you also need to start storing all the information required to completely reinstate all the children, possibly also in the same order they were originally created in. You know, tricky.
- jcelerier 5y ago
  > It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. yep, as soon as you have an object graph serialization is the only way to stay sane. Anecdotally that's what I do in https://ossia.io https://ossia.io with Qt's QDataStream and serializing / deserializing hundreds of steps is pretty much instant. A nice benefit of it is to be able to provide a "restore on crash" feature: the undo/redo stacks get saved to disk and can be used to go back to the exact state the user left if a crash happens
nyanpasu64 5y ago
I came up with a "almost too clever" way to reduce the tedium of writing command objects. Most command APIs expect you to write a separate redo and undo method, and possibly even a separate "apply" method. Instead I created a `BaseEditCommand` interface where each command object subclass precomputes the new state of the altered portions of the document. When the command is applied, the undo system calls `apply_swap(self: &mut dyn BaseEditCommand, &mut Document)` which swaps the Document's old state with the BaseEditCommand's new state. To undo the change, you merely call `apply_swap` a second time, which swaps the old state from the edit command back into the document (saving the document's new state in the edit command). To redo the change, you merely call `apply_swap` a third time. It has the same tradeoffs as the usual command/action pattern (richer information about what was changed, but you have to implement a new type for each operation, and might end up copying a lot of memory anyway). However it's a lot easier to implement each command (less boilerplate, somewhat lower risk of implementing undo/redo incorrectly and altering state). As a bonus, apply/undo/redo perform zero memory allocations, because they only swap data, not copy or destroy it. One arguable downside is that you can't transplant the same command from one point in the history to another (but most undo commands in traditional applications, as opposed to VCS systems or nonlinear editors, aren't built to do that either). And I'm not sure my "can_merge" system (which merely drops commands rather than bundling or intelligently combining their contents) was a good idea, since all mergable commands must alter the same state. API: https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/edit_common.h#L29 https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/...

by catern 5y ago

qsort 5y ago

Well, yes, it does matter, because there's no guarantee that you can safely compute and execute the inverse operation. Same reason debuggers don't have a "step back" button. Strictly from a computation theory point of view, you could obviously store a list of executed opcodes and undo by replaying up to the (N-1)th operation, but I think they want to avoid the overhead.

johnday 5y ago
"Forward replay" was actually the mechanism that Tabletop Simulator originally used for its undo system. After around 30 minutes of playing games in the simulator, pressing "Undo" would hang the client and likely disconnect most people connected to the server. It's not a great way to implement undo.

royjacobs 5y ago

It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. This then grows more complex if items have parent-child relationships and you also need to start storing all the information required to completely reinstate all the children, possibly also in the same order they were originally created in. You know, tricky.

jcelerier 5y ago
> It can be quite tricky to get right once you get into ownership issues. If you delete an item, undo'ing that should reinstate it. So that undo step becomes the owner of the data of the item, otherwise it couldn't reinstate it. This can already become a bit complicated if you're dealing with memory management of this item. Do resources that the item uses get deleted immediately, or do you want to keep them around in your undo state too? If the resource requires a lot of processing then that may be the only option. yep, as soon as you have an object graph serialization is the only way to stay sane. Anecdotally that's what I do in https://ossia.io https://ossia.io with Qt's QDataStream and serializing / deserializing hundreds of steps is pretty much instant. A nice benefit of it is to be able to provide a "restore on crash" feature: the undo/redo stacks get saved to disk and can be used to go back to the exact state the user left if a crash happens

nyanpasu64 5y ago

I came up with a "almost too clever" way to reduce the tedium of writing command objects. Most command APIs expect you to write a separate redo and undo method, and possibly even a separate "apply" method. Instead I created a `BaseEditCommand` interface where each command object subclass precomputes the new state of the altered portions of the document. When the command is applied, the undo system calls `apply_swap(self: &mut dyn BaseEditCommand, &mut Document)` which swaps the Document's old state with the BaseEditCommand's new state. To undo the change, you merely call `apply_swap` a second time, which swaps the old state from the edit command back into the document (saving the document's new state in the edit command). To redo the change, you merely call `apply_swap` a third time. It has the same tradeoffs as the usual command/action pattern (richer information about what was changed, but you have to implement a new type for each operation, and might end up copying a lot of memory anyway). However it's a lot easier to implement each command (less boilerplate, somewhat lower risk of implementing undo/redo incorrectly and altering state). As a bonus, apply/undo/redo perform zero memory allocations, because they only swap data, not copy or destroy it. One arguable downside is that you can't transplant the same command from one point in the history to another (but most undo commands in traditional applications, as opposed to VCS systems or nonlinear editors, aren't built to do that either). And I'm not sure my "can_merge" system (which merely drops commands rather than bundling or intelligently combining their contents) was a good idea, since all mergable commands must alter the same state. API: https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/edit_common.h#L29 https://gitlab.com/exotracker/exotracker-cpp/-/blob/dev/src/...