Undo/Redo Design

[stjahns]

The editor needs to be designed with undo/redo in mind. Usually this is done by maintaining a list of Command objects, where each Command object performs some mutation and provides a way to reverse that mutation. Look up 'Command Pattern' if you aren't familiar with this.

For example an 'Add Edge' command object will need to remember the nodes it adds edges between. This could be problematic if the node indices are not constant for a pair of given nodes after nodes are removed. For example, if we add an edge, then remove a node causing the indices to shift, then undo both commands, none of the node indices will be the same.

We'll need some kind of persistent identification for nodes and edges, this might mean writing our own internal graph structure for the editor to operate on, rather than using petgraph.

Thoughts?

[stjahns]

We could add a GUID field to our UiNode and UiEdge structs, but then it would require scanning through the whole list of nodes or edges in order to retrieve a node/edge by its GUID. Maybe the simplicity is worth the inefficiency, as I think the only times that would be necessary is when a change is made to the graph, so it wouldn't be the end of the world.

[stjahns]

I'm not really familiar with what FRP could bring to the table, not sure if it could simplify things or just add more complexity.

[viperscape]

I have to give this some thought, but I think a mix of a command deque and our own uids might work here. Such as, relapsing an add_edge(s,t) would have to check if s and t's uid's match and if not iterate the graph entirely.

[stjahns]

I'm thinking that we are probably going to be better off dropping petgraph as the internal graph implementation, I don't think we are really gaining anything much from it. For example, one thing petgraph does is when removing a node, it will remove all the outgoing edges, which doesn't really help us as we need to keep track of those edges in a 'RemoveNode' command anyway, in order to add them back again on redo.

[viperscape]

We could track edges via vectors storing uids for outgoing and incoming, to be rebuilt if needed. I think you're right though, there are serious snags with petgraph. If we do build a graph lib, we should consider narrowing the scope to directed graphs, among other things I'm sure. Are there any other currently active graph libs?

[stjahns]

Also, I'm not sure how to handle 'Nodes' with multiple different sockets (ie a BlendTree node with 2 input sockets and 1 output socket) with petgraph without awkward workarounds such as "1 node for the node itself, connected to nodes representing each of its sockets", so I'm figuring we are going to need something more specialized in the end anyhow.

[viperscape]

I'll probably reference this issue later in a future post, closing for now