我有一个 玩家的坐标，有一堆的怪物坐标，我想找出，玩家距离最近的那个怪物。
除了 for循环逐个查找，还有什么比较优秀的快速算法吗？或者方便的api。
我 听说过 四叉树碰撞检测
好的，谢谢我去了解一下。
/**
* [二进制堆](https://eloquentjavascript.net/1st_edition/appendix2.html)
*/
export class BinaryHeap<T> {
/** 二叉树 */
private content: T[] = [];
/** 分数计算方法 */
private scoreFunction: (node: T) => number = null;
/**
* @param scoreFunction 分数计算方法
*/
constructor(scoreFunction: (node: T) => number) {
this.content = [];
this.scoreFunction = scoreFunction;
}
/**
* 向树中push一个元素，并将它冒泡排序
* @param element
*/
public push(element: T): void {
// Add the new element to the end of the array.
// 将新元素添加到数组的末尾。
this.content.push(element);
// Allow it to bubble up.
// 让它冒泡。
this.bubbleUp(this.content.length - 1);
console.log(this.content);
}
/**
* 移除树最后一个元素
*/
public pop(): T {
// Store the first element so we can return it later.
// 存储第一个元素，以便稍后返回。
let result = this.content[0];
// Get the element at the end of the array.
// 获取数组末尾的元素。
let end = this.content.pop();
// If there are any elements left, put the end element at the start, and let it sink down.
// 如果还剩下任何元素，将end元素放在开始位置，让它下沉。
if (this.content.length > 0) {
this.content[0] = end;
this.sinkDown(0);
}
return result;
}
public remove(node: T): void {
let length = this.content.length;
// To remove a value, we must search through the array to find it.
// 要删除一个值，必须在数组中搜索它。
for (let i = 0; i < length; i++) {
if (this.content[i] != node) continue;
// When it is found, the process seen in 'pop' is repeated to fill up the hole.
// 找到后，重复“pop”中的过程，将洞填满。
let end = this.content.pop();
// If the element we popped was the one we needed to remove,we're done.
// 如果弹出的元素是需要删除的元素，那么就完成了。
if (i == length - 1) break;
// Otherwise, we replace the removed element with the popped one, and allow it to float up or sink down as appropriate.
// 否则，我们将删除的元素替换为弹出的元素，并允许它根据情况向上或向下浮动。
this.content[i] = end;
this.bubbleUp(i);
this.sinkDown(i);
break;
}
}
public size(): number {
return this.content.length;
}
/**
* 冒泡排序
* @param n 索引
*/
private bubbleUp(n: number): void {
// Fetch the element that has to be moved.
// 获取必须移动的元素。
let element = this.content[n], score = this.scoreFunction(element);
// When at 0, an element can not go up any further.
// 当值为0时，元素不能再向上移动了。
while (n > 0) {
// Compute the parent element's index, and fetch it.
// 计算父元素的索引，并获取它。
let parentN = Math.floor((n + 1) / 2) - 1,
parent = this.content[parentN];
// If the parent has a lesser score, things are in order and we are done.
// 如果父级的分数较低，事情就会有条不紊，我们也就完事了。
if (score >= this.scoreFunction(parent))
break;
// Otherwise, swap the parent with the current element and continue.
// 否则，将父元素与当前元素交换并继续。
this.content[parentN] = element;
this.content[n] = parent;
n = parentN;
}
}
private sinkDown(n: number): void {
// Look up the target element and its score.
// 查找目标元素及其得分。
let length = this.content.length;
let element = this.content[n];
let elemScore = this.scoreFunction(element);
while (true) {
// Compute the indices of the child elements.
// 计算子元素的索引。
let child2N = (n + 1) * 2;
let child1N = child2N - 1;
// This is used to store the new position of the element,if any.
// 这用于存储元素的新位置(如果有的话)。
let swap: number = null;
// If the first child exists (is inside the array)...
// 如果第一个子元素存在(在数组中)…
let child1Score = 0;
if (child1N < length) {
// Look it up and compute its score.
// 查找并计算它的分数。
let child1 = this.content[child1N];
child1Score = this.scoreFunction(child1);
// If the score is less than our element's, we need to swap.
// 如果分数小于元素的分数，则需要进行交换。
if (child1Score < elemScore) {
swap = child1N;
}
}
// Do the same checks for the other child.
// 对另一个子级做同样的检查。
if (child2N < length) {
let child2 = this.content[child2N];
let child2Score = this.scoreFunction(child2);
if (child2Score < (swap == null ? elemScore : child1Score)) {
swap = child2N;
}
}
// No need to swap further, we are done.
// 不需要进一步交换，我们完成了。
if (swap == null) {
break;
}
// Otherwise, swap and continue.
// 否则，交换并继续。
this.content[n] = this.content[swap];
this.content[swap] = element;
n = swap;
}
}
}
改进版：
export class RectData {
public x: number;
public y: number;
public width: number;
public height: number;
public anchorX: number = 0;
public anchorY: number = 0;
public constructor(x: number, y: number, width: number, height: number, anchorX: number, anchorY: number) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.anchorX = anchorX;
this.anchorY = anchorY;
}
}
export class Quadtree {
/** 单节点最大的对象数 */
private max_objects: number = 10;
/** 节点分裂的最大次数 */
private max_levels: number = 4;
/** 当前分裂的次数 */
private level: number = 0;
/** 检测区域 锚点左下角 */
private bounds: RectData = null;
/** 区域内的所有对象 */
private objects: RectData[] = [];
/** 子节点 固定为4个 */
private nodes: Quadtree[] = [];
/**
* @param bounds
* **区域** bounds of the node { x, y, width, height }
* @param max_objects
* **单节点最大的对象数** (optional) max objects a node can hold before splitting into 4 subnodes (default: 10)
* @param max_levels
* **节点分裂的最大次数** (optional) total max levels inside root Quadtree (default: 4)
* @param level
* **当前分裂的次数** (optional) depth level, required for subnodes (default: 0)
*/
public constructor(bounds: RectData, max_objects: number = 10, max_levels: number = 4, level: number = 0) {
// 设置单节点最大的对象数
this.max_objects = max_objects;
// 设置节点分裂的最大次数
this.max_levels = max_levels;
this.level = level;
this.bounds = bounds;
// this.bounds.anchorX = 0;
// this.bounds.anchorY = 0;
this.objects = [];
this.nodes = [];
}
/**
* Split the node into 4 subnodes
* 将节点划分为4个子节点
*/
public split(): void {
// 即将分裂的总次数
let nextLevel = this.level + 1;
// 分裂节点的宽
let subWidth = this.bounds.width / 2;
// 分裂节点的高
let subHeight = this.bounds.height / 2;
// 位置
let x = this.bounds.x;
let y = this.bounds.y;
// ---------------
// | 2 | 3 |
// | 区域 | 区域 |
// |------|------|
// | 1 | 0 |
// | 区域 | 区域 |
// ---------------
// 顶部右侧子节点
this.nodes[0] = new Quadtree(
new RectData(
x + subWidth - subWidth * this.bounds.anchorX,
y - subHeight * this.bounds.anchorY,
subWidth,
subHeight,
this.bounds.anchorX,
this.bounds.anchorY),
this.max_objects,
this.max_levels,
nextLevel);
// 顶部左侧子节点
this.nodes[1] = new Quadtree(
new RectData(
x - subWidth * this.bounds.anchorX,
y - subHeight * this.bounds.anchorY,
subWidth,
subHeight,
this.bounds.anchorX,
this.bounds.anchorY),
this.max_objects,
this.max_levels,
nextLevel);
// 底部左侧子节点
this.nodes[2] = new Quadtree(
new RectData(
x - subWidth * this.bounds.anchorX,
y + subHeight - subHeight * this.bounds.anchorY,
subWidth,
subHeight,
this.bounds.anchorX,
this.bounds.anchorY),
this.max_objects,
this.max_levels,
nextLevel);
// 底部右侧子节点
this.nodes[3] = new Quadtree(
new RectData(
x + subWidth - subWidth * this.bounds.anchorX,
y + subHeight - subHeight * this.bounds.anchorY,
subWidth,
subHeight,
this.bounds.anchorX,
this.bounds.anchorY),
this.max_objects,
this.max_levels,
nextLevel);
}
/**
* Determine which node the object belongs to
* 确定对象属于哪些子节点
* @param Object pRect bounds of the area to be checked, with x, y, width, height
* @return Array an array of indexes of the intersecting subnodes
* (0-3 = top-right, top-left, bottom-left, bottom-right / ne, nw, sw, se)
*/
public getIndex(pRect: RectData): number[] {
let indexes: number[] = [];
// 区域中心X值
let subWidth = this.bounds.width / 2;
let subHeight = this.bounds.height / 2;
let verticalMidpoint = this.bounds.x + subWidth - this.bounds.width * this.bounds.anchorX;
// 区域中心Y值
let horizontalMidpoint = this.bounds.y + subHeight - this.bounds.height * this.bounds.anchorY;
console.log(verticalMidpoint, horizontalMidpoint);
let pRectSubWidth = pRect.width * pRect.anchorX;
let pRectSubHeight = pRect.height * pRect.anchorY;
// Y小于中心点Y
let startIsNorth = pRect.y - pRectSubHeight < horizontalMidpoint;
// X小于中心点X
let startIsWest = pRect.x - pRectSubWidth < verticalMidpoint;
// 左上角X大于中心点X
let endIsEast = pRect.x + pRect.width - pRectSubWidth > verticalMidpoint;
// 左上角Y大于中心点Y
let endIsSouth = pRect.y + pRect.height - pRectSubHeight > horizontalMidpoint;
// Y小于中心点Y且左上角X大于中心点X
if (startIsNorth && endIsEast) {
indexes.push(0);
}
// X小于中心点X且Y小于中心点Y
if (startIsWest && startIsNorth) {
indexes.push(1);
}
// X小于中心点X且左上角Y大于中心点Y
if (startIsWest && endIsSouth) {
indexes.push(2);
}
// 左上角X大于中心点X且左上角Y大于中心点Y
if (endIsEast && endIsSouth) {
indexes.push(3);
}
return indexes;
}
/**
* Insert the object into the node. If the node
* exceeds the capacity, it will split and add all
* objects to their corresponding subnodes.
* 将对象插入到节点中。如果节点超过容量，则将所有对象拆分并添加到相应的子节点中。
* @param Object pRect bounds of the object to be added { x, y, width, height }
*/
public insert(pRect: RectData): void {
let indexes: number[];
//if we have subnodes, call insert on matching subnodes
// 如果我们有子节点，在匹配的子节点上调用insert
if (this.nodes.length > 0) {
indexes = this.getIndex(pRect);
for (let i = 0; i < indexes.length; i++) {
let index = indexes[i];
let node = this.nodes[index];
node.insert(pRect);
}
return;
}
//otherwise, store object here
// 否则，将对象存到本节点
this.objects.push(pRect);
//max_objects reached
// 如果当前节点的可容纳对象数达到上限并且当前可分裂数未达上限
if (this.objects.length > this.max_objects && this.level < this.max_levels) {
//split if we don't already have subnodes
// 还未分裂，进行分裂
if (this.nodes.length == 0) {
this.split();
}
//add all objects to their corresponding subnode
// 将所有对象划分到所在节点内
for (let i = 0; i < this.objects.length; i++) {
let rect = this.objects[i];
indexes = this.getIndex(rect);
for (let k = 0; k < indexes.length; k++) {
let index = indexes[k];
let node = this.nodes[index];
rect = this.objects[i];
node.insert(rect);
}
}
//clean up this node
// 有子节点的父节点不持有对象，对象全部被子节点持有
this.objects = [];
}
}
public updateQuadtree(): void {
if (this.nodes.length == 0) {
return;
}
let set = new Set();
for (const node of this.nodes) {
let objects = node.objects;
for (const object of objects) {
set.add(object);
}
}
set.forEach((object) => {
let nodeIndexes = this.getIndex(object);
let allIndex = [0, 1, 2, 3];
// 更新现在的区域
for (let i = 0; i < nodeIndexes.length; i++) {
const nodeIndex = nodeIndexes[i];
allIndex.splice(nodeIndex, 1);
let node = this.nodes[nodeIndex];
if (node.objects.indexOf(object) != -1) {
continue;
}
// 将其插入子节点
node.insert(object);
}
// 移除以前所在的区域
for (let i = 0; i < allIndex.length; i++) {
const nodeIndex = allIndex[i];
let node = this.nodes[nodeIndex];
let objectIndex = node.objects.indexOf(object);
node.objects.splice(objectIndex, 1);
}
});
for (const node of this.nodes) {
node.updateQuadtree();
}
}
/**
* Return all objects that could collide with the given object
* 返回所有可能与给定对象发生碰撞的对象
* @param Object pRect bounds of the object to be checked { x, y, width, height }
* @return Array array with all detected objects
*/
public retrieve(pRect: RectData): RectData[] {
let indexes = this.getIndex(pRect);
let returnObjects = this.objects;
//if we have subnodes, retrieve their objects
// 如果有子节点，则遍历子节点拿到所有对象
if (this.nodes.length > 0) {
for (let i = 0; i < indexes.length; i++) {
let index = indexes[i];
let node = this.nodes[index];
let objects = node.retrieve(pRect)
returnObjects = returnObjects.concat(objects);
}
}
//remove duplicates 看下来是浅拷贝，但无需indexOf
// returnObjects = returnObjects.filter((item: RectData, index: number) => {
// return returnObjects.indexOf(item) >= index;
// });
return returnObjects.concat();
}
/**
* Clear the quadtree
* 清空四叉树
*/
public clear(): void {
this.objects = [];
for (let i = 0; i < this.nodes.length; i++) {
let node = this.nodes[i];
node.clear();
}
this.nodes = [];
}
}
1赞
用法：每次使用前清空四叉树，放入所有怪物坐标，调用retrieve方法。
updateQuadtree方法未经过测试，慎用。
谢谢大佬，有好多代码，感觉可以好好的研究一番了。
该主题在最后一个回复创建后14天后自动关闭。不再允许新的回复。