4

私は、プレイヤーが入れた石の位置を 2 次元のゲーム フィールドに格納するゲーム (「Qwirkle」と呼ばれています) を作成しようとしていました。最初のプレーヤーは石をどこにでも置き、他のプレーヤーは任意の方向 (左/右/上下) から石に接続できます。ゲームフィールド自体は、ゲームのアイデアを台無しにする固定サイズに制限されていません。ただし、石の数は、プレーヤーが開始時に定義できる値に制限されています。

ゲーム ロジックのため、インデックスを使用して石を for ループする必要があります。ただし、プレーヤーはどの側からでも石を追加できるため、任意の方向 (たとえば、負および正のインデックス方向) に拡張できるリストが必要です。

一度に複数の石をチェックする必要があるため、パフォーマンスは重要ではありません。

最善の方法は、_stones[-3,5] のような石にアクセスして、もちろん -3, 5 の位置にある石にアクセスすることです。

これには、任意の側からプッシュおよびポップできるスタック (PushBack / PushFront など) が役立つと思いましたが、C# でそれを実現する方法がよくわかりません。

私が考えているような事前実装されたリスト/スタックはありますか、それとも私のアプローチは完全に奇妙ですか?

4

5 に答える 5

5

必要なデータ構造は不変の quadtreeです。ボードがほとんど空である場合、不変の quadree を使用すると、本質的にサイズが無制限のボードを表すことができます。1 兆 x 1 兆のセル ボードは、32 x 32 のセル ボードより数バイト多いメモリしか必要としません。不変の四分木は、説明した方法で簡単にインデックスを付けることができ、古い四分木と編集が与えられた新しい四分木を計算するのは簡単です。

私は何年にもわたって不変の quadtree アルゴリズムを何度か書いてきました。長い間、それらについての一連のブログ記事を書くつもりでしたが、一度もしたことがありません。戻ってきたら、この回答を更新します。

その間、ゴスパーのアルゴリズムに関するドブス博士の記事は、不変の四分木がどのように機能するかを学ぶために使用したものです。

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478

于 2013-03-19T16:31:26.210 に答える
2

あなたが望むのは両端のキューです（「デッキ」と発音されるデキューとして知られています）。.NET BCL には (残念ながら) 実装はありませんが、サード パーティの実装があります (Google を参照)。

于 2013-03-19T15:11:31.403 に答える
0

リストのインデックスについて考える代わりに、ディクショナリの整数キーを考えることができます。次元はどうでもいい。

Dictionary<int,Dictionary<int,Stone>> stones = new Dictionary<int,Dictionary<int,Stone>>();
// do some initialisation for the base field size ...

// access it this way
Stone s = stones[-1][-5];

唯一の問題は、リソースを消費する可能性のある 2 番目の次元を追加する場合です (すべての 1 番目の次元を反復処理します)。

于 2013-03-19T15:13:10.117 に答える
0

たとえば、2 つの ArrayList を含むカスタム データ構造を実装することで、より多くのことを学べると思います。1 つは前進し、1 つは後退します。もちろん、あなたの実装ではどちらも同じように進みますが、逆方向の ArrayList の最初の要素に対して -0 のインデックスを取得しないように、実装ではデータ構造に正のインデックスに 1 を加えた否定を返すようにすることができます。 .

問題を誤解しているかもしれませんが、それが双方向の拡張可能なデータ構造を実装する方法です。

幸運を！

于 2013-03-20T09:21:01.790 に答える
-1

次のようなことができます。

_stones[-(i),i] および/または _stones[i,-(i)]

ただの提案です。

于 2013-03-19T15:07:54.673 に答える