Archived

This topic is now archived and is closed to further replies.

webmunkey

Help! Collison detection!

Recommended Posts

webmunkey    122
Hey, I have a massive xpos and ypos array in my program and I want to test to see if an xpos and a ypos equal a previous entry in the array. The only thing I can think of is a very large for loop, but this array is massive and I think a for loop would slow down the program. Does anyone have any ideas on what I can do different? Please help! Thanks...

Share this post


Link to post
Share on other sites
monkeyman    253
That''s rough

The best suggestion I can offer is this:

Create some 2d grid of imaginary tiles that covers the entire area in which these xpos/ypos values might be..if you already have this in place you''re halfway there..

For each cell in the grid, create a list of xpos/ypos values that reside within that cell...when you check for duplicate values, only check the ones that reside in the same cell..

if your xpos/ypos values are subject to change, do this:

If the xpos/ypos value is still within the bounds of it''s current cell, do nothing..

if the xpos/ypos value is now within another cell:

remove it from the list of the last cell..
add it to the list of the new cell..

The higher the grid resolution, the less data you have to check, but there''s some extra code and overhead involved, so it might not be the best solution for what you''re doing..



"Like all good things, it starts with a monkey.."

Share this post


Link to post
Share on other sites
Ksero    262
One way to do this could be to scrap the array entirely and have a sorted list (A linked list? A deque?) of those positions instead. Sort by the coordinate with the most possible values (is that a good way of saying that? What I mean is: If you're doing a side-scrolling shoot'em up, your levels will be more wide than high, so sort for X). Then when you check for overlap, for every point you just check & compare it with the next points in the list until you get to a point with a different X coordinate.

When the point moves to a different X, you need to move it in the list to the right position. As long as you do that right, there is never need for actually sorting the array (which takes time). It keeps itself sorted.

*hopes that makes sense* You could try different approaches and see what works best for you!
//Ksero

[EDIT]: fixed paragraph formatting

Edited by - Ksero on August 2, 2001 3:33:23 AM

Share this post


Link to post
Share on other sites
webmunkey    122
Thanks for replying guys! I solved the problem by sectioning off the level and just check to see if something changed in that section and check for collison with all entities in that section so it doesn''t have to run through a massive for loop. Works like a charm except I get some weird errors sometimes when crossing quadrants...oh well, thanks a bunch!
Later,
-Jesse

Share this post


Link to post
Share on other sites