1

ターンベースのヘックスグリッドゲームを作っています。プレイヤーはユニットを選択し、ヘクス グリッド上を移動します。グリッド内の各タイルは特定の地形タイプ (例: 砂漠、丘、山など) であり、各ユニット タイプは、地形上を移動する際に異なる能力を持っています (例: 山を簡単に移動できるものもあれば、移動が難しいものもあれば、移動が難しいものもあります)。全くない）。

各ユニットには移動値があり、各タイルはその地形タイプとユニット タイプに基づいて一定量の移動を行います。たとえば、戦車は砂漠を移動するのに 1、沼地を移動するのに 4 のコストがかかり、山を越えて移動することはできません。飛行ユニットは、1 のコストですべての上を移動します。

私が抱えている問題は、ユニットが選択されたときに、ユニットがどこに移動できるかを示す周囲の領域を強調表示したいということです。その情報に基づいてタイルを作成します。

これを再帰関数で動作させたところ、計算に時間がかかりすぎることがわかりました。関数をスレッドに移動して、ゲームをブロックしないようにしましたが、スレッドが可動領域を計算するのに約 2 秒かかります。 100 万回以上の再帰があり、明らかに問題があります。

この問題を最適化する方法について、誰かが賢いアイデアを持っているかどうか疑問に思っています。

これが私が現在使用している再帰関数です（そのC＃btw）：

private void CalcMoveGridRecursive(int nCenterIndex, int nMoveRemaining)
{
    //List of the 6 tiles adjacent to the center tile
    int[] anAdjacentTiles = m_ThreadData.m_aHexData[nCenterIndex].m_anAdjacentTiles;

    foreach(int tileIndex in anAdjacentTiles)
    {
        //make sure this adjacent tile exists
        if(tileIndex == -1)
            continue;

        //How much would it cost the unit to move onto this adjacent tile
        int nMoveCost = m_ThreadData.m_anTerrainMoveCost[(int)m_ThreadData.m_aHexData[tileIndex].m_eTileType];

        if(nMoveCost != -1 && nMoveCost <= nMoveRemaining)
        {
            //Make sure the adjacent tile isnt already in our list.
            if(!m_ThreadData.m_lPassableTiles.Contains(tileIndex))
                m_ThreadData.m_lPassableTiles.Add(tileIndex);

            //Now check the 6 tiles surrounding the adjacent tile we just checked (it becomes the new center).
            CalcMoveGridRecursive(tileIndex, nMoveRemaining - nMoveCost);
        }
    }
}

再帰の終わりに、m_lPassableTiles には、ユニットが到達できる可能性のあるすべてのタイルのインデックスのリストが含まれており、それらは光ります。

これはすべて機能しますが、時間がかかりすぎます。これに対するより良いアプローチを知っている人はいますか？

4

2 に答える 2

0

ご存知のように、再帰関数を使用すると、問題をできるだけ単純にしたいと考えます。これはまだ一度に噛み切りすぎているように見えます。いくつかの考え：

  1. HashSet構造体を使用して保存してみてくださいm_lPassableTiles。この方法でその状態を回避できますがContains、これは一般にコストのかかる操作です。

  2. 頭の中でこれのロジックを十分にテストしていませんが、foreachループの前に基本的なケースを設定していただけますか? つまり、それはnMoveRemaining == 0？

  3. プログラムが内部でどのように設計されているかを知らなくてm_anAdjacentTilesも、とにかく既存のタイルのみが含まれていると予想されるため、そのチェックを削除できます ( tileIndex == -1)。パフォーマンスが大幅に向上するわけではありませんが、コードが単純になります。

ちなみに、シヴィライゼーション V のように、これを行うゲームは、ユーザーがユニットを特定の場所に移動する意図を示唆した場合にのみ、移動コストを計算すると思います。つまり、タイルを選択すると、それが何回移動するかが表示されます。これははるかに効率的な操作です。

もちろん、ユニットを移動すると、周囲の土地が表示されますが、ユニットが1回の「ターン」で移動できる範囲の土地しか表示されず、移動するにつれてさらに多くの土地が表示されると思います. いくつかのターンを未知の領域に移動することを選択した場合は、慎重に監視するか、一度に 1 ターンずつ実行することをお勧めします。:)

（後で...）

...待って、100万回の再帰？ええ、それは正しい計算だと思います: 6^8(8 は利用可能な動きです) -- しかし、あなたのグリッドは本当にそんなに大きいですか? 1000x1000? そのユニットが実際に移動できるタイル数は? さまざまな地形タイプを想定すると、特定の方向に平均して 4 つまたは 5 つになるでしょうか。

私が間違っている場合は訂正してください (あなたの基本的な設計がわからないため)。すでにチェック済みの隣接するタイルの隣接するタイルをチェックしています。無限再帰からあなたを救う唯一のことは、残りの動きをチェックすることだと思います。

タイルが に追加さm_lPassableTilesれたら、関数に受け取った隣接するタイルのリストから削除します。あなたはあなたのラインで似たようなことをやっていますContains...if再帰呼び出しを含めるためにそのステートメントを追加した場合はどうなりますか? これにより、再帰呼び出しが100万回以上から...せいぜい数千回に削減されるはずです。

于 2012-06-25T04:00:25.317 に答える
0

皆さん、ご意見ありがとうございます。再帰関数をダイクストラのアルゴリズムに置き換えることでこれを解決しましたが、完全に機能します。

于 2012-06-26T08:07:13.767 に答える