Sorry, that would be: if landscape[x][y][int(round(log(size + 1, 2)))] >= z: ..it collides... where size is the collision diameter of the object. -Casey On Sep 17, 2007, at 4:38 PM, Casey Duncan wrote:
Here's an alternate similar thought. Again assuming the collision geometries of the object potentially contacting the landscape are simple, you could turn your 2D array into a 3D array where the 3rd dimension is the log base 2 of the other dimensions.Each value in the array is the maximum height of the landscape at the 2 dimensional position averaged over a size of 2**z (z being the third dimension).let's take a 1000x1000x10 array as an example:a[100][100][0] is the average height of the landscape centered at 100, 100 for an object of size 1 (using arbitrary size units).a[100][100][1] is the average for an area of size 2, a[100][100][6] is the average at that point for size 64, etc.Let's say you have an object of size 60 at location x,y,z on the grid. To see if it collides you do:if landscape[x][y][int(round(log(z + 1, 2)))] >= z: ..it collides...This makes every collision check O(1). though it becomes increasingly inaccurate for large objects. If you want to make it more accurate, you could make z increase more slowly using a lower base and/or by performing a more expensive check inside the if statement, assuming collisions are not the common case.-Casey On Sep 17, 2007, at 4:04 PM, Casey Duncan wrote:ODE has a trimesh object, which can be used to represent arbitrary 3D surfaces for collision detection. Use pyODE to interface to it from python.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: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 landscapeNumeric did not meet the requirements for inclusion in the PythonStandard Library. Numarray was written as a replacement. Though fastwith large arrays it proved slower than Numeric for small arrays.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 bepainfully slow. Is there a fast way to do it, without using an outdated module? Ian