【unity小技巧】Unity 四叉树算法实现空间分割、物体存储并进行查询和碰撞检测

devtools/2024/11/26 22:01:08/

文章目录

  • 前言
  • 四叉树的工作原理
  • 四叉树的优点
  • 四叉树的应用场景
  • 案例
    • 四叉树实现空间分割和物体存储并进行查询
        • 四叉树节点类
        • 使用示例
      • 解释
    • 四叉树实现碰撞检测
      • 四叉树的构建
      • 四叉树的实现步骤
        • 1. 创建四叉树的基本类
        • 2. 在 Unity 中使用四叉树进行碰撞检测
      • 3. 解释
      • 4. 优势
      • 5. 注意事项
  • 完结

前言

四叉树(Quadtree)是一种树形数据结构,广泛用于二维空间中的空间分割。它通过递归将空间分成四个子区域来优化数据查找、碰撞检测、视野剔除等操作。在 Unity 中,四叉树通常用于优化大规模物体的碰撞检测、可见性检测或物体管理等任务,避免直接遍历所有物体,提升性能。

四叉树通过空间分割优化了大规模物体的管理和查询,广泛应用于游戏开发中的碰撞检测、物体管理和视野剔除等场景。在 Unity 中实现四叉树能够显著提升大规模场景的性能,避免了全局遍历物体的高昂成本。
在 Unity 中,四叉树(QuadTree)是一种常用的空间分割算法,特别适用于碰撞检测等需要处理大量物体的场景。四叉树的基本思想是将空间递归地划分为四个子区域,从而有效地减少碰撞检测时的计算量。通过这种方式,四叉树可以将物体分到不同的区域,避免在整个场景中进行每一对物体的碰撞检测,从而提高性能。

四叉树的工作原理

  1. 空间分割:四叉树通过递归将一个区域划分成四个子区域(通常是矩形或正方形)。每次分割都会将空间进一步细化,直到每个区域中包含的物体数小于或等于一个预设的阈值。
  2. 节点存储:每个四叉树节点包含四个子节点(代表四个子区域),以及该区域内的物体。如果当前区域已经足够小(例如达到了一个物体数量的阈值),就会将物体存储在该节点中,而不再继续细分。

四叉树的优点

  • 提高查询效率:通过分割空间,查询时可以快速定位物体,而不是遍历所有物体。
  • 优化碰撞检测:避免对所有物体进行碰撞检测,只检查位于同一子区域或相邻区域的物体。
  • 内存效率:四叉树有效地组织数据,减少不必要的计算和存储。

四叉树的应用场景

  1. 碰撞检测:四叉树可以优化物体之间的碰撞检测,只检查位于相同或相邻区域的物体,避免全局遍历所有物体。
  2. 视野剔除:通过四叉树,可以快速判断哪些物体在摄像机视野内,从而只渲染那些物体,节省计算资源。
  3. 区域管理:用于管理游戏中的区域数据,如生成和管理场景中的物体、敌人、道具等。

案例

四叉树实现空间分割和物体存储并进行查询

下面是一个简单的四叉树实现,帮助理解其基本概念。这个例子主要展示如何在 2D 空间中进行空间分割和物体存储。

四叉树节点类
using System;
using System.Collections.Generic;
using UnityEngine;// 定义一个简单的物体类
public class GameObject
{public Vector2 position;public string name;public GameObject(Vector2 position, string name){this.position = position;this.name = name;}
}// 四叉树节点类
public class Quadtree
{public Rect boundary; // 当前区域的边界public List<GameObject> objects; // 当前区域的物体列表public Quadtree[] children; // 四个子区域public bool divided; // 是否已经分割过private int capacity; // 每个节点容纳的最大物体数量// 构造函数public Quadtree(Rect boundary, int capacity){this.boundary = boundary;this.capacity = capacity;this.objects = new List<GameObject>();this.divided = false;}// 插入物体到四叉树中public bool Insert(GameObject obj){// 如果物体不在当前节点的边界内,则不插入if (!boundary.Contains(obj.position))return false;// 如果当前节点已经存满物体if (objects.Count < capacity){objects.Add(obj);return true;}// 如果当前节点已经分割过子节点,则将物体插入到合适的子节点if (!divided)Subdivide();// 尝试将物体插入子节点foreach (var child in children){if (child.Insert(obj))return true;}return false; // 如果无法插入,返回 false}// 分割当前区域为四个子区域public void Subdivide(){float x = boundary.xMin;float y = boundary.yMin;float w = boundary.width / 2;float h = boundary.height / 2;// 创建四个子节点children = new Quadtree[4];children[0] = new Quadtree(new Rect(x, y, w, h), capacity);children[1] = new Quadtree(new Rect(x + w, y, w, h), capacity);children[2] = new Quadtree(new Rect(x, y + h, w, h), capacity);children[3] = new Quadtree(new Rect(x + w, y + h, w, h), capacity);divided = true;// 将当前节点中的物体插入到子节点中for (int i = 0; i < objects.Count; i++){foreach (var child in children){if (child.Insert(objects[i]))break;}}objects.Clear(); // 清空当前节点中的物体}// 查询指定区域内的所有物体public List<GameObject> Query(Rect range){List<GameObject> found = new List<GameObject>();// 如果查询区域不与当前区域相交,直接返回空列表if (!boundary.Overlaps(range))return found;// 检查当前节点中的物体foreach (var obj in objects){if (range.Contains(obj.position))found.Add(obj);}// 如果有子节点,查询子节点if (divided){foreach (var child in children){found.AddRange(child.Query(range));}}return found;}
}
使用示例

下面是一个简单的示例,演示如何使用四叉树来管理物体并进行查询。

using UnityEngine;public class QuadtreeExample : MonoBehaviour
{private Quadtree quadtree;void Start(){// 创建一个大小为 100x100 的四叉树,最大物体容量为 4quadtree = new Quadtree(new Rect(0, 0, 100, 100), 4);// 插入一些物体quadtree.Insert(new GameObject(new Vector2(10, 10), "Object 1"));quadtree.Insert(new GameObject(new Vector2(20, 20), "Object 2"));quadtree.Insert(new GameObject(new Vector2(30, 30), "Object 3"));quadtree.Insert(new GameObject(new Vector2(40, 40), "Object 4"));quadtree.Insert(new GameObject(new Vector2(60, 60), "Object 5"));// 查询区域内的物体Rect queryRange = new Rect(0, 0, 50, 50);var foundObjects = quadtree.Query(queryRange);// 输出查询结果foreach (var obj in foundObjects){Debug.Log($"Found: {obj.name} at {obj.position}");}}
}

解释

  • Insert 方法:负责插入物体。如果当前节点已满并且没有分割过子节点,则会调用 Subdivide 方法将空间分割成四个子区域。
  • Query 方法:负责查询指定区域内的物体。它会检查当前节点的物体是否与查询区域相交,如果有交集,则返回这些物体。同时,它会递归查询子节点。
  • Subdivide 方法:当节点满时,将当前区域分割为四个子区域,并把物体分配到适当的子区域。

四叉树实现碰撞检测

Unity 自带的碰撞系统已经非常强大并且适用于大部分情况,但在以下情况下使用四叉树等空间分割算法会更加高效:

  • 需要在大量物体间快速进行碰撞检测时。
  • 需要自定义碰撞规则或需求,超出物理引擎的处理范围。
  • 场景中有大量静态物体或动态物体,且物体分布不均匀。
  • 需要减少物理引擎开销或优化特定类型的碰撞检测。

四叉树的构建

  1. 定义区域:首先定义一个边界区域,通常是整个场景的边界或某个特定的区域。
  2. 插入物体:将每个物体插入到四叉树的对应位置。每个物体通过其位置来确定应该放置在哪个节点(象限)中。
  3. 分割:当一个节点中的物体数量超过一定的阈值时,就会将该节点分割成四个子节点。
  4. 查询和碰撞检测:在查询时,四叉树帮助你快速确定哪些物体可能发生碰撞,只检测那些处于同一子区域或相邻子区域的物体。

四叉树的实现步骤

假设我们正在使用 Unity 进行碰撞检测,我们可以通过以下步骤来实现四叉树的碰撞检测:

1. 创建四叉树的基本类
using System.Collections.Generic;
using UnityEngine;public class QuadTree
{private Rect boundary;      // 四叉树的边界区域private int capacity;       // 每个节点最大存放物体的数量private List<GameObject> objects;  // 当前节点包含的物体private QuadTree[] nodes;  // 四个子节点public QuadTree(Rect boundary, int capacity){this.boundary = boundary;this.capacity = capacity;objects = new List<GameObject>();nodes = new QuadTree[4];}// 将物体插入四叉树public void Insert(GameObject obj){// 判断物体是否在当前节点的边界内if (!boundary.Contains(obj.transform.position))return;// 如果当前节点没有分裂且物体数量少于阈值,直接插入if (objects.Count < capacity){objects.Add(obj);return;}// 否则,分裂当前节点if (nodes[0] == null)Subdivide();// 将当前节点的物体转移到子节点foreach (var item in objects){foreach (var node in nodes)node.Insert(item);}objects.Clear();// 继续插入新的物体foreach (var node in nodes)node.Insert(obj);}// 子节点分割private void Subdivide(){float halfWidth = boundary.width / 2;float halfHeight = boundary.height / 2;nodes[0] = new QuadTree(new Rect(boundary.x, boundary.y, halfWidth, halfHeight), capacity);nodes[1] = new QuadTree(new Rect(boundary.x + halfWidth, boundary.y, halfWidth, halfHeight), capacity);nodes[2] = new QuadTree(new Rect(boundary.x, boundary.y + halfHeight, halfWidth, halfHeight), capacity);nodes[3] = new QuadTree(new Rect(boundary.x + halfWidth, boundary.y + halfHeight, halfWidth, halfHeight), capacity);}// 查询可能发生碰撞的物体public List<GameObject> Query(Rect range){List<GameObject> foundObjects = new List<GameObject>();// 如果查询范围不与当前节点的边界相交,则返回空if (!boundary.Overlaps(range))return foundObjects;// 在当前节点内查找物体foreach (var obj in objects){if (range.Contains(obj.transform.position))foundObjects.Add(obj);}// 查询子节点if (nodes[0] != null){foreach (var node in nodes){foundObjects.AddRange(node.Query(range));}}return foundObjects;}
}
2. 在 Unity 中使用四叉树进行碰撞检测

在 Unity 的 Update 方法中,我们可以每帧都查询物体是否发生碰撞。比如,我们可以使用四叉树来查找玩家与场景中其他物体的碰撞:

public class QuadTreeCollision : MonoBehaviour
{public QuadTree quadTree;public float range = 10f;void Start(){Rect sceneBounds = new Rect(0, 0, 100, 100);  // 假设场景大小为100x100quadTree = new QuadTree(sceneBounds, 4);// 插入所有物体foreach (var obj in FindObjectsOfType<GameObject>()){quadTree.Insert(obj);}}void Update(){// 检查玩家的范围是否与其他物体发生碰撞Rect playerRange = new Rect(transform.position.x - range, transform.position.y - range, range * 2, range * 2);List<GameObject> nearbyObjects = quadTree.Query(playerRange);// 进行碰撞检测foreach (var obj in nearbyObjects){if (obj != gameObject && IsColliding(obj)){// 处理碰撞Debug.Log("Collision detected with " + obj.name);}}}bool IsColliding(GameObject other){// 简单的碰撞检测,可以根据需求实现return Vector3.Distance(transform.position, other.transform.position) < range;}
}

3. 解释

  • QuadTree 类负责管理四叉树的结构和物体的插入与查询操作。每个 QuadTree 节点包含了一个 boundary(矩形区域)和一个 objects 列表(存储该区域内的物体)。
  • Insert 方法用于将物体插入四叉树,若当前节点的物体数量超过阈值,则分裂节点。
  • Query 方法用于查询给定范围内的所有物体。
  • QuadTreeCollision 类中,我们在每帧检查玩家的周围区域,并通过 quadTree.Query 方法查找与玩家可能发生碰撞的物体。如果这些物体与玩家发生碰撞,则执行相应的碰撞处理。

4. 优势

  • 性能提升:四叉树通过将场景划分成更小的区域,减少了每一帧需要进行的碰撞检测对比次数,尤其在物体较多时效果显著。
  • 内存使用:四叉树结构相对高效,因为它仅会存储活跃区域内的物体,而不会一次性存储所有物体。

5. 注意事项

  • 四叉树适用于二维空间中的物体,若是3D游戏,可能需要使用八叉树(Octree)等其他空间分割结构。
  • 四叉树的分割会带来一定的性能开销,尤其在频繁分割和合并节点时,可能需要平衡容量和分割频率。

这样,四叉树就能帮助你高效地进行碰撞检测,特别是当场景中有大量物体时,能大大减少计算量。

完结

赠人玫瑰,手有余香!如果文章内容对你有所帮助,请不要吝啬你的点赞评论和关注,你的每一次支持都是我不断创作的最大动力。当然如果你发现了文章中存在错误或者有更好的解决方法,也欢迎评论私信告诉我哦!

好了,我是向宇,https://xiangyu.blog.csdn.net

一位在小公司默默奋斗的开发者,闲暇之余,边学习边记录分享,站在巨人的肩膀上,通过学习前辈们的经验总是会给我很多帮助和启发!如果你遇到任何问题,也欢迎你评论私信或者加群找我, 虽然有些问题我也不一定会,但是我会查阅各方资料,争取给出最好的建议,希望可以帮助更多想学编程的人,共勉~
在这里插入图片描述


http://www.ppmy.cn/devtools/137230.html

相关文章

实时质检系统—静音检测功能设置流程

设置流程 1. 设置静音检测时间 在实时质检系统中&#xff0c;有一静音检测功能&#xff1a;可以对主叫或被叫在接通后的规定时间内开启静音检测。例&#xff1a;被叫静音检测配置设置了10&#xff0c;那么质检电话在接通后的10秒内&#xff0c;开启静音检测&#xff0c;如果被…

Jira关键git

在使用 Git 和 Jira 管理项目时&#xff0c;可以通过在 Git 提交信息中关联 Jira 工单&#xff0c;同时实现关闭相关任务的功能。以下是操作步骤&#xff1a; 1. 确保 Git 和 Jira 集成 确认 Jira 已与您的代码库&#xff08;如 GitHub、GitLab 或 Bitbucket&#xff09;正确…

记录一个奇怪的前端布局现象

背景 我再根尚硅谷的教程学着写页面时&#xff0c;用padding和margin使li里的文本水平垂直居中我看到下一级的时候发现li添加了一个div后&#xff0c;结果和老师的代码有所出入我就写了个demo 加padding/margin的demo <!DOCTYPE html> <html lang"en">…

Linux中的权限管理

Linux 权限管理主要是指对 Linux 系统中的文件和目录进行权限设置和管理&#xff0c;以确保系统的安全性和稳定性。以下是对 Linux 中权限管理的详细介绍&#xff1a; 一、权限的基本概念 在 Linux 系统中&#xff0c;权限是指某个特定的用户具有特定的系统资源使用权利。Lin…

大数据新视界 -- Hive 数据仓库:构建高效数据存储的基石(下)(2/ 30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

【学习笔记】AD智能PDF导出(装配文件)

2.下一步“NEXT” 3.选择文件名称&#xff0c;下一步“NEXT” 4.可选导出原材料的BOM表 右键选择装配图“Create Assembly Drawings” 5.可以双击下图方框&#xff0c;或者右键需要编辑的标题&#xff0c;选择“Properties”&#xff0c;勾选如下图 6.装配文件&#xff0c;添加…

第5-1节:SpringBoot对SpringMVC的自动配置

我的后端学习大纲 SpringBoot学习大纲 1、SpringBoot对SpringMVC自动配置概览

zotero安卓测试版下载和使用

2023年年底&#xff0c;Zotero官方就已经推出了安卓版的测试版Zotero for Android (beta),&#xff0c;但名额有限且只能通过Google商店下载。此外&#xff0c;还有一些第三方开发的安卓应用&#xff0c;如Zoo for Zotero、ZotDroid等。 在首次使用Zotero安卓版时&#xff0c;用…