1

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

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

4

2 回答 2

1

我相信你想实现一个链表而不是使用 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;

追加

要将项目符号添加到列表的末尾，您需要设置nextold 的引用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没有做你认为它做的事情。

于 2013-02-09T02:02:55.567 回答
0

这是我删除集合中的子弹或任何对象的方法。从来没有发现它是游戏的瓶颈——它总是渲染。

游戏

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--;
    }
  }
}
于 2013-02-09T09:48:34.403 回答