Выполнение обнаружения столкновений более эффективно

Question

Я работаю над HTML5-холстом, где карта случайным образом генерируется 10px на 10px плитки, которые игрок может затем выкопать и использовать. Плитки хранятся в массиве объектов, а небольшая карта содержит около 23000 плиток. Моя функция обнаружения столкновений проверяет позицию игроков против всех неэфирных плит, которые выполняются каждый раз (с использованием requestAnimationFrame()), и она отлично работает, но я чувствую, что это интенсивность процессора. Функция коллизий следующим образом (код пришел из онлайн учебника):

function colCheck(shapeA, shapeB) { 
    var vX = (shapeA.x + (shapeA.width/2)) - (shapeB.x + (shapeB.width/2)), 
    vY = (shapeA.y + (shapeA.height/2)) - (shapeB.y + (shapeB.height/2)), 
    hWidths = (shapeA.width/2) + (shapeB.width/2), 
    hHeights = (shapeA.height/2) + (shapeB.height/2), 
    colDir = null; 

    // if the x and y vector are less than the half width or half height, they we must be inside the object, causing a collision 
    if (Math.abs(vX) < hWidths && Math.abs(vY) < hHeights) {   
     // figures out on which side we are colliding (top, bottom, left, or right)   
     var oX = hWidths - Math.abs(vX),    
      oY = hHeights - Math.abs(vY);   
     if (oX >= oY) { 
      if (vY > 0) { 
       colDir = "t"; 
       shapeA.y += oY; 
      } else { 
       colDir = "b"; 
       shapeA.y -= oY; 
      } 
     } else { 
      if (vX > 0) { 
       colDir = "l"; 
       shapeA.x += oX; 
      } else { 
       colDir = "r"; 
       shapeA.x -= oX; 
      } 
     } 
    } 
    return colDir; 
}; 

Тогда в моей функции обновления я запускаю эту функцию с игроком и плитками в качестве аргументов:

for (var i = 0; i < tiles.length; i++) { 
    //the tiles tag attribute determines rendering colour and how the player can interact with it ie. dirt, rock, etc. 
    //anything except "none" is solid and therefore needs collision 
    if (tiles[i].tag !== "none") { 
     dir = colCheck(player, tiles[i]); 
     if (dir === "l"){ 
      player.velX = 0; 
      player.jumping = false; 
     } else if (dir === "r") { 
      player.velX = 0; 
      player.jumping = false; 
     } else if (dir === "b") { 
      player.grounded = true; 
      player.jumping = false; 
     } else if (dir === "t") { 
      player.velY *= -0.3; 
     } 
    } 
}; 

Так что я нахожусь интересно, если я только проверю плитки на определенном расстоянии от игрока, используя условие вроде Math.abs(tiles[i].x - player.x) < 100 и то же самое для y, должно ли сделать код более эффективным, потому что он будет проверять столкновение против меньшего количества фрагментов или или менее эффективно проверять дополнительные параметры?

И если это трудно сказать без тестирования, как мне найти, насколько хорошо работает мой код?

Answer 1

, но я чувствую, что это ресурсоемкие

процессора предназначены, чтобы сделать много вещей очень быстро. Существует математика для определения эффективности вашего алгоритма, и кажется, что ваша текущая реализация - O (n). Если вы уменьшите количество плиток до постоянного числа, вы достигнете O (1), что лучше, но может быть не заметно для вашего приложения. Для достижения O (1) вам нужно будет сохранить индекс X ближайших плит и инкрементно обновлять индекс при изменении ближайших фрагментов. То есть если игрок переместится вправо, вы измените индекс так, чтобы левый самый столбец плиток был удален, и вы получите новый столбец плиток справа. При проверке на столкновении вы просто перебираете фиксированное количество плиток в индексе вместо всего набора плиток.

... должен ли сделать код более эффективным, потому что он будет проверять столкновение против меньшего количества плиток или или менее эффективно проверять дополнительные параметры?

Лучший способ ответить на это с помощью профилировщика, но я ожидаю, что это улучшит производительность, особенно на больших картах. Это будет решение O (n), потому что вы по-прежнему выполняете итерацию по всему набору плиток, и вы можете себе представить, как ваш набор плиток приближается к бесконечности, производительность снова начнет ухудшаться. Ваше предлагаемое решение может быть хорошим компромиссом между предложенным мной решением O (1).

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

Как я могу найти, насколько хорошо работает мой код?

Лучшим способом оптимизации кода является attach a profiler и измерять, какие части вашего кода являются наиболее интенсивными с процессора.Когда вы выясните, какая часть вашего кода слишком медленная, либо определите решение самостоятельно, либо перейдите к https://codereview.stackexchange.com/ и спросите очень конкретную информацию о том, как улучшить раздел кода, который не работает хорошо, и включить информацию о профилировщике и связанный раздел кода.

Answer 2

В ответ на ответ Самуила предлагая Я использую профилировщика:

С картой, составленной из ~ 23 000 плиток в массиве: Исходный код столкновение было время работает 48%. Изменив if (tiles[i].tag !== "none") на следующее количество времени, проведенное для проверки коллизий, снизилось до 5%.

if (tiles[i].tag !== "none" 
    && Math.abs(tiles[i].x - player.x) < 200 
    && Math.abs(tiles[i].y - player.y) < 200) 

С картой, составленной из ~ 180 000 плиток: Исходный код столкновения был запущен 60-65% времени и производительность игры настолько мала, что не может быть воспроизведен. С обновленным кодом функция столкновения работает только 0,5% времени, но производительность по-прежнему низкая, поэтому я бы предположил, что хотя меньшее количество фрагментов проверяется на наличие конфликтов, существует так много фрагментов, которые проверяют их положение относительно игрока. игра для работы медленно.