see: http://www.ode.org/ode-latest-userguide.html#sec_10_7_6Your solution might not be too inefficient if you can quickly narrow down the possible points in the array where collisions could happen. Whether you can do this depends on the 2D grid size, and the colliding object size and shape.
If the shape of the map is more or less fixed, you could also optimize this by using succeeding approximations. To do this you would have many 2D arrays, each finer grained than the last. Suppose the first Array was 1x1, and it's value is the maximum height of the entire map. If the common case is that the objects are far above the landscape, then most collision detection would take exactly one comparison to the 1st array. If an object is below the 1st array height, then you go to a 2nd, perhaps a 2x2 array, locating the point on the grid where the object resides. If it collides with that point, you go to a 4x4 grid, etc. etc. In 11 checks you would get to a 1024x1024 grid check.
That means that you can detect a collision in at worst O(log n) assuming you can quickly determine the test point in a given grid. In the best case you can detect objects that do not collide at all in O (1) time. You could tune the starting grid dimensions, the max grid dimensions and the granularity increase between arrays to get the best performance for your case. I think this could be made fast enough in pure python, but it largely depends on how many objects you need to check per frame.
How well this works will also largely depend on the shape of the bottom of the objects (or their collision geometries), If they are irregular (i.e., not spheres, cubes, etc) it becomes much more complex and I would recommend just using ODE.
hth, -Casey On Sep 17, 2007, at 3:15 PM, Ian Mallett wrote:
Wow, we're getting off topic... On 9/17/07, Lenard Lindstrom <len-l@xxxxxxxxx> wrote:Numeric did not meet the requirements for inclusion in the Python Standard Library. Numarray was written as a replacement. Though fast with large arrays it proved slower than Numeric for small arrays.That's interesting. My solution to collision detection (like on a 3D surface) is to have a 2D array, perhaps several thousand on a side, where the components represent data about the height of the landscape at that point. An object's position is rounded off to the nearest point, and the point's height is compared with the object's height. This will be implemented in one of my games. (Map Editor (by me) provides height data). I've recently been concerned that this will be painfully slow. Is there a fast way to do it, without using an outdated module? Ian