0

我们可以在链表中获得随机性吗？我正在实施太空射击游戏，其中敌人应该随机射击子弹。我将敌人存储在链表中，我想随机选择一些敌人并从中射击。我怎样才能用链表做到这一点？

4

4 回答 4

4

以我的拙见，随机化一个数字 N 然后让 N 号船射击并不是解决这个问题的正确方法。首先，这意味着一艘船会在每一帧或每一轮射击，这不一定是你想要的。

问题在于，无论屏幕上有多少敌人，射击的数量都是一样的。天气你有 1 个或 100 个敌人，所有敌人加起来的射速将恰好是每回合/帧一发，这在游戏设计方面毫无意义。这也意味着一艘船有时可能不会在 2xN 回合内开火（这有点像旧的武侠电影，坏人排队等候与“英雄”战斗，从不同时攻击）。

在我看来，好的方法是迭代船只并让每艘船以一定的概率开火，最好是根据上次开火的时间。

long now = getCurrentTime... /*replace with real function*/
double epsilon = 0.0001; /*adjust as needed*/
while(current = enemyList.next()){
    if(Math.random() < epsilon * (now - current.lastFired))
    {
        current.fire();
        current.lastFired = now;
    }
}

如果你不利用这个机会，迭代 N 个元素几乎没有任何意义。如果您使用列表，则意味着您计划遍历所有敌人并更新每个敌人。再次迭代其中的 N 个是没有意义的，只是为了选择一个来触发。

于 2012-11-19T05:02:57.320 回答
3

您可以从第一个节点开始并调用 n 数量的“下一个”。

伪代码：

int num = Math.random() * myLinkedList.Count;
for( num ){
     myLinkedList.next();
}
return myLinkedList.currentNode;

也许您可以添加第二个容器，例如数组/数组列表/向量并从那里管理它……您可以随时询问您的教授是否可以接受他/她。

于 2012-11-19T02:09:56.593 回答
2

如果您准确地知道列表中有多少项，以及您希望每帧拍摄多少项，实际上有一种相对简单的方法：对于每个项，如果N的列表中有k项，和p项目离开总共Q射击，那么当前项目应该以概率p/k射击- 然后应该更新k和p的值。其伪代码如下所示：

myThing curThing = myList->head;
int objectsLeft = myListCount;
int shootersLeft = numShootersPerTick;
while ( curThing )
{
  if ( random(objectsLeft) < shootersLeft )
  {
    curThing->Shoot();
    shootersLeft--;
  }
  objectsLeft--;
  curThing = curThing->next;
}

请注意，我假设 random(N) 返回一个介于 0 和 N-1 之间的数字；即，N 件事之一。虽然这个算法似乎应该选择具有不同概率的不同项目（毕竟，每个项目的随机数检查都在变化！），但可以从数学上证明，这不仅以正确的概率选择每个单独的射手，每个一组射手实际上同样可能。

于 2012-11-19T02:26:56.063 回答
0

假设您想从列表中选择k个随机元素（N是总数）。选择的这k 个元素应该是完全随机的。方法如下：

  1. 首先取前k个元素。

  2. 通过列表前进；当出现第m 个元素时，生成一个随机整数0<=r<m。

    • 如果r<k，则丢弃一个随机的先前选择的元素并将其替换为第m 个元素。

带有概率和归纳论证的一点算术表明这给了所有元素平等的机会。

于 2013-12-18T09:05:06.743 回答