ときどき私は、いくつかのテキストエディタができるように、イラストレーションソフトがすべてのアンドゥ状態を保存してくれたらいいのにと思うことがある。Emacsのような通常の状態保持アンドゥでは、アンドゥ操作はアクションとしてカウントされるため、アクションをやり直すには、他のアクションを実行し、その後、望む状態に戻るまでアンドゥする必要がある。基本的に、やり直しのアクションを実行するには、それまでのアンドゥのアクションを元に戻さなければなりません。このため、望む状態に到達するまでに何度もアンドゥをしなければならなくなることもあるが、ツリー構造として表現することもでき、枝をクリックしてさまざまな過去や分岐点を調べることができる。例として添付の図をご覧ください（わかりにくいかもしれません
しかし、上記の動作は、イラストレーションソフトにより最適化されるように修正できると思う。アンドゥを状態を変更する操作として扱わず、リドゥ操作を導入するのだ。元に戻す操作は状態を後戻りさせ、やり直し操作は前方に移動させる。しかし、他の新しいアクションはステートの最後に置かれ、その位置が現在のステートになります。例として、添付の2番目の図をご覧ください⬆️ 。これはツリー構造でも表現できると思います。
3つ目のオプションは、誰もが慣れ親しんでいるようにソフトウェアが動作するだけで、裏では上記の動作のいずれかを実行し、ユーザーが別の失われたように見える枝に戻りたいときにツリー構造を表示するというものです。
すべての例で、私は正方形を描き、それを三角形に変え、前に描いた正方形に戻り、また三角形に戻したい。
こちらのトゥート拝見したのですが、アンドゥを木構造で管理する発想はとても面白いですね！
私は趣味でソフトフェア開発をしている者なのですが、こちらの内容について僭越ながら私の意見も置いておきます。
まず、既存のソフトウェアの実装についての考察ですが、多くのソフトは図2の実装が近いと思います。
しかし、UNDO後のDRAWの動作については図とは少し違い、4番目のACTIONが追加されるときに1～3番目のACTIONについては破棄される動作になる実装が多いと考えています。（実際私が開発するソフトウェアではそのようにしています）
これは4番目のACTIONが追加されるときに1～3のACTIONが（リストで管理する場合）利用されなくなることが確定するためです。
また、すべてのアンドゥ状態を保存する点についてはメモリ使用量の問題もあります。
ペイントソフトでは多くの場合ACTIONには、描画前と描画後の画像データを含めると思われますが、それを際限なく保存してしまうとメモリ使用量も増えてしまうので、基本的にACTIONのスタックには上限が設けられています。
対策としては古いACTION同士についてはマージして容量を減らすことで保存できるACTIONを増やすことができそうです。
すでにご存知の内容でしたら失礼しました。
@CharNoe 詳細な回答をありがとう！アクションのマージは面白いアイデアですね。
言い忘れていたのですが、描画ソフトや編集ソフトのコンテキストでは、ステートはイミュータブルであるべきだと思います。そうすることで、部分構造の共有を利用し、メモリフットプリントを減らし、多くのステートを保持できるようになります。たとえば、小さなタイルで表現されるキャンバスを考えてみよう。そして、描画後に変更されなかったタイルは、次の状態のために同じメモリ位置を指し示したままになる。タイルを変更する場合、そのタイルのメモリのコピーがアクションの間編集可能にされ、アクションが終了すると、タイルは不変にされ、不変のルックアップテーブル（ツリー構造で表されることもある）に挿入される。挿入操作は、実際にはテーブルの新しい浅いコピーを作成する。作成されるステートの多くは、毎回少量のタイルやデータにしか影響しないという前提である。
もうひとつできることは、非常に古いステートをディスクにシリアライズし、そのファイルにかなり大きな制限をかけることである（できればユーザーが設定できる