▲
neo 3달전 | parent | favorite | on: GN⁺: 정렬, 스윕, 가지치기: Collision Detection Algorithms (2023)(leanrada.com)
Hacker News 의견

  • 저자는 최적의 성능을 위해 mergesort나 quicksort 같은 "빠른" 정렬 알고리즘을 사용할 것을 제안함

    • 그러나 실제로는 insertion sort 같은 "덜 좋은" 정렬 알고리즘이 더 나은 성능을 보일 수 있음
    • 충돌 감지 시스템의 객체는 프레임 간에 상대적으로 작은 단계로 이동하기 때문에 이전 프레임의 거의 정렬된 리스트를 유지할 수 있음
    • 이러한 거의 정렬된 리스트를 정렬할 때, insertion sort는 O(n)에 가깝고 Quicksort는 O(n^2)에 가까움

  • 과거에 비슷한 작업을 했지만 정렬 대신 각 방향에 대한 인덱스 리스트를 유지했음

    • 예를 들어, objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge 같은 4개의 리스트가 있음
    • 객체가 수평으로 이동하면 leftEdge와 rightEdge 배열에서 자신의 인덱스를 업데이트함
    • 이동하면서 최대 1~2개의 인덱스만 교환하면 됨

  • 이 글은 정말 잘 정리되어 있음

    • 90년대 후반부터 게임 개발을 해왔지만 대부분의 작업이 엔진에 의해 추상화됨
    • 복잡한 시스템 시뮬레이션을 이해하는 데 필수적임
    • 저자가 매우 접근하기 쉬운 글을 작성해줘서 감사함

  • 연속 충돌 감지에 관한 문서를 항상 즐겨 읽었음

  • 일러스트레이션 사용이 좋았음

    • 때때로 이러한 기사들이 멋진 데모를 모으기 위한 핑계처럼 느껴지지만, 이번 글은 일러스트레이션이 주를 이루지 않음

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

  • "이 단순한 알고리즘은 Big O 용어로 O(n^2) 시간에 실행됨"이라는 주장에 대해 의문을 제기함

    • 외부 루프(i)는 n - 1까지 세고, 내부 루프(j)는 i + 1에서 시작하여 점점 적은 수를 셈
    • CS 전공자는 아니지만, 큰 n 값에 대해 O(n^2)와 대략적으로 동일한지, 아니면 더 적은지 궁금함

  • 이 방법이 잠재적 충돌자를 줄이기 위해 쿼드 트리를 사용하는 것과 유사한지 궁금했음

  • 선형 프로그래밍 방법이 제안된 적이 있는지 궁금했음

  • 이 웹사이트에 좋은 의미로 산만해졌음

    • 재미있고 영감을 줌