本記事は C# Advent Calendar 2019 16日目の記事です。
はじめに
ゲーム制作に人間性を捧げているyoship1639です。
皆様C#の進捗具合はいかがでしょうか。
ゲーム制作をしているとデータや操作の履歴を保持したくなる時がありますよね。例えば、パズルゲームとか。
Undo, Redo機能を持つコレクションを自作もしくは類似の操作を行う処理を記述しなければならないので意外と面倒な奴です。
そこで、過去のデータや操作履歴をUndo, Redoしたい時にメソッド一つで使えるジェネリックに対応させた汎用コレクションクラス History を実装してみたので、その機能、アルゴリズム、ソースコードを紹介したいと思います。
Historyが持つべき機能
目標とするのは操作一つで履歴の操作を行えることです。
履歴を持つだけなら単純にListで良いですが、その操作履歴を時系列で復元するには、Undo, Redoに相当する処理が含まれていなければなりません。なので、最低限必要な機能としては履歴の追加をするPush、Undoに相当するBack、Redoに相当するForwardが求められます。それに加え、コレクションとしての機能(foreachなど)も必要なのでIEnumerable、Linq機能も欲しいのでIEnumerable<T>、クローンもできるようICloneableをそれぞれ実装します。
Push
Pushは簡単そうでちょっと考えなければなりません。単純にデータを追加するだけだと、Redoでindexが先頭でない場合に操作履歴が破綻してしまいます。そのため、以下の手順で履歴をpushします。
- index以降の履歴を削除する
- データをaddしindexを1進める
これで、不具合なく履歴を追加することができます。
Back
Backは操作履歴を1つUndoするので、今回の場合はindex--を行うだけでokです。
indexが0になったらこれ以上Backできないようにします。
Forward
Forwardは操作履歴を1つRedoするので、Backと同様index++だけでokです。
indexがCount-1に到達したらForwardできないようにします。
IEnumerable、IEnumerable<T>、ICloneableは実装部分で紹介します。
Historyを実装する
上記の機能を順次実装します。保持するデータは汎用でなければならないのでジェネリッククラスです。
まず最低限のひな型として、操作履歴位置であるindex、操作履歴をもつlist、コンストラクタを準備します。データなしの状態だとindexは-1を指すことになるので、初期値を挿入できるコンストラクタを記述しておきます。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
public class History<T>
{
private List<T> list = new List<T>();
private int index = -1;
public History() {}
public History(T firstValue)
{
list.Add(firstValue);
index++;
}
}
Pushの実装
前章で説明した要領で実装します。
public void Push(T value)
{
if (index < list.Count - 1)
{
list.RemoveRange(index + 1, list.Count - 1 - index);
}
list.Add(value);
index = list.Count - 1;
}
Back, Forwardの実装
それぞれ、indexが破綻しない状態の場合にindexを操作し、その位置のデータを返します。破綻していたらこれ以上操作できないというthrowを吐かせてもいいですが、今回はとりあえずdefault valueを返します。
public T Back()
{
if (index > 0)
{
index--;
return list[index];
}
return default;
}
public T Forward()
{
if (index < list.Count - 1)
{
index++;
return list[index];
}
return default;
}
At, Peek, Clear、インデクサの実装
上記だけだと使い勝手が悪いので、指定indexのデータを返すAt、先頭のデータを返すPeek、データを全削除するClear、さらにlistみたいに扱えるインデクサを実装します。
public T this[int index]
{
get
{
return list[index];
}
}
public T At(int index)
{
if (index < 0 || index >= list.Count)
{
return default;
}
this.index = index;
return list[index];
}
public T Peek()
{
if (index > 0)
{
return list[index - 1];
}
return default;
}
public void Clear()
{
var first = list[0];
list.Clear();
list.Add(first);
index = 0;
}
最低限必要なプロパティの実装
このままだと要素数とかインデックスの位置がわからないのでプロパティで設定できるようにしてあげます。
public int Count => list.Count;
public int Index { get; set; }
public T CurrentValue => list[Index];
public bool EnableUndo => Index > 0;
public bool EnableRedo => Index < list.Count - 1;
IEnumerableの実装
IEnumerableは要素アクセスができるコレクションとしての機能を保証するインタフェースで、これを実装していないとforeachでループさせることができません。Historyはコレクションとしての最低限の機能を実装する予定なのでこれを実装します。
特段Enumeratorを実装する必要はなく、listがもつenumeratorをそのまま返してあげます。これでIEnumerableは実装できました。
public IEnumerator GetEnumerator()
{
return list.GetEnumerator();
}
IEnumerable<T>の実装
IEnumerable<T>はジェネリックコレクションが実装できるインタフェースで、これを実装するとlinq系の機能、拡張メソッドが使えるようになります。例えばWhereとかSkipとかですね。
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return list.GetEnumerator();
}
実はIEnumerable<T>はIEnumerableを継承しているので後でIEnumerableは削除しましょう。
ICloneableの実装
コレクションのコピーはよく行う操作なのでICloneableも実装してあげます。
public object Clone()
{
var history = new History<T>();
history.Index = Index;
history.list = list.ToList();
return history;
}
これで一通りの機能は実装できました。
Historyのソースコード
今回実装したHistoryのソースコード全文です。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
public class History<T> : IEnumerable<T>, ICloneable
{
private List<T> list = new List<T>();
public int Count => list.Count;
public int Index { get; set; }
public T CurrentValue => list[Index];
public bool EnableUndo => Index > 0;
public bool EnableRedo => Index < list.Count - 1;
public T this[int index]
{
get
{
return list[index];
}
}
public History(T firstValue)
{
list.Add(firstValue);
Index++;
}
public History() { }
public void Push(T value)
{
if (Index < list.Count - 1)
{
list.RemoveRange(Index + 1, list.Count - 1 - Index);
}
list.Add(value);
Index = list.Count - 1;
}
public T Back()
{
if (Index > 0)
{
Index--;
return list[Index];
}
return default;
}
public T At(int index)
{
if (index < 0 || index >= list.Count)
{
return default;
}
this.Index = index;
return list[index];
}
public T Forward()
{
if (Index < list.Count - 1)
{
Index++;
return list[Index];
}
return default;
}
public T Peek()
{
if (Index > 0)
{
return list[Index - 1];
}
return default;
}
public void Clear()
{
list.Clear();
Index = -1;
}
public IEnumerator GetEnumerator()
{
return list.GetEnumerator();
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return list.GetEnumerator();
}
public object Clone()
{
var history = new History<T>();
history.Index = Index;
history.list = list.ToList();
return history;
}
}
Historyの使い方
Historyはこんな感じに使えます。
var history = new History<int>();
// 何らかの操作をして0, 1, 2が追加されたと仮定する
history.Push(0);
history.Push(1);
history.Push(2); // indexは2を指す
Debug.Log(history.CurrentValue); // index=2なので2が返る
history.Back(); // Undo
Debug.Log(history.CurrentValue); // index=1なので1が返る
Debug.Log(history.Back()); // Back自身も値を返す、index=0なので0が返る
Debug.Log(history.Forward()); // Forwardで1が返る
Debug.Log(history.Forward()); // Forwardで2が返る
foreach (var value in history)
{
Debug.Log(value); // コレクションとしても使える
}
Debug.Log(history.Where(x => x % 2 == 0).Count()); // linqも使える
これだけだとありがたみがあまり感じられませんが、ジェネリックなので構造体やクラスを記録することができるため、いろんな場面で使えます。
終わりに
Undo、Redoが必要な場面で実際に使ってみてけっこう使えたので、UnityEngineやSystem.Collectionにデフォルトで組み込んであると嬉しいな～と思いました。
まだまだ足りない機能が多いので、もっと拡張していってもいいかもしれません。（Remove系とか）
本領を発揮するのは複雑な操作履歴データを扱う時なので、ぜひご活用いただければと思います！
それでは。