Python-有效检查列表中的每个项目与其他所有项目 [英] Python - Checking every item in a list against every other item efficiently

问题描述

我正在开发一个游戏，其中每个对象都应检查它是否与任何其他对象发生碰撞.我有一个所有对象的清单，还有一个可以确定两个对象是否碰撞并将其销毁的函数.我当前使用的方法效率很低.

for i in list1:
    for j in list1:
        if collide(i, j):
            i.kill()
            j.kill()

最初，两个对象被杀死后，我将它们从列表中删除，但是发生了一些碰撞，但没有检测到，因此我恢复了此代码.它可以工作，但是我想要更有效的方法.

解决方案

首先，这要测试两次，并且还要测试一个对象是否与自身碰撞:

for i in list1:
    for j in list1:
        if collide(i, j):
            i.kill()
            j.kill()

这恰好循环了len(list1)**2次.

一种非常简单的方法将测试次数除以2(并避免针对自身进行测试):

for i,obj1 in enumerate(list1):
   for j in range(i+1,len(list1)):
      obj2 = list1[j]
      if collide(obj1,obj2):
         obj1.kill()
         obj2.kill()

利用了collide(obj1,obj2)与collide(obj2,obj1)相同的事实.

在这一点上，由于obj1现在已死，您可能想break退出内部循环.但这取决于您想做什么.

如果准确的碰撞测试价格昂贵，则可以考虑进行更粗略的检查(距离，矩形边界，任何快速方法)，因此可以丢弃彼此相距太远的项目而无需执行昂贵"的测试. /p>

I'm working on a game where each object should check if it is colliding with any other object. I have a single list of all the objects and a function which can determine if two objects are colliding and destroys them. The current method I'm using is very inefficient.

for i in list1:
    for j in list1:
        if collide(i, j):
            i.kill()
            j.kill()

Initially I removed both objects from the list after they were killed, but some collision occurred without detecting so I reverted back to this code. It works, but I'd like something more efficient.

解决方案

first this is testing twice too much and also testing if one object collides with itself:

for i in list1:
    for j in list1:
        if collide(i, j):
            i.kill()
            j.kill()

This loops exactly len(list1)**2 times.

a very simple way to divide the number of tests by 2 (and avoiding testing against itself):

for i,obj1 in enumerate(list1):
   for j in range(i+1,len(list1)):
      obj2 = list1[j]
      if collide(obj1,obj2):
         obj1.kill()
         obj2.kill()

It takes advantage of the fact that collide(obj1,obj2) is the same as collide(obj2,obj1).

At this point, you probably want to break out the inner loop since obj1 is now dead. But that depends on what you want to do.

If an accurate collision test is expensive, you could consider a rougher check (distance, rectangle boundary, any quick method), so you can discard items which are too far away from each other without performing the "expensive" test.

这篇关于Python-有效检查列表中的每个项目与其他所有项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！