链表中的随机性

Question

我们能在链表中获得随机性吗？我正在实现太空射击游戏，在游戏中，敌人应该随机发射子弹。我将敌人存储在链表中，我想随机选择一些敌人并从他们中射击。如何使用链表执行此操作？

Answer 1

如果你确切地知道你的列表中有多少个项目，以及你希望每一帧拍摄多少个项目，实际上有一个相对简单的方法:对于每个项目，如果N个项目列表中有k个项目，而总Q个项目中有p个项目要拍摄，那么当前项目应该以概率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个值中的一个。虽然这个算法看起来应该以不同的概率选择不同的物品(毕竟，每个物品的随机数检查都是不同的！)，但它可以从数学上表明，这不仅选择了具有正确概率的每个单独的射手，而且每组射手的概率实际上是相等的。

Answer 2

在我看来，随机化一个数字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个，只是为了选择一个来触发。

Answer 3

你可以从第一个节点开始，然后调用n个“next”。

伪代码：

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

也许你可以添加第二个容器，比如数组/数组列表/向量，然后在there...You中管理它。你可以问你的教授他/她是否同意。