1

すべての弾丸を保存したいとします。私のゲームでは、フレームごとに新しい位置を計算するために誰かが撃っています。

プレーヤーが10人いて、全員のショットレートが1秒あたり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;

追加

リストの最後に箇条書きを追加するに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はあなたが思っていることをしないからです。

于 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 に答える