Java более эффективный поиск массива

Question

Я кодирую игру с помощью LibGdx, и у меня есть массив со всеми моими стеновыми объектами, с которыми игрок может столкнуться. Для тех, кто не использует LibGdx, я говорю о классе Array от LibGdx, который обеспечивает те же функции, что и ArrayList, но он построен с учетом эффективности памяти. Когда я проверяю на столкновение, я, чтобы пройти через каждую стену в массиве и проверить столкновения, как это:

for(Wall w : walls) { 
    if(w.bounds().contains(player.bounds()) { 
    // handle collision 
    } 
} 

я понял, что это неэффективно, потому что я иду через все стены, даже если эта стена является выключение текущий вид карты. Очевидно, если я проверяю на столкновение со стенами, находящимися сейчас в окне просмотра камеры (это означает, что они в настоящее время видны игроку), тогда нет смысла проходить через весь массив, потому что игрок не может столкнуться с ними, пока они не войдут в Посмотреть. Я думал о том, чтобы сделать мою игру немного более эффективной, только проверяя на столкновение со стенами рядом с игроком. В моей игре у меня есть все стены, привязанные к сетке с ячейками 32x32 px. Я действительно не знаю, как я мог бы создать более эффективный поиск коллизий. Могу ли я использовать как какую-то карту, которая использует позицию vector2 для своего ключа, а затем просматривает позицию игрока и просматривает стены в определенном диапазоне от позиции игрока на карте? Я просто действительно потерял, как иметь код, который не будет проходить через все 100 стен в моей игре, когда есть только 10 текущих возможных стен, которые игрок мог коснуться из-за того, где он сейчас находится. Есть ли в этом смысл? Может ли кто-нибудь объяснить хороший способ сделать что-то подобное? Спасибо.

Answer 1

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

Вот как я ее решил:

Первое: Сегмент карты на зоны, то есть) нарисовать карту на бумаге или что-то и разрезать его на части..

Во-вторых: Запишите границы пикселей для каждого сегментированного участка карты.

В-третьих: Проверьте, где находится ваше местоположение игроков относительно границ.

Наконец: проверяйте стены только в пределах этих границ.

В царстве бесконечных стен это не какой-либо более эффективным (говоря о Big O), но и для всех практических целей это эффективно при рубке на время подстановок

---

if (boundary1.contains(player1)) { 

    for(Wall w : Boundary1Walls) { 
     if(w.bounds().contains(player.bounds()) { 
      // handle collision 
     } 
    } 
} 
else if (boundary2.contains(player1)) { 

    for (Wall w : Boundary2Walls) { 
     if(w.bounds().contains(player.bounds()) { 
      // handle collision 
     } 
    } 
} 

.... Продолжить таким образом

Обратите внимание ... Я сделал это так, прежде чем поступать в колледж для разработки программного обеспечения, поэтому я не использовал структуры данных, такие как BST, которые могли бы использоваться для хранения стен по отношению к их координаты. Быстрое время поиска.

Answer 2

Есть много алгоритмов столкновения, вам нужно найти тот, который вам подходит.

Одно из решений, которое я могу придумать на верхней части головы:
Сохраните список своих стенок, отсортированный по их координатам. Если вы создаете новую стену, используйте сортировку вставки, чтобы применить массив. Если вы хотите проверить наличие коллизий, возьмите координаты объектов (в данном случае, вероятно, игрок, который работает) и выполните двойной поиск, чтобы найти ближайшую стену для игрока. Затем вычислите, сталкивается ли игрок и эта стена.Если ближайшая стена не вызывает столкновения, вы можете быть уверены, что никакой другой стены не будет.

Answer 3

Каждая стена находится на одной или нескольких этих сетках 32x32px. Пусть координаты сетки равны x и y. Если сетка содержит стенку, ввести это в

HashMap<CoordPair,Set<Wall>> xy2wall 

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

Если сетка 32x32 приводит к слишком большому количеству записей, вы всегда можете использовать более грубую сетку.