การเรียงลำดับ การกวาด และการตัดทิ้ง: อัลกอริทึมตรวจจับการชน (2023)

 (leanrada.com)
3 คะแนน โดย GN⁺ 2024-08-15 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • อธิบายลำดับการเพิ่มประสิทธิภาพจากการตรวจทุกคู่ไปสู่ sweep-and-prune โดยใช้ซิมูเลชันลูกบอลเพื่อแก้โจทย์ การตรวจจับการชน ที่พบซ้ำ ๆ ในฟิสิกส์เกม
  • วิธีแบบง่ายจะเรียก intersects() กับคู่ตัวเลือกทั้งหมดของวัตถุ n ชิ้น ต้องตรวจประมาณ (n*(n-1))/2 ครั้ง จึงโตอย่างรวดเร็วเป็น O(n²)
  • การทดสอบการตัดกันของ AABB ประกอบด้วยอสมการหลายตัวและ && โดยสามารถใช้ short-circuit evaluation และสมบัติถ่ายทอดของอสมการเพื่อตัดตัวเลือกที่ไม่มีโอกาสชนออกได้ตั้งแต่เนิ่น ๆ
  • หลังเรียงวัตถุตาม minimum x หรือขอบซ้ายแล้ว เมื่อ ball2.left > ball1.right ก็ break ลูปด้านในเพื่อตัดตัวเลือกที่เหลือออกพร้อมกัน
  • เมื่อรวมต้นทุนการเรียงลำดับ O(n log n) กับต้นทุนลูปตามจำนวนการซ้อนทับบนแกน x คือ m จะอยู่ราว O(n log n + m) โดยเฉลี่ย และลดการเรียก intersects() ที่ไม่จำเป็นได้มาก

จุดเริ่มต้นของการตรวจจับการชนในเกม

  • การตรวจจับการชน เป็นเงื่อนไขตั้งต้นของพฤติกรรมหลายอย่างในการเขียนโปรแกรมวิดีโอเกม
    • ทำให้ตัวละครไม่สามารถเดินทะลุกันได้
    • ทำให้ Goomba เปลี่ยนทิศทางเมื่อชนกับวัตถุอื่น
    • ใน agar.io เซลล์ใหญ่กินเซลล์เล็กเมื่อสัมผัสกัน
    • จัดการฟิสิกส์เกมทั่วไป
  • ตัวอย่างนี้ใช้ ซิมูเลชันลูกบอลแข็งเกร็ง เพื่อเปรียบเทียบแนวทางตรวจจับการชนหลายแบบ
  • ขอบเขตคือแนวทางตั้งแต่วิธีที่ง่ายที่สุดไปจนถึง sweep-and-prune โดยไม่รวมการแบ่งพื้นที่หรือการแบ่งย่อยด้วยต้นไม้เชิงพื้นที่

แนวทางแบบง่ายที่ตรวจทุกคู่

  • วิธีที่ตรงที่สุดคือมองทุกคู่ของวัตถุเป็นตัวเลือก
    • ลูปด้านนอกวนผ่านลูกบอลแต่ละลูก
    • ลูปด้านในเริ่มจาก i + 1 เพื่อหลีกเลี่ยง คู่ซ้ำ อย่าง A-B และ B-A
    • เรียก intersects(ball1, ball2) กับแต่ละคู่ตัวเลือก และถ้าเป็นจริงก็เรียก bounce(ball1, ball2)
  • การตรวจนี้ทำซ้ำในทุกขั้นเวลา ดังนั้นลูกบอลจะถูกจัดการให้เด้งเมื่อถึงจังหวะที่ชนกัน
  • เมื่อจำนวนวัตถุน้อยก็เพียงพอ แต่เมื่อจำนวนเพิ่มขึ้น ปริมาณการตรวจจะกลายเป็นคอขวดด้านประสิทธิภาพอย่างรวดเร็ว

ข้อจำกัดที่ O(n²) สร้างขึ้น

  • อัลกอริทึมแบบง่ายทำงานในเวลา O(n²) ตาม Big O
  • สำหรับลูกบอล n ลูก จำนวนคู่ที่ต้องตรวจประมาณ (n*(n-1))/2 หรือ 0.5n² - 0.5n คู่
    • ถ้า n = 5 จะมี 10 คู่
    • ถ้า n = 10 จะมี 45 คู่
    • ถ้า n = 15 จะมี 105 คู่
    • ถ้า n = 20 จะมี 190 คู่
  • ในกรณีแย่ที่สุดที่วัตถุทั้งหมดซ้อนทับกันพร้อมกัน อัลกอริทึมตรวจจับการชนใด ๆ ก็หลีกเลี่ยงการจัดการการชนแบบ O(n²) ได้ยาก
  • ในการเปรียบเทียบจริง กรณีเฉลี่ยและกรณีดีที่สุดมีประโยชน์เชิงปฏิบัติมากกว่ากรณีแย่ที่สุด
  • วิธีแบบง่ายจะเคลื่อนที่แบบ Θ(n²) เสมอโดยไม่ขึ้นกับจำนวนการชนจริง จึงมีช่องให้ปรับปรุงมาก

งานซ้ำภายใน intersects()

  • จุดเริ่มต้นของการเพิ่มประสิทธิภาพคือฟังก์ชัน intersects() ที่ถูกเรียกสำหรับทุกคู่ตัวเลือก
  • การทดสอบการตัดกันของ AABB ทั่วไปประกอบด้วย การตรวจอสมการ หลายรายการเพื่อเปรียบเทียบขอบเขตในแต่ละทิศทาง
function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}
  • การตรวจนี้แบ่งเป็นสี่เงื่อนไข
    • object1.left < object2.right
    • object1.right > object2.left
    • object1.top < object2.bottom
    • object1.bottom > object2.top
  • เพราะ short-circuit evaluation ของ && หากมีเงื่อนไขใดเป็นเท็จ การทดสอบการตัดกันทั้งหมดจะเป็นเท็จทันที
  • หากสรุปกรณีที่ “มีอย่างน้อยหนึ่งเงื่อนไขเป็นเท็จ” ครอบคลุมหลายการทดสอบ ก็จะลดการเรียก intersects() เองได้
  • แนวคิดนี้ไปในทิศทางเดียวกับ ทฤษฎีบทแกนแยก ที่ว่าหากเงาบนแกนหนึ่งไม่ซ้อนทับกัน วัตถุสองชิ้นก็ไม่ชนกัน

การตัดตัวเลือกด้วยสมบัติถ่ายทอดของอสมการ

  • แค่มองเงื่อนไข object1.right > object2.left เพียงตัวเดียวก็มีช่องให้เพิ่มประสิทธิภาพแล้ว
  • เมื่อวัตถุสามชิ้น A, B, C อยู่ในแนวนอนตามลำดับ A-B-C การตรวจต่อไปนี้ทั้งหมดอาจเป็นเท็จได้
A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false
  • ถ้า A > B เป็นเท็จ และ B > C เป็นเท็จ เราจะรู้ได้จาก สมบัติถ่ายทอดของอสมการ ว่า A > C ก็เป็นเท็จเช่นกัน
  • ดังนั้นจึงตัดสินได้ว่าวัตถุสองชิ้นไม่ชนกันโดยไม่ต้องเรียก intersects(A, C)
  • การข้ามนี้ใช้ได้เมื่อวัตถุอยู่ในลำดับเฉพาะเท่านั้น แต่ป้ายชื่อของวัตถุเป็นสิ่งกำหนดตามอำเภอใจ จึงกำหนดให้วัตถุซ้ายเป็น A ตรงกลางเป็น B และขวาเป็น C ได้
  • งานในการจัดวางวัตถุให้อยู่ในลำดับเชิงตรรกะแบบนี้ก็คือ การเรียงลำดับ นั่นเอง

เรียงตามค่าต่ำสุดของแกน x

  • รายการที่เรียงแล้วทำให้สามารถใช้สมบัติถ่ายทอดของอสมการกับตัวเลือกหลายตัวได้พร้อมกัน
  • อัลกอริทึมเรียงลำดับที่เร็วโดยทั่วไปคือ O(n log n) ซึ่งต่ำกว่า O(n²)
  • วัตถุไม่ใช่จุด แต่กินช่วงบนแกน x ดังนั้นการเรียงตามตำแหน่ง x จึงใช้ขอบซ้ายหรือ minimum x
  • สิ่งที่ต้องเปลี่ยนจากโค้ด O(n²) แบบง่ายมีสองอย่าง
    • ก่อนลูป ให้เรียก sortByLeft(balls) เพื่อเรียงลูกบอลตามพิกัด x ของขอบซ้าย
    • ในลูปด้านใน ถ้า ball2.left > ball1.right ให้ break
// sort by min x
sortByLeft(balls);

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];

    // stop when too far away
    if (ball2.left > ball1.right) break;

    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • ฟังก์ชันเรียงลำดับจะเรียงอาร์เรย์โดยอิงจากผลต่างของขอบซ้าย
function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

เหตุผลที่ break ปลอดภัย

  • หากรายการถูกเรียงแล้ว สำหรับจำนวนเต็มบวกใด ๆ c ความสัมพันธ์ต่อไปนี้จะเป็นจริง
balls[j + c].left >= balls[j].left
  • หากตัวเลือกปัจจุบันเป็นไปตามเงื่อนไขต่อไปนี้ คู่ปัจจุบันจะไม่ซ้อนทับกันบนแกน x
balls[j].left > ball1.right
  • เมื่อนำสองอสมการมารวมกัน จะได้ความสัมพันธ์ต่อไปนี้
balls[j + c].left >= balls[j].left > ball1.right
  • ตามสมบัติถ่ายทอด balls[j + c].left > ball1.right ก็เป็นจริงด้วย ดังนั้นตัวเลือกหลังจากนั้นทั้งหมดก็จะไม่ซ้อนทับกับ ball1 บนแกน x เช่นกัน
  • ทันทีที่ ball2 ปัจจุบันไม่ซ้อนทับกับ ball1 อีกต่อไป ก็สามารถ หยุด ลูปด้านในได้โดยไม่ต้องตรวจตัวเลือกที่เหลือ
  • การเพิ่มประสิทธิภาพนี้จำกัดการเรียก intersects() จริงให้อยู่เฉพาะคู่ที่ซ้อนทับกันบนแกน x

ความซับซ้อนด้านเวลาที่ดีขึ้น

  • ต้นทุนการเรียงลำดับเพิ่มพจน์ O(n log n) เมื่อใช้การเรียงลำดับที่เร็วอย่าง mergesort หรือ quicksort
  • ลูปซ้อนสองชั้นที่มีการหยุดก่อนเวลาอาจมองได้ว่าเป็น O(n + m) โดยเฉลี่ย
    • m คือจำนวนการซ้อนทับทั้งหมดบนแกน x
    • ในกรณีดีที่สุดที่ไม่มีการซ้อนทับ แทบไม่มีงานที่ไม่จำเป็น จึงใกล้ O(n)
    • ในกรณีแย่ที่สุด ยังอาจแย่ลงไปถึง O(n²)
  • กรณีเฉลี่ยตั้งอยู่บนสมมติฐานว่าวัตถุกระจายค่อนข้างสม่ำเสมอและมีการชนต่อวัตถุเพียงไม่กี่ครั้ง
  • ความซับซ้อนรวมคือ O(n log n + m) เมื่อรวมการเรียงลำดับกับลูป
  • เหตุผลที่ดีกว่าวิธีแบบง่ายมีสองข้อ
    • n log n เล็กกว่า n²
    • พึ่งพาจำนวนการซ้อนทับ m บางส่วน จึงไม่ประมวลผลมากเกินกว่าที่จำเป็น

ภาระการใช้งานจริงและขั้นต่อไป

  • วิธีอิงการเรียงลำดับนี้เป็นจุดสมดุลที่เปลี่ยนโค้ดไม่มาก แต่ปรับปรุงประสิทธิภาพเวลาเรียกใช้งานได้มาก
  • ในเดโมเปรียบเทียบ การตรวจคู่แบบอิงการเรียงลำดับลดจำนวนการทดสอบ intersects() ต่อเฟรมได้อย่างเห็นได้ชัด เมื่อเทียบกับการตรวจทุกคู่ทั่วทั้งระบบ
  • ต้นทุนการเรียงลำดับไม่ได้แสดงในการแสดงผลเปรียบเทียบ แต่ตั้งอยู่บนสมมติฐานว่าการทดสอบการตัดกันมีต้นทุนสูงพอ
  • แนวทางที่ก้าวหน้ากว่านี้และโค้ดสุดท้ายจะต่อไปยัง Part 2

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

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

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

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

    • ผู้เขียนพูดถึงประเด็นที่แทบเหมือนกันใน Part 2
      อธิบายทำนองว่า “ขั้นตอนการเรียงลำดับเป็นคอขวดในการวิเคราะห์ แต่ส่วนใหญ่แล้วการเรียงลำดับแทบไม่ต้องทำอะไร รายการมักถูกเรียงไว้แล้วจากเฟรมก่อนหน้าแทบตลอดเวลา แม้ลำดับจะเสียไป ก็มักกลับมาเรียงได้ด้วยการสลับเพียงไม่กี่ครั้ง นี่คือตัวอย่างการทำงานของ insertion sort”
    • แทนที่จะเรียงลำดับทุกขั้นตอน ก็มีวิธีทำให้ โครงสร้าง indexing หลวมขึ้นเล็กน้อย เพื่อจับคู่ผู้มีโอกาสชนเมื่อออบเจ็กต์ขยับน้อยกว่า epsilon
      เช่น ขยายรัศมีของทรงกลมเพิ่มขึ้น epsilon ก็ทำได้
      ตราบใดที่ทรงกลมยังไม่ขยับไปถึง epsilon ก็ไม่จำเป็นต้องคำนวณ index ใหม่
      เมื่อต้องคำนวณใหม่ เพื่อหลีกเลี่ยง peak latency อาจเรียงลำดับทีละ 10% ทุกเฟรมเพื่อสร้าง index ที่ล้าหลังอยู่
      หลังผ่านไป 10 เฟรม ก็จะได้ index ที่ยังใช้ได้ ตราบใดที่อยู่ภายใน epsilon จากตำแหน่งเมื่อ 10 เฟรมก่อน
    • quick sort จะกลายเป็น O(n^2) กับรายการที่เกือบเรียงแล้วก็ต่อเมื่อ เลือก pivot ได้แย่มากจริง ๆ เท่านั้น
      ถ้าเลือก pivot แบบสุ่มก็จะเป็น O(n log n) และถ้ารายการเกือบเรียงอยู่แล้ว ก็อาจเลือกสมาชิกตรงกลางของรายการเป็น pivot ได้
      อย่างไรก็ตาม แม้ใช้ pivot ที่เหมาะที่สุด quick sort ในกรณีดีที่สุดก็ยังเป็น O(n log n)
      มีตัวแปรของ merge sort แบบง่าย ๆ ที่ทำงานเป็น O(n log k) เมื่อ k คือจำนวน run แบบเรียงจากน้อยไปมาก/มากไปน้อยในข้อมูล
      sort ค่าเริ่มต้นใน standard library ของ Haskell ใช้อัลกอริทึมแบบนั้น และ Python ก็น่าจะเช่นกัน

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

  • สำหรับ continuous collision detection ผมชอบเอกสารนี้เสมอ: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
    ตัวไลบรารีเองก็ยอดเยี่ยมด้านประสิทธิภาพ
    เพียงแต่มีการ optimize เยอะ จึงผสานเข้าใช้งานค่อนข้างยากเล็กน้อย

  • สงสัยว่าประโยค “อัลกอริทึมแบบ naive นี้รันในเวลา O(n2) ตาม Big-O” ถูกต้องไหม
    outer loop i ทำงาน n - 1 ครั้ง และ inner loop j เริ่มจาก i + 1 ดังนั้นดูเหมือนมันจะวนลดลงเรื่อย ๆ น้อยกว่า n - 1 ไม่ใช่หรือ
    ผมไม่ได้เรียนสายนี้มา เลยสงสัยว่าเมื่อ n ใหญ่ จะถือว่าใกล้เคียงกับ O(n2) หรือจริง ๆ แล้วน้อยกว่าตามที่เห็น

    • ไม่ใช่ n^2 เป๊ะ ๆ
      สำหรับสมาชิกตัวที่ i จะทำการเปรียบเทียบ (n - i - 1) ครั้ง และถ้า index เริ่มที่ 0 จำนวนการเปรียบเทียบรวมคือ (n - 1) * n / 2
      ดู https://en.wikipedia.org/wiki/Triangular_number
      ท้ายที่สุดแล้วในการวิเคราะห์ Big-O ไม่ต่างกัน
      Big-O อธิบายพฤติกรรมเมื่อ n มุ่งสู่อินฟินิตี้ และในตอนนั้น พจน์กำลังสอง จะครอบงำ
    • “optimization” ที่ให้ inner loop เริ่มจาก j = i + 1 มีไว้เพื่อไม่ต้องตรวจคู่ของออบเจ็กต์ทุกคู่ซ้ำสองครั้ง
      และยังช่วยไม่ให้นำออบเจ็กต์ไปตรวจชนกับตัวมันเองด้วย
      เพราะตรวจทุกคู่หนึ่งครั้ง อัลกอริทึมจึงเป็น O(n^2)
    • Big-O เป็นเพียงการจัดประเภทความซับซ้อนที่อธิบายว่า จำนวนการดำเนินการเชิงนามธรรม scale อย่างไร ตามขนาดอินพุต หรือความยาวของรายการอินพุต
      โดยทั่วไปถ้าสามารถเขียนจำนวนการดำเนินการเป็นฟังก์ชันของขนาดอินพุตในเชิงวิเคราะห์ได้ Big-O จะเก็บไว้แค่พจน์ที่ใหญ่ที่สุดและทิ้งสัมประสิทธิ์ทั้งหมด
      มันไม่ได้อธิบาย performance จริงของอัลกอริทึมเสมอไป
      20n2^+5n และ 2n^2 + 9001n ต่างก็เป็น O(n^2)
    • เพราะเป็นผลรวมตั้งแต่ 1 ถึง n จึงได้ n(n+1)/2
      ในสัญกรณ์ Big-O จะละเลยสัมประสิทธิ์ทั้งหมดและพจน์ที่โตช้ากว่า จึงลดรูปเป็น ความซับซ้อนกำลังสอง
    • อาจเข้าใจง่ายขึ้นถ้ามองว่า Big-O คล้ายการคำนวณลิมิตในแคลคูลัส

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

  • Part 2: https://leanrada.com/notes/sweep-and-prune-2/
    บทความดี ๆ อื่น ๆ ก็น่าอ่านเช่นกัน: https://leanrada.com/

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

    • วิธีนั้นดูมีประโยชน์กับฉากที่ส่วนใหญ่เป็น static
      ยิ่งมีองค์ประกอบ dynamic มากขึ้น วิธีสร้างกราฟใหม่ ก็ดูจะดีกว่า

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

    • ใช่
      แต่ใน offline rendering มากกว่า real-time rendering มักจะเห็นการใช้สิ่งอย่าง k-d tree บ่อยกว่า

  • สงสัยตรงที่บอกว่า “จะไม่กล่าวถึงวิธีอื่นอย่าง spatial partitioning หรือการแบ่งย่อย spatial tree”
    มีใครรู้ไหมว่าอัลกอริทึมในบทความนี้โดยทั่วไปเร็วกว่า spatial partitioning/spatial tree subdivision หรือไม่
    นานมาแล้วผมเคยใช้แนวทางประเภท spatial tree และดูแบบ naive แล้วเหมือนเป็นวิธีที่ค่อนข้างดี แต่ตอนนั้นเป็นยุค 80 ก่อนอินเทอร์เน็ต จึงไม่เคยค้นคว้าหรือเปรียบเทียบกับอัลกอริทึมที่คนอื่นใช้

    • ความซับซ้อนในการดูแล spatial partitioning หรือ tree subdivision และสิ่งทำนองนั้นอาจเป็นภาระหนัก โดยเฉพาะเมื่อมีออบเจ็กต์ที่เคลื่อนที่จำนวนมหาศาล
      การจัดการรายการ entity เดี่ยว ๆ หนึ่งรายการ หรือ grid 256x256 cell ที่แต่ละ cell มีรายการ entity ของตัวเอง เขียน ดีบัก และ optimize ได้ง่ายกว่ามากเมื่อเทียบกับโครงสร้าง partition ที่ซับซ้อนซึ่งต้องรักษา tree invariant ทั้งหมดทุกครั้งที่ออบเจ็กต์ขยับ
      ในยุค DOOM หรือ Quake performance ของระบบพื้นฐานแบบนี้สำคัญกว่าสมัยนี้มาก ดังนั้นผู้เขียน engine จึงน่าจะมีเหตุผลมากกว่าที่จะสร้างระบบ partition ที่ซับซ้อนมาก
      CPU สมัยนี้เก่งมากในการไล่อ่านอาร์เรย์ที่เรียงลำดับ และด้วย pipelining การตาม linked list หรือ tree จึงได้เปรียบน้อยลงเมื่อเทียบกับเมื่อก่อน
      เวลา CPU ถูกใช้ไปกับอย่าง AI และ rendering มากกว่าการจัดการรายการ entity