Ordenação, sweep e poda: algoritmos de detecção de colisão (2023)

 (leanrada.com)
3 pontos por GN⁺ 2024-08-15 | 1 comentários | Compartilhar no WhatsApp

Algoritmos de detecção de colisão

Detecção de colisão

  • Na programação de videogames, a detecção de colisão é um problema muito comum
  • É essencial para impedir que personagens atravessem uns aos outros ou para implementar um motor de física

Abordagem simples 🐥

  • Um método que verifica todos os pares de objetos para confirmar se há colisão
  • Exemplo de código: 
    for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • Esse método tem complexidade de tempo O(n^2)

Problema de desempenho

  • Conforme o número de objetos aumenta, surgem problemas de desempenho
  • Por exemplo, quando n = 20, é preciso verificar 190 pares

Melhorando a solução

  • É importante reduzir trabalho desnecessário
  • Otimização da função intersects(): 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

Otimização por ordenação

  • Se os objetos forem ordenados pela coordenada x, é possível reduzir verificações desnecessárias
  • Exemplo de código: 
    sortByLeft(balls);
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (ball2.left > ball1.right) break;
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

Análise de desempenho

  • Ordenação: O(n log n)
  • Loop interno: em média O(n + m) (m é o total de sobreposições no eixo x)
  • Complexidade de tempo final: O(n log n + m)

Comparação visual

  • Comparação entre a verificação global de pares e a verificação de pares ordenados
  • A verificação de pares ordenados realiza muito menos verificações

Resumo do GN⁺

  • Este artigo trata de como otimizar algoritmos de detecção de colisão no desenvolvimento de jogos
  • Começa com um algoritmo simples O(n^2) e melhora bastante o desempenho por meio da ordenação
  • É uma informação muito útil para desenvolvedores de jogos e engenheiros de software
  • Outros projetos com funcionalidade semelhante incluem Box2D e Bullet Physics

Leituras relacionadas

1 comentários

 
GN⁺ 2024-08-15
Comentários no Hacker News

  • O autor sugere usar algoritmos de ordenação “rápidos” como mergesort ou quicksort para obter desempenho ideal

    • Porém, na prática, algoritmos de ordenação “piores”, como insertion sort, podem apresentar desempenho melhor
    • Os objetos em um sistema de detecção de colisão se movem em passos relativamente pequenos entre os frames, então é possível manter a lista do frame anterior quase ordenada
    • Ao ordenar uma lista quase ordenada assim, insertion sort fica próximo de O(n), enquanto Quicksort fica próximo de O(n^2)

  • Já fizeram algo parecido no passado, mas mantinham listas de índices para cada direção em vez de ordenar

    • Por exemplo, havia 4 listas como objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
    • Quando um objeto se movia horizontalmente, seu índice era atualizado nos arrays leftEdge e rightEdge
    • Durante o movimento, bastava trocar no máximo 1 ou 2 índices

  • Este texto está realmente muito bem organizado

    • Trabalho com desenvolvimento de jogos desde o fim dos anos 90, mas a maior parte disso foi abstraída pelos engines
    • Isso é essencial para entender simulações de sistemas complexos
    • Agradeço ao autor por ter escrito um texto tão acessível

  • Sempre gostei de ler documentação sobre detecção contínua de colisão

  • Gostei do uso de ilustrações

    • Às vezes, esses artigos parecem só uma desculpa para reunir demos bonitas, mas neste texto as ilustrações não dominam o conteúdo

  • Parte 2: https://leanrada.com/notes/sweep-and-prune-2/

  • Foi levantada uma dúvida sobre a afirmação de que “esse algoritmo simples executa em tempo O(n^2) em termos de Big O”

    • O loop externo (i) conta até n - 1, e o loop interno (j) começa em i + 1 e conta cada vez menos elementos
    • Não sou formado em ciência da computação, mas fiquei curioso se, para valores grandes de n, isso é aproximadamente igual a O(n^2) ou se seria menos que isso

  • Houve curiosidade sobre se esse método é semelhante ao uso de quadtree para reduzir colisores em potencial

  • Houve curiosidade sobre se já foi proposto um método de programação linear

  • Este site me distraiu, no bom sentido

    • É divertido e inspirador