跳至主要內容
六边形网格坐标系统

本文主要参考这篇文章hexagons，作者对六边形坐标系统进行了深入的研究和总结，相当具有研究价值。

重要

本文研究的六边形默认是正六边形

一、六边形几何概念

QSTX2025/8/3大约 8 分钟GameDevGameDevHexagons
物理碰撞检测算法总结

碰撞检测是物理引擎和游戏开发中的核心模块

示意图说明

本文中的部分示意图使用 Mermaid 绘制，确保在任何环境下都能正常显示。 :::，负责判断游戏世界中的物体是否发生相交。在现代游戏中，一个场景可能包含数千甚至数万个物体，因此高效的碰撞检测算法至关重要。

碰撞检测通常分为宽阶段（Broad Phase）和窄阶段（Narrow Phase）两个主要步骤：

  • 宽阶段：快速剔除大量明显不相交的物体对，减少需要进入窄阶段精确检测的物体对数
  • 窄阶段：对宽阶段筛选出的潜在碰撞对进行精确的碰撞检测，判断是否真正相交，并计算碰撞信息

一、宽阶段

宽阶段是碰撞检测的第一道关卡，其核心目标是快速。由于不需要精确结果，宽阶段可以使用各种空间划分和层次结构技术来加速。

1. BVH (Bounding Volume Hierarchy)

边界体积层次结构是一种基于树的空间划分技术，通过构建树状结构来组织场景中的物体。

原理简介

BVH 树结构示意

BVH 的核心思想是：

  1. 每个物体都用一个简单的包围体（如 AABB、球、OBB 等）包裹
  2. 将相邻的物体分组，用更大的包围体包裹它们
  3. 递归地进行这个过程，直到形成一棵树

为什么选择 BVH？

优点：

  • 适合动态场景，物体移动时只需局部更新树结构
  • 内存占用相对较低
  • 构建和查询效率平衡良好
  • 不受物体分布影响

缺点：

  • 树的平衡性对性能影响较大
  • 需要合理的分裂策略

常用包围体类型

四种常见包围体对比

包围体类型 优点 缺点 适用场景
AABB 相交检测快，内存小 贴合度差 通用场景
球 相交检测最快，旋转不变 贴合度最差 球形物体
OBB 贴合度好 相交检测慢，需要旋转 复杂形状
k-DOP 贴合度较好，检测较快 构建复杂 高精度需求

Python 伪代码实现

class BVHNode:
    def __init__(self, bounds, left=None, right=None, objects=None):
        self.bounds = bounds
        self.left = left
        self.right = right
        self.objects = objects or []

def build_bvh(objects):
    if len(objects) == 1:
        return BVHNode(compute_bounds(objects[0]), objects=objects)
    
    axis = choose_split_axis(objects)
    objects_sorted = sort_objects_along_axis(objects, axis)
    mid = len(objects_sorted) // 2
    
    left = build_bvh(objects_sorted[:mid])
    right = build_bvh(objects_sorted[mid:])
    
    return BVHNode(merge_bounds(left.bounds, right.bounds), left, right)

def query_bvh(node, bounds):
    if not intersects(node.bounds, bounds):
        return []
    
    if node.objects:
        return node.objects
    
    return query_bvh(node.left, bounds) + query_bvh(node.right, bounds)

优化技巧

  1. SAH (Surface Area Heuristic)：使用表面积启发式来选择最佳分裂平面
  2. 增量更新：物体移动时只更新相关路径，不重建整棵树
  3. BVH 质量优化：周期性重建树以保持良好性能
  4. 并行构建：使用多线程并行构建 BVH

2. 空间网格 (Spatial Grid)

空间网格将空间划分为均匀的网格单元，每个物体只与同一网格或相邻网格中的物体进行检测。

原理简介

空间网格划分示意

空间网格的核心思想：

  1. 将整个游戏空间划分为大小相同的立方体（或正方形）网格
  2. 每个物体根据其位置和大小，被插入到一个或多个网格单元中
  3. 检测碰撞时，只需要检查物体所在的单元及其相邻单元

为什么选择空间网格？

优点：

  • 实现简单直观
  • 插入和查询速度快（O(1) 或 O(常数)）
  • 适合物体均匀分布的场景
  • 特别适合粒子系统等大量小物体

缺点：

  • 网格大小难以选择：太大则每个单元物体太多，太小则物体跨多个单元
  • 内存浪费：空网格仍然占用内存
  • 不适合物体大小差异很大的场景

网格大小选择策略

场景类型 推荐网格大小 原因
粒子系统 2-3倍粒子半径 减少跨单元
均匀分布物体 平均物体大小的1.5-2倍 平衡性能
混合大小物体 分层网格或使用其他算法 空间网格不适合

Python 伪代码实现

class SpatialGrid:
    def __init__(self, cell_size):
        self.cell_size = cell_size
        self.cells = {}
    
    def get_cell_key(self, position):
        x = int(position.x / self.cell_size)
        y = int(position.y / self.cell_size)
        z = int(position.z / self.cell_size)
        return (x, y, z)
    
    def insert(self, obj):
        min_key = self.get_cell_key(obj.bounds.min)
        max_key = self.get_cell_key(obj.bounds.max)
        
        for x in range(min_key[0], max_key[0] + 1):
            for y in range(min_key[1], max_key[1] + 1):
                for z in range(min_key[2], max_key[2] + 1):
                    key = (x, y, z)
                    if key not in self.cells:
                        self.cells[key] = []
                    self.cells[key].append(obj)
    
    def query_potential_collisions(self, obj):
        candidates = set()
        min_key = self.get_cell_key(obj.bounds.min)
        max_key = self.get_cell_key(obj.bounds.max)
        
        for x in range(min_key[0], max_key[0] + 1):
            for y in range(min_key[1], max_key[1] + 1):
                for z in range(min_key[2], max_key[2] + 1):
                    key = (x, y, z)
                    if key in self.cells:
                        candidates.update(self.cells[key])
        
        return candidates - {obj}

优化技巧

  1. 松散网格 (Loose Grid)：允许物体稍微超出网格边界，减少跨单元
  2. 分层网格：使用多层不同大小的网格适应不同大小的物体
  3. 哈希网格：使用哈希表存储只包含物体的单元，节省内存
  4. 时间一致性：利用上一帧的碰撞对，减少重复检测

3. 八叉树 (Octree)

八叉树递归地将空间划分为8个子空间，特别适合三维空间。

原理简介

八叉树划分示意

八叉树的核心思想：

  1. 从一个包含整个场景的根节点开始
  2. 如果节点中的物体数量超过阈值，且未达到最大深度，则将该节点分裂为8个子节点
  3. 将物体分配到对应的子节点中（可能跨多个节点）
  4. 递归地进行这个过程

在二维空间中，类似的数据结构称为四叉树 (Quadtree)。

四叉树 vs 八叉树对比

特性 四叉树 (2D) 八叉树 (3D)
维度 2D 3D
子节点数 4 个 8 个
分裂方式 2×2 划分 2×2×2 划分

为什么选择八叉树？

优点：

  • 自然适应三维空间
  • 适合物体分布不均匀的场景
  • 可以处理各种大小的物体
  • 可视化调试直观

缺点：

  • 树深度可能较大
  • 大物体可能跨很多节点
  • 动态场景需要频繁更新
  • 内存占用相对较高

四叉树 vs 八叉树

特性 四叉树 八叉树
维度 2D 3D
子节点数 4 8
适用场景 2D游戏、UI 3D游戏
内存占用 较低 较高

Python 伪代码实现

class OctreeNode:
    def __init__(self, bounds, depth=0, max_depth=8, max_objects=8):
        self.bounds = bounds
        self.depth = depth
        self.max_depth = max_depth
        self.max_objects = max_objects
        self.objects = []
        self.children = [None] * 8
    
    def insert(self, obj):
        if self.children[0] is not None:
            indices = self.get_child_indices(obj)
            for idx in indices:
                self.children[idx].insert(obj)
            return
        
        self.objects.append(obj)
        
        if len(self.objects) > self.max_objects and self.depth < self.max_depth:
            if self.children[0] is None:
                self.subdivide()
            for obj in self.objects:
                indices = self.get_child_indices(obj)
                for idx in indices:
                    self.children[idx].insert(obj)
            self.objects = []

优化技巧

  1. 松散八叉树 (Loose Octree)：扩大子节点边界，减少跨节点
  2. 线性八叉树：使用数组存储，提高缓存效率
  3. 自适应分裂：根据物体分布选择分裂策略
  4. 批量更新：多个物体移动时批量处理

宽阶段算法对比

算法 最佳场景 时间复杂度 内存 动态更新 实现难度
BVH 通用动态场景 O(log n) 中 优秀 中等
空间网格 均匀分布小物体 O(1) 高 良好 简单
八叉树 不均匀分布 O(log n) 中高 一般 中等

二、窄阶段

窄阶段是碰撞检测的核心，对宽阶段筛选出的潜在碰撞对进行精确的碰撞检测。窄阶段不仅要判断是否相交，还要计算详细的碰撞信息（如接触点、法向量、穿透深度等），这些信息对物理模拟至关重要。

1. SAT (Separating Axis Theorem)

分离轴定理是判断凸多边形碰撞的经典算法，简洁而高效。

原理简介

SAT 分离轴定理示意

SAT 的核心思想：对于两个凸多边形，如果存在一条直线（分离轴），使得两个多边形在这条轴上的投影不重叠，则这两个多边形不相交。

反之，如果在所有潜在的分离轴上投影都重叠，则两个多边形相交。

对于2D凸多边形，需要检查的潜在分离轴是：

  • 每个多边形每条边的法向量

对于3D凸多面体，需要检查的潜在分离轴是：

  • 每个多面体每个面的法向量
  • 两个多面体各取一条边的叉乘

投影重叠判断

  • ❌ maxA < minB 或 maxB < minA → 不相交
  • ✅ 否则 → 投影重叠

为什么选择 SAT？

优点：

  • 原理简单，易于理解和实现
  • 计算效率高
  • 可以直接得到碰撞法向量和穿透深度
  • 数值稳定性好

缺点：

  • 只适用于凸多边形/多面体
  • 3D情况下需要检查的轴数量较多
  • 不直接提供接触点（需要额外计算）

凸 vs 凹

SAT 只适用于凸形状。对于凹形状，需要先进行凸分解，将其分解为多个凸形状的组合。

什么是凸形状？

对于形状内任意两点，连接它们的线段完全在形状内部，则该形状为凸形状。

QSTX2025/4/22大约 24 分钟GameDevGameDevPhysicsCollision Detection
线段与AABB求交的算法

如何快速判断任意线段与任意AABB是否相交？首先想到的方法是借助射线与AABB求交的算法，获得射线进入和离开的时机，在射线与AABB相交的前提下保证进入时机在线段终点之前。

下面是搜集到的三种算法即实现，并且通过添加轴的的维度完全可以应用于三维情况。

零、 数据结构

import random
import time
import numpy as np
import matplotlib.pyplot as plt


class Vec2D:
    def __init__(self, x, y):
        self.v = np.array([x, y])

    def __sub__(self, other):
        return Vec2D(self.v[0] - other.v[0], self.v[1] - other.v[1])

    def __getitem__(self, index):
        return self.v[index]

    def __mul__(self, scalar):
        return Vec2D(self.v[0] * scalar, self.v[1] * scalar)

    def __add__(self, other):
        return Vec2D(self.v[0] + other.v[0], self.v[1] + other.v[1])

    def ToString(self):
        return f'({self.v[0]},{self.v[1]})'

class Rect:
    def __init__(self, min_x, min_y, max_x, max_y):
        self.min = Vec2D(min_x, min_y)
        self.max = Vec2D(max_x, max_y)

    def ToString(self):
        return f'{{ {self.min.ToString()},{self.max.ToString()} }}'
QSTX2025/3/25大约 7 分钟GameDevGameDevGraphics
且试天下
Copyright © 2026 QSTX