javascript - Canvas 游戏 - 存储/计算位置/迭代粒子/子弹/游戏元素的最有效方法

Question

假设我想存储所有子弹，任何人在我的游戏中射击以计算每帧的新位置等。

如果有 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% 都是空的。

Answer 1

我相信您想要实现一个链表而不是使用 JavaScript 数组。

关于 JS 数组的真相

首先，你可能对数组有一个误解。当我们想到 JavaScript 数组时，我们实际上讨论的是 HashMap ，其中的键恰好是整数。这就是数组可以有非数字索引的原因:

L = [];
L[1] = 4
L["spam"] = 2;

数组的迭代速度很快(至少在 C/C++ 意义上)，但通过 HashMap 的迭代则相当差。

在您的情况下，某些浏览器可能会将您的数组实现为真正的数组，如果 certain constraints都满足了。但我相当确定您也不想要真正的数组。

数组性能

即使是真正的数组也不是特别适合您想要做的事情(正如您所指出的，即使您删除项目符号，您的数组也会不断填充 undefined 元素!)

想象一下，如果您确实想从真实数组中删除项目符号并删除 undefined elements:我能想到的最有效的算法是在完整扫描子弹后创建一个新数组，将所有尚未删除的子弹复制到这个新数组中。这很好，但我们可以做得更好。

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;

正在追加

要将项目符号添加到列表末尾，您需要设置 next旧的引用last_bullet ，然后移动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 doesn't do what you think it does.