Оптимизация движения по гекс сетке

Я делаю пошаговую гекс-сетку. Игрок выбирает юниты и перемещает их по гекс-сетке. Каждая плитка в сетке относится к определенному типу местности (например, пустыня, холмы, горы и т. Д.), И у каждого типа юнитов есть разные способности, когда речь идет о перемещении по местности (например, некоторые могут легко перемещаться по горам, некоторые с трудом, а некоторые не за что).

У каждого юнита есть значение движения, и каждый тайл занимает определенное количество движения в зависимости от его типа местности и типа юнита. Например, 1 танк стоит за пустыню, 4 за болото и не может двигаться по горам. Где, как летающий юнит, перемещается по всему, стоимость 1.

У меня проблема в том, что когда выбран юнит, я хочу выделить область вокруг него, показывающую, где он может двигаться, это означает проработку всех возможных путей через окружающие гексы, сколько движений займет каждый путь и освещение плитки на основе этой информации.

Я получил это, работая с рекурсивной функцией, и обнаружил, что вычисление заняло слишком много времени, я переместил функцию в поток, чтобы она не блокировала игру, но потоку для вычисления подвижной области требуется около 2 секунд. блок с ходом 8. Его более миллиона рекурсий, что, очевидно, проблематично.

Мне интересно, есть ли у кого-нибудь умные идеи о том, как я могу оптимизировать эту проблему.

Вот рекурсивная функция, которую я сейчас использую (ее 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 содержит список индексов всех плиток, которых может достичь юнит, и они сделаны светящимися.

Это все работает, это занимает слишком много времени. Кто-нибудь знает лучший подход к этому?

Источник

2 ответа

Решение

Благодарность за вклад каждого. Я решил это, заменив рекурсивную функцию алгоритмом Дейкстры, и она отлично работает.

Источник

Как вы знаете, с помощью рекурсивных функций вы хотите максимально упростить задачу. Это все еще похоже на то, что он пытается откусить слишком много сразу. Пара мыслей:

  1. Попробуйте использовать HashSet структура для хранения m_lPassableTiles? Вы могли бы избежать этого Contains Таким образом, это дорогостоящая операция.

  2. Я не слишком тщательно проверил логику этого в своей голове, но не могли бы вы установить базовый вариант до того, как foreach цикл? А именно, что nMoveRemaining == 0?

  3. Не зная, как ваша программа разработана внутри, я бы ожидал m_anAdjacentTiles в любом случае содержать только существующие плитки, так что вы можете устранить эту проверку (tileIndex == -1). Не огромный прирост производительности, но делает ваш код проще.

Между прочим, я думаю, что игры, которые делают это, как Civilization V, только рассчитывают затраты на перемещение, поскольку пользователь предлагает намерение переместить юнит в определенное место. Другими словами, вы выбираете плитку, и она показывает, сколько ходов потребуется. Это гораздо более эффективная операция.

Конечно, когда вы перемещаете юнит, раскрывается окружающая земля - ​​но я думаю, что она раскрывает землю только настолько, насколько юнит может двигаться за один "ход", тогда больше раскрывается по мере движения. Если вы решите перенести несколько поворотов на неизвестную территорию, вам лучше внимательно следить за этим или делать это по одному за раз.:)

(Потом...)

... подождите, миллион рекурсий? Да, я полагаю, это правильная математика: 6^8 (8 доступных движений) - но действительно ли ваша сетка настолько велика? 1000x1000? Сколько плиток может пройти этот юнит? Может быть, 4 или 5 в среднем в любом заданном направлении, принимая разные типы местности?

Поправьте меня, если я ошибаюсь (поскольку я не знаю ваш базовый дизайн), но я думаю, что происходит некоторое совпадение... значительное совпадение. Это проверка соседних плиток соседних плиток уже проверена. Я думаю, единственное, что спасает вас от бесконечной рекурсии, это проверка оставшихся ходов.

Когда плитка добавлена ​​в m_lPassableTilesудалите его из любого списка соседних плиток, полученных в вашу функцию. Вы вроде делаете что-то подобное в своей линии с Contains... что если вы аннексировали это if Скажите включить ваш рекурсивный вызов? Это должно сократить ваши рекурсивные вызовы с миллиона + до... тысяч максимум.

Источник
Другие вопросы по тегам