四叉树相关介绍
四叉树（QuadTree）是一棵包含树根（Root）的树，它的每个内部结点都有4个子结点。树中的每个结点都对应一个正方形。如果结点有子结点，则它们对应的正方形是4个象限,四叉树常见的应用有图像处理、空间数据索引、2D中的快速碰撞检测、稀疏数据等。
代码编写
1. 创建地图
首先我们创建一个边界条件,确定地图的四个方向的长度,便于后面生成食物
/**
* 地图宽度
*/
public static width = 5000;
public static widthHalf = SnackGameDef.width / 2;
/**
* 地图高
*/
public static height = 5000;
public static heightHalf = SnackGameDef.height / 2;
然后根据这个边界创建一个对应的场景地图
private async initScene() {
let scene: GameObject;
// this.sceneArr.push(scene);
// left
scene = await UtilEx.AssetEx.spawnAsync("197386", "scene")
await scene.asyncReady();
scene.worldTransform.position = new mw.Vector(0, SnackGameDef.widthHalf, 0);
scene.worldTransform.scale = new mw.Vector(SnackGameDef.widthHalf / 100 * 2 + 0.1, 0.1, 1);
if (scene instanceof Model) {
scene.setMaterial("186469");
scene.createMaterialInstance(0);
UtilEx.TypeEx.setColor(scene, "#FF0000FF");
}
// right
scene = await UtilEx.AssetEx.spawnAsync("197386", "scene")
await scene.asyncReady();
scene.worldTransform.position = new mw.Vector(0, -SnackGameDef.widthHalf, 0);
scene.worldTransform.scale = new mw.Vector(SnackGameDef.widthHalf / 100 * 2 + 0.1, 0.1, 1)
if (scene instanceof Model) {
scene.setMaterial("186469");
scene.createMaterialInstance(0);
UtilEx.TypeEx.setColor(scene, "#FF0000FF");
}
// front
scene = await UtilEx.AssetEx.spawnAsync("197386", "scene")
await scene.asyncReady();
scene.worldTransform.position = new mw.Vector(SnackGameDef.heightHalf, 0, 0);
scene.worldTransform.scale = new mw.Vector(0.1, SnackGameDef.heightHalf / 100 * 2 + 0.1, 1);
if (scene instanceof Model) {
scene.setMaterial("186469");
scene.createMaterialInstance(0);
UtilEx.TypeEx.setColor(scene, "#FF0000FF");
}
// back
scene = await UtilEx.AssetEx.spawnAsync("197386", "scene")
await scene.asyncReady();
scene.worldTransform.position = new mw.Vector(-SnackGameDef.heightHalf, 0, 0);
scene.worldTransform.scale = new mw.Vector(0.1, SnackGameDef.heightHalf / 100 * 2 + 0.1, 1);
if (scene instanceof Model) {
scene.setMaterial("186469");
scene.createMaterialInstance(0);
UtilEx.TypeEx.setColor(scene, "#FF0000FF");
}
}
2. 生成食物
在地图中随机一个点位,生成食物
spawnFood() {
let x = IOMath.randomInt(-SnackGameDef.heightHalf, SnackGameDef.heightHalf);
let y = IOMath.randomInt(-SnackGameDef.widthHalf, SnackGameDef.widthHalf);
let food: GameObject = GameObject.spawn("food")
food.worldTransform.position = new Vector(x, y, 0);
}
3. 记录食物位置
这里我们要用到一个地图记录的方法四叉树
/**
* @Description : 空间划分，用于检测玩家是否在交互范围内
*/
export class Point<T> {
x: number;
y: number;
goGuid: string;
info:T;
quadTree: QuadTree;//所属的父亲节点
constructor(x: number, y: number, goGuid: string,info?:T){
this.x = x;
this.y = y;
this.goGuid = goGuid;
this.info = info;
}
}
export class Rectangle {
//中心点坐标
x: number;
y: number;
//宽度一半
halfWidth: number;
//高度一半
halfHeight: number;
/**
* @description: 构建一个区域
* @param x 区域中心点x坐标
* @param y 区域中心点y坐标
* @param w 区域宽度的一半
* @param h 区域高度的一半
* @return
*/
constructor(x: number, y: number, w: number, h: number) {
this.x = x;
this.y = y;
this.halfWidth = w;
this.halfHeight = h;
}
/**
* @description: 点是否在区域内
* @param {Point} point
* @return {*}
*/
contains(point: Point<any>) {
return (point.x >= this.x - this.halfWidth
&& point.x < this.x + this.halfWidth
&& point.y >= this.y - this.halfHeight
&& point.y < this.y + this.halfHeight);
}
/**
* @description: 两个区域是否相交
* @param {Rectangle} range
* @return {*}
*/
intersects(range: Rectangle) {
return !(range.x - range.halfWidth > this.x + this.halfWidth
|| range.x + range.halfWidth < this.x - this.halfWidth
|| range.y - range.halfHeight > this.y + this.halfHeight
|| range.y + range.halfHeight < this.y - this.halfHeight);
}
}
/**
* 存储点guid和父节点的映射
*/
const nodeMap: Map<string, QuadTree> = new Map<string, QuadTree>();
export class QuadTree {
boundary: Rectangle;
capacity: number;
//包含的点
points: Point<any>[];
// 细分标记
divided: boolean;
northeast: QuadTree;
northwest: QuadTree;
southeast: QuadTree;
southwest: QuadTree;
constructor(boundary: Rectangle, n: number) {
this.boundary = boundary;
this.capacity = n;
this.points = [];
this.divided = false;
}
/**
* @description: 划分四个区域
* @return {*}
*/
subdivide(): void {
let x = this.boundary.x;
let y = this.boundary.y;
let w = this.boundary.halfWidth;
let h = this.boundary.halfHeight;
let ne = new Rectangle(x + w / 2, y - h / 2, w / 2, h / 2);
this.northeast = new QuadTree(ne, this.capacity);
let nw = new Rectangle(x - w / 2, y - h / 2, w / 2, h / 2);
this.northwest = new QuadTree(nw, this.capacity);
let se = new Rectangle(x + w / 2, y + h / 2, w / 2, h / 2);
this.southeast = new QuadTree(se, this.capacity);
let sw = new Rectangle(x - w / 2, y + h / 2, w / 2, h / 2);
this.southwest = new QuadTree(sw, this.capacity);
this.divided = true;
}
/**
* @description: 根据区域插入点
* @param {Point} point 点位
* @return {*}
*/
insert(point: Point<any>): boolean {
if (!this.boundary.contains(point)) {
return false;
}
if (this.points.length < this.capacity) {
this.points.push(point);
//记录下点位和父节点的映射
nodeMap.set(point.goGuid, this);
return true;
} else {
if (!this.divided) {
this.subdivide();
}
if (this.northeast.insert(point)) {
return true;
} else if (this.northwest.insert(point)) {
return true;
} else if (this.southeast.insert(point)) {
return true;
} else if (this.southwest.insert(point)) {
return true;
}
}
}
delete(point:Point<any>) {
let index = this.points.findIndex(findPoint => point== findPoint);
if (index != -1) {
this.points.splice(index, 1);
if (nodeMap.has(point.goGuid)) {
nodeMap.delete(point.goGuid);
}
}
if (this.divided) {
this.northwest.delete(point);
this.northeast.delete(point);
this.southwest.delete(point);
this.southeast.delete(point);
}
}
/**
* @description: 动态更新点的位置
* @param point 新的点
* @return
*/
update(point: Point<any>) {
if (!nodeMap.has(point.goGuid)) {
this.insert(point);
} else {
let node = nodeMap.get(point.goGuid);//原来的父节点
if (node.boundary.contains(point)) {
//如果还在原来的区域内，直接更新位置
node.points[node.points.findIndex(v => v.goGuid === point.goGuid)] = point;
} else {
//不同的父节点,先删除再插入
node.points.splice(node.points.findIndex(v => v.goGuid === point.goGuid), 1);
this.insert(point);
}
}
}
/**
* @description: 根据区域查找点
* @param {Rectangle} range 矩形范围
* @param {Point} found 找到的点数组
* @return {*}
*/
query(range: Rectangle, found: Point<any>[]) {
if (!found) {
found = [];
}
if (!this.boundary.intersects(range)) {
return found;
} else {
for (let p of this.points) {
if (range.contains(p)) {
found.push(p);
}
}
if (this.divided) {
this.northwest.query(range, found);
this.northeast.query(range, found);
this.southwest.query(range, found);
this.southeast.query(range, found);
}
}
return found;
}
}
我们写一个关于食物的类,修改一下食物生成函数
class FoodInfo{
goGuid:string
go:GameObject
}
uuid=0
spawnFood() {
let x = IOMath.randomInt(-SnackGameDef.heightHalf, SnackGameDef.heightHalf);
let y = IOMath.randomInt(-SnackGameDef.widthHalf, SnackGameDef.widthHalf);
let go: GameObject = GameObject.spawn("food")
go.worldTransform.position = new Vector(x, y, 0);
let info =new FoodInfo()
info.goGuid=uuid++
info.go=go
let point = new Point(x, y, info.guid, info);
return point
}
然后将上面生成的食物放到四叉树中
quadTree
spawn(){
this.quadTree = new QuadTree(new Rectangle(0, 0, SnackGameDef.widthHalf, SnackGameDef.heightHalf), 4);
for(let i=0;i<100;i++){
let point=spawnFood();
this.quadTree.insert(point);
}
}
这样就保存下了食物,方便后面的查询,修改
这波分享是真的猛
偷学
