Swept AABB Collision Detection Conflict with Tile-sized Gaps

Question

พื้นหลัง

วิธีการกวาดเพื่อตรวจจับและแก้ไขการชนได้พิสูจน์แล้วว่าใช้งานได้หลากหลายมากในการใช้การชนกันในเกมของเราและฉันมีบทความ GameDev.net นี้เพื่อขอบคุณสำหรับสิ่งนั้น: https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/

บทความนี้มีประโยชน์มากและฉันได้เรียนรู้มากมายจากมัน มันมีข้อบกพร่องบางอย่างในโค้ดตัวอย่าง (โชคดีที่เราไม่มีพวกเขาเอง) แต่แนวคิดเป็นส่วนสำคัญ ฉันขอแนะนำให้คุณอ่านเนื่องจากเป็นข้อมูลอ้างอิงที่สำคัญมากสำหรับโพสต์นี้

ความขัดแย้ง

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

ในขณะที่รหัสทำงานตามบทความ GameDev (ฉันมีการสาธิตเพิ่มเติมในโพสต์นี้) มีปัญหาเล็กน้อยเกี่ยวกับวิธีการ "เลื่อน"

การเลื่อนเป็นวิธีการแก้ปัญหาการชนเพื่อให้เอนทิตีไม่ยึดติดกับพื้นผิวของร่างกายฟิสิกส์อื่น ๆ โดยทั่วไปจะช่วยให้ผู้เล่นสามารถเดินบนพื้นและเลื่อนไปตามกำแพงเมื่อกระโดดขึ้นไปโดยไม่ติดอยู่บนพื้นผิว ภาพนี้จากบทความอธิบายได้ดีกว่าที่ฉันทำ:

นี่เป็นทางออกที่ดี แต่ จำกัด ผู้เล่นที่มีขนาดกระเบื้องไม่ให้ตกลงไปในรูขนาดกระเบื้องและให้ผู้เล่นเดินข้ามมันไปแทน

อย่างที่คุณเห็นคุณคาดว่าผู้เล่นจะตกลงไปในหลุมเหล่านั้น แต่ดูเถิดเขาเดินผ่านพวกเขาไป ฉันได้ทดสอบด้วยความเร็วในการเดินที่หลากหลายแม้จะต่ำกว่าหนึ่งพิกเซลต่อเฟรมและผู้เล่นก็ยังเดินผ่านพวกเขา

นอกจากนี้ฉันต้องการชี้แจงว่านี่ไม่ใช่ปัญหากับแกนเดียวเนื่องจากผู้เล่นไม่สามารถกระโดดลงไปในรูขนาดเท่ากระเบื้องได้

โปรดทราบว่าผู้เล่นยังคงสามารถตกลงไปในหลุมเหล่านั้นได้เพียงแค่ต้องมีการปิดกั้นเพื่อให้สามารถทำได้

... และเช่นเดียวกันกับการเดินเป็นหนึ่งเดียว

ต้นตอของปัญหา

ฉันขอแนะนำให้คุณอ่านโค้ดบางส่วนในการสาธิตที่ฉันให้ไว้เนื่องจากการตัดโค้ดต่อไปนี้เกี่ยวข้องกับส่วนนี้:

resolveCollisionOrMove(deltaTime, movement = this.vel, remainingTime = 1, collisionStack = this.collisionStack) {
    // Sort collisions in the correct order: First by distance, then by
    // time of impact to correct the order a bit.
    collisionStack.sort((a, b) => a.distance - b.distance);
    collisionStack.sort((a, b) => a.collisionTime - b.collisionTime);
    let hit = collisionStack.shift();

    // If a collision is detected at all, resolve for the closest AABB. Otherwise add velocity to position.
    if (hit) {
        this.center.x += movement.x * hit.collisionTime * deltaTime;
        this.center.y += movement.y * hit.collisionTime * deltaTime;

        // Calculate the correct time of impact for the remaining
        // collisions or to apply movement
        let time = remainingTime - hit.collisionTime;

        // Calculate the collision normal (vector used to slide the object that collided)
        let dotProduct = p5.Vector.dot(movement, hit.normal) * time;
        hit.normal.mult(dotProduct);

        // Handle events after each respective side that collided
        this.onCollision(hit.side);

        if (time > 0) {
            // If the time of impact happened to be above zero, then recalculate
            // collision for all other potential collisions with respect to the normal vector
            let stack = [];
            for (let sweep of collisionStack) {
                // Pass the normal vector as the movement vector for the next possible collision
                if (this.createMovementBoundary(deltaTime, hit.normal).overlaps(sweep.aabb)) {
                    let newSweep = this.calculateSweepData(sweep.aabb, hit.normal, deltaTime);
                    stack.push(newSweep);
                }
            }

            // Keep resolving collisions for the other potential collisions
            this.resolveCollisionOrMove(deltaTime, hit.normal, time, stack);
        }
    } else {
        this.center.add(p5.Vector.mult(movement, deltaTime));
    }
}

ฉันคิดว่านี่เป็นปัญหาที่เกิดจากการชนกันตามปกติที่คำนวณสำหรับเอฟเฟกต์การเลื่อน สมมติว่าผู้เล่นเดินไปยังรูขนาดเท่ากระเบื้องจากด้านซ้าย (ตอนนี้รูอยู่ทางขวาของผู้เล่น) อัลกอริธึมการแก้ปัญหาการชนของฉันคำนึงถึงการชนอื่น ๆ ที่อาจเกิดขึ้นตามเวกเตอร์การเลื่อนที่ใช้กับผู้เล่นเมื่อพบการชนที่ใกล้เคียงที่สุด ซึ่งหมายความว่ากระเบื้องก่อนหลุมคือสิ่งที่ชนกับผู้เล่นก่อนซึ่งจะใช้เวกเตอร์การเคลื่อนไหว (สไลด์) ที่มีองค์ประกอบ y เป็นศูนย์ สิ่งนี้ทำให้อัลกอริทึมการชนกันไม่สนใจกระเบื้องทางด้านซ้ายของหลุมเนื่องจากอาจเกิดการชนกันเนื่องจากตามตรรกะแล้วผู้เล่นจะไม่ชนกับด้านซ้าย

เส้นสีเขียวเป็นเวกเตอร์ปกติที่ใช้สำหรับการเลื่อน (ซึ่งใช้ในการคำนวณการชนครั้งต่อไป) ในขณะที่เส้นสีแดงคือความเร็วจริงที่ใช้กับผู้เล่นก่อนที่จะแก้ไขการชน ...

ปัญหาคือฉันไม่รู้วิธีแก้ปัญหานี้โดยไม่ทำลายรหัส ฉันรู้ว่าปัญหานี้สามารถแก้ไขได้เพียงแค่ลดขนาดเครื่องเล่น นั่นไม่ใช่สิ่งที่ฉันยินดีที่จะยอมรับว่าเป็นวิธีแก้ปัญหาเนื่องจากมัน จำกัด กลไกการเล่นเกมจำนวนมากซึ่งฉันจะไม่เข้าที่นี่

รหัส

นี่คือลิงค์ไปยัง JSFiddle ที่ฉันสร้างขึ้นเมื่อเวทมนตร์ทั้งหมดเกิดขึ้น: https://jsfiddle.net/uwg0m9zp/

ฉันได้เขียนมันใน JavaScript ในไฟล์ HTML ไฟล์เดียวที่ฉันใช้ไลบรารี p5.js เพื่อลดความซับซ้อนของการป้อนข้อมูลกราฟิกและการคำนวณเวกเตอร์ การเรียกใช้ฟังก์ชัน p5.js ส่วนใหญ่ไม่สำคัญสำหรับปัญหานี้ยกเว้นคณิตศาสตร์เวกเตอร์ แต่ถ้าโครงสร้างของโค้ดทำให้สับสนคุณเพียงแค่ค้นหาเอกสาร (หรือถามในความคิดเห็น):https://p5js.org/

คำแนะนำการสาธิต

การสาธิตนี้มีรูปสี่เหลี่ยมผืนผ้าสีน้ำเงินซึ่งเป็นผู้เล่นของเรา เขาสามารถเดินบินและชนกับกระเบื้องสีม่วงในแผนที่

การควบคุม ได้แก่ :

• A: เดินไปทางซ้าย
• D: เดินไปทางขวา
• อวกาศ: บิน

ใช้ตัวควบคุมเหล่านี้เพื่อเดิน / บินเข้าไปในช่องว่างของกระเบื้อง

คำสุดท้าย

ฉันหวังว่าฉันจะอธิบายปัญหาของฉันได้ดี โปรดอย่าลังเลที่จะถามคำถามหากฉันรู้สึกสับสนเล็กน้อย โปรดทราบว่าฉันได้ทดสอบด้วยเพื่อดูว่านี่เป็นปัญหาความไม่แม่นยำของการลอย (โดยใช้ epsilon เป็นต้น) และไม่มีโชค

ขอขอบคุณที่อ่านสิ่งนี้และขอความช่วยเหลือล่วงหน้า!

Answer 1

เนื่องจากคุณมีโลกที่เรียงต่อกันและตัวอักษรที่มีขนาดพอดีขั้นตอนแรกในการแยกแยะปัญหานี้จึงสามารถรับรู้ได้เมื่ออักขระอยู่ในแนวเดียวกับกระเบื้อง ในกรณีที่ตกลงไปในหลุมจะเกิดขึ้นเมื่อ

• พิกัด Y เป็นจำนวนเต็ม (สมมติว่าไทล์ของคุณมีความยาวด้าน 1) ซึ่งควรเป็นจริงเมื่อใดก็ตามที่เกิดการเลื่อนบนสิ่งกีดขวางแนวกระเบื้อง
• พิกัด X คำนวณโดยการเลื่อนปัดเศษลงเป็นจำนวนเต็มเปลี่ยนเป็นจำนวนเต็มต่างจากที่เป็นจุดเริ่มต้นของส่วนเลื่อนของการเคลื่อนที่

การกระโดดจะเหมือนกันกับพิกัดที่กลับด้าน

เมื่อคุณทราบว่าการคำนวณการชนของคุณเกิดขึ้นจากการจัดแนวกระเบื้องให้แบ่งการเคลื่อนไหวออกเป็นสองส่วน:

ตอนนี้คุณสามารถแสร้งทำเป็นว่าคุณกำลังทำขั้นตอนทางฟิสิกส์ที่เริ่มต้นที่ตำแหน่งกล่องประในแผนภาพนี้จัดการสถานการณ์ตามที่คุณต้องการและหากคำตอบไม่ใช่ "ตกลงไปในหลุม" (เช่นในกรณีที่ ไม่มีรู!) ให้ใช้ส่วนที่สองของการเคลื่อนไหวต่อไป (กล่องกรอบทึบในแผนภาพ) เพื่อรักษาความเร็ว

---

ส่วนที่สองของปัญหาน่าสนใจ: เราจะตัดสินใจอย่างไรว่าตัวละครควรตกลงไปในหลุม? ถ้าเรามองในขณะนี้ก็สอดคล้องกับกระเบื้องมันจะไปทางขวาหรืออาจลงไปและเวกเตอร์ความเร็วสอดคล้องส่วนใหญ่ไปทางขวามีเล็กมีส่วนร่วมของแรงโน้มถ่วงชี้ลง (น้อยเพราะมันได้รับในเหวสำหรับศูนย์เวลา ; หรือในการจำลองความเร็วหนึ่งเฟรม) ในทำนองเดียวกันในกรณีการกระโดดความเร็วจะขึ้นและมีแรงไปด้านข้าง แต่ไม่มีความเร็วด้านข้าง ความละเอียดตามการจัดแนวของเวกเตอร์ความเร็วจะให้คำตอบที่คุณไม่ต้องการอย่างสม่ำเสมอ!

ดังนั้นสำหรับการเล่นเกมที่คุณต้องการคุณควรตรวจจับกรณีที่ตรงตามเงื่อนไขเหล่านี้ทั้งหมด:

• ตัวอักษรสอดคล้องกับกระเบื้อง (ตามที่กล่าวไว้ข้างต้น)
• ความเร็วกำลังชี้ไปในทิศทางที่แน่นอนและแรงโน้มถ่วงหรือแรงป้อนข้อมูลของผู้เล่นจะชี้ในแนวตั้งฉาก
• และมีพื้นที่เปิดโล่งในทิศทางตั้งฉากนั้น

และเลือกใช้เส้นทางตั้งฉากเสมอ! คุณสามารถใช้สิ่งนี้ได้โดยดำเนินการต่อราวกับว่ามีไทล์ปิดกั้นที่หยุดตัวละครให้เคลื่อนที่ไปในทิศทางปกติ (อาจจะยุ่งยากในกรณีกระโดด) หรือคุณสามารถทำให้การใช้งานง่ายขึ้นและยังเพิ่มความมีไหวพริบโดยให้ตัวละครเตะพิเศษเข้าไปใน รู (หนึ่งเฟรมของการเลื่อนตำแหน่ง + ความเร็วบางส่วนในทิศทางนั้น) อาจจะเป็นภาพเคลื่อนไหวพิเศษ

Answer 2

หลังจากใช้เวลานับไม่ถ้วนในการค้นหาปัญหาผ่านการลองผิดลองถูกและถามรอบ ๆ บนเซิร์ฟเวอร์ Discord และที่นี่เพื่อนของฉันและฉันพบวิธีแก้ปัญหาที่หลากหลายมากสำหรับปัญหาที่น่ารำคาญโดยเฉพาะ

เครดิตเกิดจาก Kevin Reid ที่สละเวลาอันมีค่าของเขามาตอบกระทู้นี้ เขาเขียนคำตอบที่เป็นลายลักษณ์อักษรซึ่งอธิบายแนวคิดที่สำคัญในโซลูชันนี้ ฉันอยากจะขอบคุณเพื่อนที่ฉันคุยด้วยบนเซิร์ฟเวอร์ SFML Discord ที่เป็นประโยชน์มากในการแสดงให้เราเห็นว่าเราควรแก้ไขปัญหานี้อย่างไร

เราเรียนรู้อะไร

มีสิ่งง่ายๆอย่างหนึ่งที่ฉันกลัวซึ่งตลกพอแก้ไขได้ทั้งหมดนั่นคือการเพิ่มกรณีพิเศษ

คดีพิเศษคดีพิเศษคดีพิเศษ ! ฉันกลัวมากที่จะทำลายการไหลของอัลกอริทึมที่ฉันไม่เคยคิดมาตั้งแต่แรก (การกวาด) แต่สิ่งที่จำเป็นก็คือการเพิ่มสิ่งพิเศษเพื่อตรวจสอบสถานการณ์รูขนาดกระเบื้องเหล่านี้ในขณะที่ยังคงติดต่อกับ อัลกอริทึม "คิด"

โซลูชันนี้ไม่เพียง แต่คำนึงถึงรูที่มีขนาดเท่ากันกับกระเบื้องเท่านั้น แต่ยังมีขนาดของเอนทิตีใด ๆ ที่กำลังจะเดินเข้าไปในหลุมเดียว

การตรวจจับกรณีดังกล่าว

ฉันจะอธิบายการตรวจจับด้วยตัวอย่างง่ายๆที่สามารถนำไปใช้กับการเคลื่อนไหวในแกนใดก็ได้ สมมติว่าผู้เล่นเดินจากซ้ายไปขวาและกำลังเข้าใกล้หลุมที่มีขนาดแนวนอนเท่ากับเขาในเฟรมนี้ อัลกอริทึมส่วน Broadphase จะตรวจจับการชนที่อาจเกิดขึ้นกับสองชิ้นต่อไปนี้เสมอ:

• ผู้เล่นที่กำลังเดินอยู่
• อันหนึ่ง (อาจ) ถัดจากหลุม

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

fixEqualSizedHoleCollision(hit, potentialMovement, time, collisionStack) {
     if (collisionStack.length > 0) {
         // The tile/entity the player currently stands on
         let standingOn = hit.aabb;

         // The tile/entity assumed to be next to the player-sized hole
         let nextToHole = collisionStack[0].aabb;
                ...

อย่างไรก็ตามฉันเรียกฟังก์ชั่นนี้ในส่วนความละเอียดการชนกันในการสาธิตใหม่ของฉัน (เพิ่มเติมคำตอบนี้)

เนื่องจากฉันแสดงการชนครั้งแรกที่อาจเกิดขึ้นฉันจึงส่งมันเป็นพารามิเตอร์สำหรับฟังก์ชันนี้เพื่อให้การชนกันที่อาจเกิดขึ้นต่อไปนี้เป็นครั้งแรกในสแต็ก

ตอนนี้สิ่งที่เราต้องทำคือตรวจสอบว่ากระเบื้องเหล่านี้อยู่ภายใต้เครื่องเล่นหรือไม่ตั้งแต่แรก! สามารถทำได้โดยการตรวจสอบว่าไพ่ทั้งสองนี้มีขนาดครึ่งหนึ่งของขนาดผู้เล่นในแนวตั้งบวกกับขนาดกระเบื้องครึ่งหนึ่งจากผู้เล่นบนแกน y แผนภาพนี้แสดงสิ่งนี้ได้ดีที่สุด

เส้นสีเขียวคือสิ่งที่แสดงถึงระยะทางที่ฉันพูดถึง เส้นสีเขียวทั้งหมดเหล่านั้นจะต้องมีค่าเท่ากันเพื่อตัดสินว่าไทล์เหล่านี้อยู่ใต้เครื่องเล่นบนแกน y หรือไม่

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

ความละเอียด

การไขคดีมีความซับซ้อนน้อยกว่าการตรวจจับอย่างน่าตกใจ เพียงแค่หยุดเครื่องเล่นเพื่อให้พอดีกับหลุมหยุดการเคลื่อนที่ x ทั้งหมดแล้วเลื่อนลงด้านล่างด้วยขนาดเดียวกับแรงโน้มถ่วง การหยุดเครื่องเล่นสามารถจำลองได้ด้วย "อุปสรรค" ที่อยู่ด้านบนของกระเบื้องถัดจากรู

เส้นสีเขียวตอนนี้เป็นเวกเตอร์การเคลื่อนไหวใหม่ของผู้เล่นและกล่องสีขาวคือสิ่งกีดขวางจำลองซึ่งจะหยุดผู้เล่นในเส้นทางของมัน! นี่คือส่วนหนึ่งของรหัสที่แก้ไขได้:

barrierOffset.x = (this.extents.x - nextToHole.extents.x) * -movementDir;
if (areBothUnderMe && isHoleBetween) {
    // Create a simulated barrier that will block the player and make him fall
    // into the hole.
    let barrier = new AABB(nextToHole.center.copy(), this.extents.copy());
    barrier.center.sub(barrierOffset);
    this.center.x = barrier.center.x + (barrier.extents.x + this.extents.x) * (-movementDir);
    hit.normal.x = 0; // The player should now fall into the hole and no longer walk
    hit.normal.y = potentialMovement.y; // The sliding should now be applied to the hole wall
}

การสาธิตใหม่

นี่คือลิงค์ใหม่ไปยัง JSFiddle พร้อมรหัสใหม่: https://jsfiddle.net/2bnv510x/

มีบางส่วนเพิ่มเติมใหม่จากก่อนหน้านี้ ก่อนอื่นคุณสามารถส่งผ่านไปยังรูขนาดกระเบื้อง (ชัด ๆ ) และประการที่สองฉันได้เพิ่มเอนทิตีขนาดใหญ่สองรายการโดยแยกขนาดกระเบื้องออกจากกัน ฉันยังได้เพิ่มการควบคุมใหม่ที่ช่วยให้คุณเปลี่ยนความเร็วของคุณ:

• Shift: เคลื่อนที่ช้ามาก
• ถาม: เคลื่อนที่เร็วมาก

สนุก!

คำพูดสุดท้าย

ฉันขอขอบคุณทุกคนที่ช่วยเราแก้ปัญหานี้ เราได้เรียนรู้มากมายจากปัญหานี้และฉันหวังว่าทุกคนที่อ่านสิ่งนี้ก็ทำได้เช่นกัน

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