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_6
Your 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 <[EMAIL PROTECTED]> 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
