ทำความเข้าใจ Collision Detection game math: 4 ระดับความแม่นยำในการตรวจจับการชน

ทำไม Collision Detection ถึงสำคัญ?

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

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

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

AABB (Axis-Aligned Bounding Box): วิธีง่ายที่สุด

AABB คือวิธีการตรวจจับการชนที่นิยมใช้กันมากที่สุด โดยใช้กล่องสี่เหลี่ยมที่ขนานกับแกน X และ Y ห่อหุ้มวัตถุ

หลักการทำงาน

วิธีนี้ตรวจสอบว่ากล่องสองใบมีการซ้อนทับกันหรือไม่ โดยดูจากเงื่อนไขง่ายๆ 4 ข้อ:

• กล่อง A อยู่ทางซ้ายของกล่อง B
• กล่อง A อยู่ทางขวาของกล่อง B
• กล่อง A อยู่ด้านบนของกล่อง B
• กล่อง A อยู่ด้านล่างของกล่อง B

ถ้าเงื่อนไขทั้ง 4 ข้อเป็นเท็จ แปลว่ากล่องทั้งสองซ้อนทับกัน

โค้ดตัวอย่าง AABB

class AABB:
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height
    
    @property
    def left(self):
        return self.x
    
    @property
    def right(self):
        return self.x + self.width
    
    @property
    def top(self):
        return self.y
    
    @property
    def bottom(self):
        return self.y + self.height

def check_aabb_collision(box1, box2):
    if box1.right < box2.left:
        return False
    if box1.left > box2.right:
        return False
    if box1.bottom < box2.top:
        return False
    if box1.top > box2.bottom:
        return False
    return True

ข้อดีและข้อจำกัด

ข้อดี:

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

ข้อจำกัด:

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

Circle Collision: เมื่อไหร่ควรใช้แทน AABB

เมื่อวัตถุมีรูปทรงกลม หรือใกล้เคียงวงกลม เช่น ลูกบอล กระสุน หรือตัวละครที่มองจากมุมบน การใช้ Circle Collision จะให้ความแม่นยำสูงกว่า AABB

หลักการทำงาน

วิธีนี้คำนวณระยะห่างระหว่างจุดศูนย์กลางของวงกลมสองวง ถ้าระยะห่างน้อยกว่าหรือเท่ากับผลรวมของรัศมีทั้งสอง แปลว่ามีการชนกัน

โค้ดตัวอย่าง Circle Collision

import math

class Circle:
    def __init__(self, x, y, radius):
        self.x = x
        self.y = y
        self.radius = radius

def check_circle_collision(circle1, circle2):
    dx = circle1.x - circle2.x
    dy = circle1.y - circle2.y
    distance = math.sqrt(dx * dx + dy * dy)
    return distance <= (circle1.radius + circle2.radius)

การเพิ่มประสิทธิภาพ

เพื่อหลีกเลี่ยงการคำนวณรากที่สองซึ่งกินทรัพยากร สามารถเปรียบเทียบกำลังสองของระยะทางแทน:

def check_circle_collision_optimized(circle1, circle2):
    dx = circle1.x - circle2.x
    dy = circle1.y - circle2.y
    distance_squared = dx * dx + dy * dy
    radius_sum = circle1.radius + circle2.radius
    return distance_squared <= (radius_sum * radius_sum)

เมื่อไหร่ควรใช้ Circle Collision

• วัตถุมีรูปทรงกลมหรือใกล้เคียงวงกลม
• เกมที่ต้องการความแม่นยำในการชนระดับหนึ่ง แต่ยังต้องการประสิทธิภาพสูง
• เกมแนว Top-down ที่ตัวละครมองเห็นเป็นวงกลมจากมุมกล้อง

SAT (Separating Axis Theorem): สำหรับรูปทรงหลายเหลี่ยม

เมื่อเกมต้องการรองรับวัตถุที่หมุนได้ หรือมีรูปทรงหลายเหลี่ยมซับซ้อน SAT คือคำตอบ

หลักการทำงาน

SAT ทำงานบนหลักการว่า ถ้ารูปหลายเหลี่ยมสองรูปไม่ชนกัน จะต้องมีเส้นแกน (Axis) อย่างน้อยหนึ่งเส้นที่สามารถแยกทั้งสองรูปออกจากกันได้ โดยการฉาย (Project) จุดยอดทั้งหมดของรูปหลายเหลี่ยมไปบนแกนนั้น ถ้าผลการฉายไม่ซ้อนทับกัน แปลว่าไม่มีการชน

แกนที่ต้องตรวจสอบ

สำหรับรูปหลายเหลี่ยม แกนที่ต้องตรวจสอบคือเส้นตั้งฉากของแต่ละด้านของรูปหลายเหลี่ยมทั้งสองรูป

โค้ดตัวอย่าง SAT (แบบย่อ)

import math

def get_axes(polygon):
    axes = []
    for i in range(len(polygon)):
        p1 = polygon[i]
        p2 = polygon[(i + 1) % len(polygon)]
        edge = (p2[0] - p1[0], p2[1] - p1[1])
        normal = (-edge[1], edge[0])
        length = math.sqrt(normal[0]**2 + normal[1]**2)
        axes.append((normal[0]/length, normal[1]/length))
    return axes

def project(polygon, axis):
    dots = [p[0]*axis[0] + p[1]*axis[1] for p in polygon]
    return min(dots), max(dots)

def check_sat_collision(poly1, poly2):
    axes = get_axes(poly1) + get_axes(poly2)
    for axis in axes:
        min1, max1 = project(poly1, axis)
        min2, max2 = project(poly2, axis)
        if max1 < min2 or max2 < min1:
            return False
    return True

ข้อดีและข้อจำกัด

ข้อดี:

• รองรับการหมุน
• แม่นยำสำหรับรูปหลายเหลี่ยม
• สามารถคำนวณทิศทางการชน (Collision Normal) เพื่อใช้ในการตอบสนองทางฟิสิกส์ได้

ข้อจำกัด:

• คำนวณช้ากว่า AABB และ Circle Collision มาก
• ไม่รองรับรูปทรงโค้ง เช่น วงกลม โดยตรง (ต้องประมาณเป็นรูปหลายเหลี่ยม)

Pixel-Perfect Collision: แม่นยำที่สุดแต่กินทรัพยากร

Pixel-Perfect Collision คือการตรวจสอบการชนที่ระดับพิกเซล โดยเช็คว่าพิกเซลที่ไม่โปร่งใสของสไปรต์สองตัวซ้อนทับกันหรือไม่

หลักการทำงาน

1. ตรวจสอบ AABB ก่อน เพื่อกรองวัตถุที่ไม่มีโอกาสชนกันออก
2. ถ้า AABB ซ้อนทับ ให้หาพื้นที่ซ้อนทับ
3. ตรวจสอบพิกเซลในพื้นที่ซ้อนทับว่ามีพิกเซลที่ไม่โปร่งใสของทั้งสองสไปรต์ซ้อนทับกันหรือไม่

โค้ดตัวอย่าง (แนวคิด)

def check_pixel_perfect_collision(sprite1, sprite2):
    # ตรวจสอบ AABB ก่อน
    if not check_aabb_collision(sprite1.bounds, sprite2.bounds):
        return False
    
    # หาพื้นที่ซ้อนทับ
    overlap_x = max(sprite1.x, sprite2.x)
    overlap_y = max(sprite1.y, sprite2.y)
    overlap_w = min(sprite1.x + sprite1.w, sprite2.x + sprite2.w) - overlap_x
    overlap_h = min(sprite1.y + sprite1.h, sprite2.y + sprite2.h) - overlap_y
    
    # ตรวจสอบพิกเซลในพื้นที่ซ้อนทับ
    for y in range(overlap_h):
        for x in range(overlap_w):
            px1 = sprite1.get_pixel(x + overlap_x - sprite1.x, y + overlap_y - sprite1.y)
            px2 = sprite2.get_pixel(x + overlap_x - sprite2.x, y + overlap_y - sprite2.y)
            if px1.alpha > 0 and px2.alpha > 0:
                return True
    return False

ข้อดีและข้อจำกัด

ข้อดี:

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

ข้อจำกัด:

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

เปรียบเทียบประสิทธิภาพและคำแนะนำ

วิธี	ความเร็ว	ความแม่นยำ	รองรับการหมุน	เหมาะกับเกมแบบไหน
AABB	เร็วมาก	ต่ำ	ไม่	เกมแพลตฟอร์ม 2D เกมที่วัตถุเป็นสี่เหลี่ยม
Circle	เร็ว	ปานกลาง	ไม่จำเป็น	เกมที่วัตถุกลม เกม Top-down
SAT	ปานกลาง	สูง	รองรับ	เกมที่วัตถุหมุนได้ เกมฟิสิกส์ 2D
Pixel-Perfect	ช้า	สูงสุด	รองรับ	เกมต่อสู้ 2D เกมที่ต้องการความแม่นยำสูง

คำแนะนำการเลือกใช้

1. เกมแพลตฟอร์ม 2D แบบคลาสสิก: ใช้ AABB สำหรับการชนกับกำแพงและพื้น อาจใช้ Circle Collision สำหรับศัตรูที่รูปทรงกลม

2. เกม Top-down Shooter: ใช้ Circle Collision สำหรับตัวละครและศัตรู ใช้ AABB สำหรับกำแพงและสิ่งกีดขวาง

3. เกมฟิสิกส์ 2D: ใช้ SAT สำหรับวัตถุที่หมุนได้ เช่น กล่องไม้ ล้อรถ หรือบล็อกที่ต้องการความสมจริง

4. เกมต่อสู้ 2D: ใช้ AABB สำหรับการกรองเบื้องต้น แล้วใช้ Pixel-Perfect Collision สำหรับการตรวจสอบการชนของท่าโจมตีที่ละเอียด

5. เกม 3D: ใช้ AABB หรือ Sphere (วงกลม 3 มิติ) สำหรับการกรองเบื้องต้น แล้วใช้ SAT หรือ GJK สำหรับการตรวจสอบขั้นสูง

เทคนิคเพิ่มประสิทธิภาพ

• Broad Phase vs Narrow Phase: ใช้วิธีง่ายๆ เช่น AABB ใน Broad Phase เพื่อกรองวัตถุที่อาจชนกัน แล้วใช้วิธีแม่นยำกว่าใน Narrow Phase เฉพาะคู่ที่ผ่าน Broad Phase
• Spatial Partitioning: แบ่งพื้นที่เกมเป็นกริดหรือ Quadtree เพื่อลดจำนวนคู่ที่ต้องตรวจสอบ
• Caching: เก็บผลการคำนวณที่ใช้ซ้ำ เช่น แกนของ SAT ถ้าวัตถุไม่ได้หมุน

สรุป

การเลือกอัลกอริทึม Collision Detection ที่เหมาะสมกับเกมของคุณคือสมดุลระหว่างความแม่นยำและประสิทธิภาพ ไม่มีวิธีเดียวที่เหมาะกับทุกสถานการณ์

อัลกอริทึมที่ดีคืออัลกอริทึมที่ตอบโจทย์เกมของคุณ ไม่ใช่อัลกอริทึมที่ซับซ้อนที่สุด

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