一次指挥大量敌人

Question

我正在开发一个简单的2D游戏,许多敌人不断产生并追逐python + pygame中的玩家或玩家.我遇到的一个问题是,有很多人编写了这种类型的游戏已经遇到的问题是敌人会很快收敛.我已经用这个函数暂时解决了这个问题,如果它们彼此太靠近,它会将任意两个敌人随机分开.这很有效,但是关于O(n ^ 2)算法,每帧运行,在高敌时,程序开始减速.

当我的程序运行此功能时,敌人似乎形成了圆形物体,我昵称为"丛".丛似乎通常是黄道但实际上可能更复杂(不对称),因为当玩家移动时,敌人被拉向不同的方向.我喜欢这种丛的行为方式,但我想知道是否有更有效的方法来计算它.目前,丛中的每个敌人(通常> 100)首先朝着玩家的方向移动,然后被推开.如果有一种方法来计算丛生成的数字,以及它如何移动它将节省大量的计算.

我不确定如何处理这个问题.可以计算图形边界移动的位置,然后展开它以确保区域保持不变.

我的两个功能目前也被用来移动敌人:

def moveEnemy(enemy, player, speed):
    a = player.left-enemy.left
    b = player.top-enemy.top
    r = speed/math.hypot(a,b)
    return enemy.move(r*a, r*b)

def clump(enemys):
    for p in range(len(enemys)):
        for q in range(len(enemys)-p-1):
            a = enemys[p]
            b = enemys[p+q+1]
            if abs(a.left-b.left)+abs(a.top-b.top)<CLUMP:
                xChange = (random.random()-.5)*CLUMP
                yChange = ((CLUMP/2)**2-xChange**2)**.5
                enemys[p] = enemys[p].move(int(xChange+.5), int(yChange + .5))
                enemys[p+q+1] = enemys[p+q+1].move(-int(xChange+.5),-int(yChange+.5))
    return enemys

编辑:一些关于丛的外观的屏幕截图:http: //imageshack.us/photo/my-images/651/elip.png/ http://imageshack.us/photo/my-images/832/newfni.png /

http://imageshack.us/photo/my-images/836/gamewk.png/

丛似乎主要是一个刚刚拉伸的圆形物体(如日食,但可能在多个方向上拉伸),但由于长方形的敌人,它目前有直边.

Answer 1

有几种方法可以解决这个问题,具体取决于你的游戏.以下是一些改进性能的想法:

1. 允许一些重叠.
2. 在固定数量的帧之后减少距离检查.
3. 改善您的距离检查公式.如果您使用的是标准距离公式,则可以通过多种方式对其进行优化.首先,摆脱平方根.精确无关紧要,只有相对距离.
4. 每个单位都可以跟踪附近单位的列表.仅在该列表中的单位之间执行计算.每隔一段时间,通过检查所有单位来更新该列表.
5. 根据您的游戏设置方式,您可以将字段分割为多个区域或单元格等区域.单元仅针对该单元中的其他单元进行测试.

编辑:当单位接近目标时,它可能表现不正常.我建议他们不要让他们回到遥远的确切目标,他们实际上寻找一个随机的附近目标.就像偏离真正的目标一样.

我相信还有很多其他方法可以改善这一点,毕竟它还是非常开放的.我还要指出的类鸟群和植绒可能会感兴趣.