การจัดเรียง, การกวาด, การตัดทิ้ง: อัลกอริทึม Collision Detection (2023)

 (leanrada.com)
3 คะแนน โดย GN⁺ 2024-08-15 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

อัลกอริทึมการตรวจจับการชน

การตรวจจับการชน

  • ในการเขียนโปรแกรมวิดีโอเกม การตรวจจับการชนเป็นปัญหาที่พบได้บ่อยมาก
  • เป็นสิ่งจำเป็นในการป้องกันไม่ให้ตัวละครทะลุผ่านกัน หรือใช้สร้าง physics engine

แนวทางแบบง่าย 🐥

  • วิธีตรวจสอบทุกคู่ของวัตถุเพื่อดูว่าชนกันหรือไม่
  • ตัวอย่างโค้ด: 
    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);
    }
  }
}
  • วิธีนี้มีความซับซ้อนเชิงเวลาแบบ O(n^2)

ปัญหาด้านประสิทธิภาพ

  • ยิ่งจำนวนวัตถุมากขึ้น ก็ยิ่งเกิดปัญหาด้านประสิทธิภาพ
  • ตัวอย่างเช่น เมื่อ n = 20 จะต้องตรวจสอบ 190 คู่

การปรับปรุงวิธีแก้ปัญหา

  • สิ่งสำคัญคือการลดงานที่ไม่จำเป็น
  • การปรับแต่งฟังก์ชัน intersects(): 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

การเพิ่มประสิทธิภาพด้วยการจัดเรียง

  • หากจัดเรียงวัตถุตามพิกัด x จะสามารถลดการตรวจสอบที่ไม่จำเป็นได้
  • ตัวอย่างโค้ด: 
    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);
    }
  }
}

การวิเคราะห์ประสิทธิภาพ

  • การจัดเรียง: O(n log n)
  • ลูปชั้นใน: โดยเฉลี่ย O(n + m) (m คือจำนวนทั้งหมดที่ซ้อนทับกันบนแกน x)
  • ความซับซ้อนเชิงเวลาสุดท้าย: O(n log n + m)

การเปรียบเทียบแบบภาพ

  • การเปรียบเทียบระหว่างการตรวจสอบทุกคู่ทั่วทั้งระบบกับการตรวจสอบคู่หลังจัดเรียง
  • การตรวจสอบคู่หลังจัดเรียงใช้จำนวนการตรวจสอบน้อยกว่ามาก

สรุปโดย GN⁺

  • บทความนี้กล่าวถึงวิธีเพิ่มประสิทธิภาพอัลกอริทึมการตรวจจับการชนในการพัฒนาเกม
  • เริ่มจากอัลกอริทึมแบบง่าย O(n^2) แล้วปรับปรุงประสิทธิภาพอย่างมากด้วยการจัดเรียง
  • เป็นข้อมูลที่มีประโยชน์มากสำหรับนักพัฒนาเกมหรือวิศวกรซอฟต์แวร์
  • โปรเจ็กต์อื่นที่มีความสามารถคล้ายกัน เช่น Box2D, Bullet Physics เป็นต้น

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-08-15
ความคิดเห็นบน Hacker News

  • ผู้เขียนแนะนำให้ใช้อัลกอริทึมการเรียงลำดับที่ "เร็ว" อย่าง mergesort หรือ quicksort เพื่อให้ได้ประสิทธิภาพสูงสุด

    • แต่ในทางปฏิบัติ อัลกอริทึมการเรียงลำดับที่ "ดูด้อยกว่า" อย่าง insertion sort อาจให้ประสิทธิภาพที่ดีกว่า
    • วัตถุในระบบตรวจจับการชนจะเคลื่อนที่ทีละระยะค่อนข้างน้อยระหว่างแต่ละเฟรม จึงสามารถคงรายการที่เกือบเรียงลำดับจากเฟรมก่อนหน้าไว้ได้
    • เมื่อเรียงลำดับรายการที่เกือบเรียงอยู่แล้วแบบนี้ insertion sort จะใกล้เคียง O(n) ขณะที่ Quicksort จะใกล้เคียง O(n^2)

  • เคยทำงานลักษณะคล้ายกันมาก่อน แต่ใช้การเก็บรายการดัชนีสำหรับแต่ละทิศทางแทนการเรียงลำดับ

    • ตัวอย่างเช่น มี 4 รายการอย่าง objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
    • ถ้าวัตถุเคลื่อนที่ในแนวนอน ก็จะอัปเดตดัชนีของตัวเองในอาร์เรย์ leftEdge และ rightEdge
    • ระหว่างการเคลื่อนที่ จำเป็นต้องสลับดัชนีสูงสุดเพียง 1-2 ตำแหน่งเท่านั้น

  • บทความนี้เรียบเรียงมาได้ดีมาก

    • แม้จะทำเกมมาตั้งแต่ช่วงปลายยุค 90 แต่ส่วนใหญ่รายละเอียดถูกเอนจินทำ abstraction ไว้หมดแล้ว
    • เรื่องนี้จำเป็นอย่างยิ่งต่อการทำความเข้าใจการจำลองระบบที่ซับซ้อน
    • ขอบคุณผู้เขียนที่เขียนออกมาได้อ่านง่ายมาก

  • ชอบอ่านเอกสารเกี่ยวกับ continuous collision detection อยู่เสมอ

  • ชอบการใช้ภาพประกอบ

    • บางครั้งบทความแนวนี้ให้ความรู้สึกเหมือนเป็นข้ออ้างเพื่อรวบรวมเดโมสวย ๆ แต่บทความนี้ไม่ได้พึ่งภาพประกอบเป็นหลัก

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

    • แนะนำให้ลองดูบทความอื่น ๆ ของเขาด้วย: https://leanrada.com/

  • ตั้งข้อสงสัยกับข้อความที่ว่า "อัลกอริทึมง่าย ๆ นี้ทำงานในเวลา O(n^2) ในความหมายของ Big O"

    • ลูปภายนอก (i) นับไปจนถึง n - 1 และลูปภายใน (j) เริ่มจาก i + 1 ทำให้นับจำนวนน้อยลงเรื่อย ๆ
    • ไม่ได้จบสาย CS เลยสงสัยว่า สำหรับ n ขนาดใหญ่ มันถือว่าเทียบได้คร่าว ๆ กับ O(n^2) จริงหรือไม่ หรือจริง ๆ แล้วน้อยกว่านั้น

  • สงสัยว่าวิธีนี้คล้ายกับการใช้ quadtree เพื่อลดจำนวนตัวที่อาจชนกันหรือไม่

  • สงสัยว่าเคยมีการเสนอวิธีแบบ linear programming ไว้หรือไม่

  • เว็บไซต์นี้ทำให้เผลอวอกแวกไปในทางที่ดี

    • สนุกและสร้างแรงบันดาลใจ