假设我想存储所有的子弹,任何人都在我的游戏中射击,以计算每帧的新位置等。
如果有10个玩家,每个人的射击速度是每秒10次,我们可能需要在10秒后跟踪1000个物体。
我们知道,对数组的迭代是非常有效的。
我应该像这样添加新项目符号吗?
// "bullets" is an array
bullets.push({
x_position: 5, // x position from which bullet was shot
y_position: 10, // same as above but for y
x_speed: 2, // count of pixels that bullet is travelling on x axis per frame
y_speed: 10 // as above but for y
});
我应该取出子弹,击中绑定,还是像这样的其他玩家?
delete bullets[i] // i -> currently processed bullet index
因为如果我试图从子弹头数组中取出元素,那么长数组的效率不是很高。
老实说,我并没有更好的想法来解决子弹的问题。几分钟后迭代这种数组可能会很痛苦,因为如果我们删除旧项目符号,数组长度就会保持不变,最终迭代的记录会超过数百万条,其中99%都是空的。
我相信您希望实现一个链表,而不是使用JavaScript数组。
JS数组的真相
首先,您可能对数组有误解。当我们想到JavaScript数组时,我们实际上是在谈论散列映射,其中的键恰好是整数。这就是数组可以具有非数字索引的原因:
L = [];
L[1] = 4
L["spam"] = 2;
数组的迭代速度很快(至少在C/C++意义上),但通过哈希图的迭代相当差。
在您的情况下,如果满足某些约束,某些浏览器可能会将您的数组实现为真正的数组。但我敢肯定你也不想要真正的数组。
阵列性能
即使是一个真正的数组也不是特别适合你想要做的事情(正如你所指出的,即使你删除了项目符号,你的数组也会不断充满undefined
元素!)
想象一下,如果你真的想从一个真实的数组中删除项目符号并删除undefined
元素:我能想到的最有效的算法是在项目符号完全扫描后创建一个新数组,将所有尚未删除的项目符号复制到这个新数组中。这很好,但我们可以做得更好。
JavaScript中的链表
基于你的问题,我认为你想要以下内容:
- 快速创建
- 快速迭代
- 快速删除
一个提供恒定时间创建、迭代和删除的简单数据结构是一个链表。(也就是说,链表不允许你快速获得随机项目符号。如果这对你来说很重要,请使用树!)
那么,如何实现链表呢?我最喜欢的方法是给每个对象一个next
引用,这样每个项目符号都指向或"链接"到列表中的下一个项目符号。
正在初始化
以下是如何启动链接列表:
first_bullet = {
x_position: 5,
y_position: 10,
x_speed: 2,
y_speed: 10,
next_bullet: undefined, // There are no other bullets in the list yet!
};
// If there's only one bullet, the last bullet is also the first bullet.
last_bullet = first_bullet;
追加
要在列表末尾添加项目符号,您需要设置旧last_bullet
的next
引用,然后移动last_bullet
:
new_bullet = {
x_position: 42,
y_position: 84,
x_speed: 1,
y_speed: 3,
next_bullet: undefined, // We're going to be last in the list
};
// Now the last bullet needs to point to the new bullet
last_bullet.next_bullet = new_bullet;
// And our new bullet becomes the end of the list
last_bullet = new_bullet;
迭代
要在链接列表中迭代:
for (b = first_bullet; b; b = b.next_bullet) {
// Do whatever with the bullet b
// We want to keep track of the last bullet we saw...
// you'll see why when you have to delete a bullet
old = b;
}
正在删除
现在删除。这里,b
表示要删除的项目符号,old
表示链表中它前面的项目符号——所以old.next_bullet
相当于b
。
function delete_bullet(old, b) {
// Maybe we're deleting the first bullet
if (b === first_bullet) {
first_bullet = b.next_bullet;
}
// Maybe we're deleting the last one
if (b === last_bullet) {
last_bullet = old;
}
// Now bypass b in the linked list
old.next_bullet = b.next_bullet;
};
请注意,我没有使用delete b
删除项目符号。这是因为delete
不会做你认为它会做的事情。
以下是我删除项目符号或集合中任何对象的方法。从来没有发现它是游戏的瓶颈——它总是渲染。
游戏
game = {
dirty: false,
entities: [ ],
clean: function() {
this.dirty = false;
clean(this.entities, "_remove");
},
step: function() {
if(this.dirty) this.clean();
}
}
项目符号
Bullet = function() {
this._remove = false;
}
Bullet.prototype = {
kill: function() {
this.game.dirty = true;
this._remove = true;
}
}
清洁功能
function clean(array, property) {
var lastArgument = arguments[arguments.length - 1];
var isLastArgumentFunction = typeof lastArgument === "function";
for(var i = 0, len = array.length; i < len; i++) {
if(array[i] === null || (property && array[i][property])) {
if(isLastArgumentFunction) {
lastArgument(array[i]);
}
array.splice(i--, 1);
len--;
}
}
}