ID:154574
 
So something I've been wondering about for the future day when we get arbitrarily sized icons...how does collision detection work in that case?

How does a grid tend to work?

I assume there is still a grid, however small...

Anyway this is something I have no experience with so I've been curious.
On 4/8/01 5:31 pm Deadron wrote:
So something I've been wondering about for the future day when we get arbitrarily sized icons...how does collision detection work in that case?

How does a grid tend to work?

I assume there is still a grid, however small...

Anyway this is something I have no experience with so I've been curious.

I did something like this back in school - basically a little program with flying/bouncing/colliding balls that were supposed to represent molecules in a gas moving around.

The simple method of collision detection had no grid at all in space - time was, of course, broken up into steps, which I suppose you could say was a grid in time. Each particle had a position and velocity, both floating point, non-gridded.

Basically, at each time step, it would iterate through all the particles in the system, checking each for collision with another. Particles were assumed to be circular, so the collision test returned true if their centers were closer than the sum of their radii. If there was a collision, the program would calculate the actual time of collision (it must have happened between the previous time step and the current step) and propagate the particles to their correct new positions and velocities based on that time and the parameters of the collision (velocities, masses, angle of incidence, etc).

This was all fine and dandy, but did not scale well (algorithm enthusiasts will recognize that this is <nobr>O(n log(n))</nobr> best case). To get better performance, I introduced a grid, but not in the sense that BYOND is currently gridded, or quantized. Positions and velocities were still unquantized, but rather the entire space of the system was broken into smaller grid spaces. Thus if a particle was in a particular grid space, I only needed to check it for collisions with other particles in that same grid space. If it overlapped a boundary, particles in the neighboring grid space were also checked. I never did detailed paper analysis, but I found that a grid of about 10x10 seemed fairly optimal for a system of several hundred particles. More (smaller) grid spaces typically meant spending too much time worrying about unpopulated grids or calculating boundary conditions, while fewer approached the case above.

Having arbitrarily shaped objects certainly complicates things, although if they are assumed to be sqare (regardless of whether parts are masked off to transparency), this wouldn't be difficult. In fact, I'm pretty sure it wouldn't be too tough fully taking into account masked hollow/transparent areas. Things will certainly be different if/when that happens (and I really hope it does - I think if so, BYOND really could be the premier game development platform in the future).

So did that answer your question at all?
On 4/8/01 5:31 pm Deadron wrote:
So something I've been wondering about for the future day when we get arbitrarily sized icons...how does collision detection work in that case?

How does a grid tend to work?

I assume there is still a grid, however small...

Anyway this is something I have no experience with so I've been curious.

Well, like almost anything in programming, this can be approached in a number of different ways. How collision detection is handled depends on a large degree on how accurate you want you collisions to be.

If you only want general collisions, and are not worried about pixel accuracy, there are 2 main ways of implementing it. One way is the circle method (described by Air Mapster), and the other is the bounding box method. The bounding box method invloves creating a rectangle whose bounds are the minimum that would be required to surround the object in question. Once all objects have these boxes, you simply iterate through them to see if their bounds intersect the bounding boxes of any other objects. An intersection (or containment) indicates a collision. And, just like with the circle method, you can place a grid on the screen (or world space) to optimize the checks.

If you want fairly accurate collisions, but still don't need 100% pixel-accuracy, you can rely on bounding polygons for the objects. Basically, this method would be more difficult to set up than any other method. With this method, you create a polygon that closely bounds the object (but it doesn't need to be a perfect outline, just a general outline). Then, you check for intersections and containment, like in the bounding box method. It is about as fast as the bounding box method, but more accurate. But, the polygons either need to be defined by the programmer/content artist, or by a hand-made algorithm (ouch!).

Pixel-accurate collisions are possible to do, and in many ways are easier to implement than bounding polygons. For the pixel accurate method, you either use an array of booleans, or use an array of large integers (like a long in C/C++) to represent individual pixels in the image. Basically, you make a data object with a width and height and an array of booleans or larger integers. For every pixel in the source image, you check to see if it is transparent or not. If not, you set the corresponding bit in the array to 1. once you have iterated through the image, you have a 1-bit representation of your image. You could in fact, pre-process all of this and make it part of your content. Once you have these 1-bit images, you can perform a boolean AND operation. If the resulting array is non-zero, you have a collision. In most compiled (and some interpreted) languages, this is extremely fast. There are numerous optimizations you can make to this to speed this up further, but this is a good beginning point. One of the easiest optimizations is to implement a two-pass collision system. First, use bounding boxes/circles and then ONLY do the bitwise comparison on objects that collided under the first pass.

I hope that this gives you a few ideas on how it can be implemented...

Mr. Sanity
In response to Mr. Sanity
On 4/9/01 10:37 am Mr. Sanity wrote:
I hope that this gives you a few ideas on how it can be implemented...

Thanks both to Sanity and Mapster...it gives me the basic picture.

It's effectively the same as the situation now for the designer, in which for each 32x32 we assume that the entire space is covered by the icon.

The difference internally I guess is that the drawing is based on a much more granular coordinate system.

One thing possibly LESS flexible about such a system than our current situation is this: For multi-tile mobs, I determine manually whether a tile the icon spills into is considered to be dense or not. For example, in DragonSnot the cave icons spill over 32x32 (or 32x64...I forget) by just a few pixels. So I treat those spillover tiles as non-dense.

Well I guess I could get the same effect by using the bounding rectangle approach and having such foofery lie outside the collision rectangle.

Ultimately it sounds like BYOND might want to support more than one way to determine collision...