Archived

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

Red Drake

A "new" way for Collision detection

Recommended Posts

I woud like to ask you if any one has heard of such a way for Collision detection. If not I think i will write an article about it. Well hear it goes: Before a game level starts we build a 2D matrix that fits the size of the terain loked from above. This does not mean that the map shoud be square/rect - it only means that if map is not rect the matrix space out of the borders of map will bee lost/unused. The matrix type shoud be : - n of pointers to Game CHARACTERS (runtime alocated) - m of pointers to Game static OBJECTS (runtime alocated) The matrix shoud hawe the folowing elements : - It''s elements are a square of n*n size ( example: 1 meter * 1 meter ) this means that it is like a box in 3D space - The number of elements of matrix is = (terain size X / metrtic unit) * (terain size Y / metric unit) The basic pricipal of engine is that first at the begining of level you aproximate the max number of objects(n) & characters(m) inside one square ("box") Then if you want to check for Collision of a character you yust check the pointers in matrix cordinates around the character and if you want to render a view distance you yust render the pointers around the character (in the direction of looking). Now if you are still folowing me you are a bether reader then I am a righter. If you think that my explanation is bad or speling is bad too you hawe to ralize that i am only 15 and i hawe about 5 months of expirience in game developing. ( Remeber that i am only 15 and i envented that by my self if it''s not invented before) So do you hawe Quastions, Coments ...

Share this post


Link to post
Share on other sites
google octress. it''s like what you described except it doesn''t take up so much memory and there are hundreds of resources out there about them (or any other kind of tree for that matter).

don''t worry, everyone has invented someone elses algorithm at some point in their life .

Share this post


Link to post
Share on other sites
Don''t feel bad -- when I made my first game and I came up with an FSM on my own... I felt so proud! Then I looked it up on the Internet and found thousands of articles on FSMs and felt really stupid...

Share this post


Link to post
Share on other sites
I yust realized that octrees are not wath i ment
(I think)

You see the point of taht matrix of pointers is a cordination of an object etc.
I hawe an object that is at X= 22.7m and Y= 20.2m

so in my matrix it woud lok like this
Matrix [22][20]

and i try to see witch objects coalide i yust check the pointer of objects in

Matrix [22][20]
Matrix [22][21]
Matrix [23][21]
Matrix [22][20]
Matrix [23][20]
Matrix [21][20]
Matrix [22][19]
Matrix [23][19]
Matrix [22][19]

etc. objects around the my object

I don''t understand octree corectly but pictures i hawe seen ilustrating it is definitly not what i meant (from gametutorials)

the point of matrix is losing calculations - you yust convert an float to int and adresit in matrix and you know about an metar acurate how far is some object from you.
(so no comparing is needed & no if''s)

Maybe i am wrong but hey i am trying to make my self feal bether.

Share this post


Link to post
Share on other sites
Can somody please respond - tell me if these are octrees or not and if this is an efective way please i hawe ben waiting fo a response for 1 h (I want to know)

Share this post


Link to post
Share on other sites
It is very similar. The idea behind octrees ( or quadtrees in 2d) is that most of the data in that matrix will be NULL. The octree takes advantage of this by keeping track of large blocks of your 1m x 1m squares that are empty. In this way, large empty spaces take very little memory unlike your algorithm which takes just the same as where there are lots of objects. You do add some complexity by doing it this way because you just traverse the tree instead of doing an index into an array, however you would have to do some tests to see which is really that much faster. You might be able to fit your octree into cache page in which case multipule retrieves won''t be as bad as one retrieve out of the page (which might happen frequently if you allocate as much space as you are considering). Basically, they both work, but octrees have the advantage of much more accuracy per memory and if built right might also induce less cahce misses.

Hope this clears it up some...

Dwiel

Go see some hot chicks and vote to see who is hottest: dwiel.no-ip.com

Share this post


Link to post
Share on other sites
No, what you''ve got is not an octree (or any kind of tree). You''ve got a hashing system (the hashing function being: index = (x / a) + (y / b) * w), which will work reasonably well in most cases. Problems will occur when all your entities hash to the same index (i.e. they all get close together), in which case you''ve degenerated to an O (n*n) search. An octree (or quadtree for 2D) can get around this problem by dynamically subdividing the leaves when the number of entities in it exceed a predefined threshold.

Trees are more complex and can use up more memory than the straightforward method you suggested, but they can be designed not to degenerate when objects get close together.

Skizz

Share this post


Link to post
Share on other sites
While you are able to calculate collisions in O(1), there are many advantages to oct/quadtrees, which work on a similar system.

The most important advantage is that they save space. If a node isn''t needed, it isn''t created, unlike with your grid.

The next huge advantage, however, is culling. While you effectively cull objects for collision detection (by saying "don''t even look at other objects except these"), when it comes to frustum culling, testing nodes against the camera frustum becomes very easy. If a parent node is then rejected, all of its children are rejected, and so you can quickly throw out objects that aren''t visible or part of a collision.

The next advantage is that they can be scaled at runtime. With your grid, you need to specify how you''re "hashing" a position into the grid... for example by cutting off the decimals. But what if all of your objects are less than a meter apart? An octree will keep subdividing until a specific number of triangles is reached, whereas your structure will lump them into one node and leave a huge grid of them blank.

Essentially, you came up with a really good start. Octrees and quadtrees take the same concept and, with a small performance hit, greatly increase memory usage, culling efficiency and scalability. As someone said above, we all invent other people''s algorithms, but your thinking is definitely on the right track, and your solution to collision culling is certainly in the right mindset... a more optimized data structure does exist, however.

Share this post


Link to post
Share on other sites
Wel i am actualy starting to understand the octrees but I still tink tht the matrice is faster for aproximitation. And about the memory wel lets say that a game(fps) is using a map size 25x25 meters and it has 8 players.
so you bild up a 25*25 matrice with type

struct MatSquare
{
Character *Chars;
int nChars
Objects *Obj;
int nObjects;
int ObjAloc; //Count of memory alocated
}

MatSquare Matrice [25][25]

so let asume that our objects in the game dont move much so per each map square you alocate num of objects

nObjects = hear you woud hawe to calculate the n of objects on your map on this square
Matrice.Obj = new Objects[nObjects+1];

In this example n+1 is number of objects in this map on this square so if some object moves we will hawe enough memory to store it :
nObjects++;
if (nObjects >= ObjAloc)
{
// Hear we woud bil a temporery memory to delit the square then alocate more memory for objects and then copy the data back (prety time consuming)
}

as for player count we coud allocate nPlayers - nPlayers/2 (if not only 2 players) and then use the uper memory alocation handler to resize an array .
Or if the user hawes lots of memory then we coud alocate nPlayers at all squares
After all who does not own 256 MB of RAM these days and sine we are wrking with pointers it coud not take much.

As for culling you can calculate the direction of camera and then render only the pointers that ar relativly close to the direction of viewing vector (it is why I started to think about this in the first place)

So do you tink that i coud post an articel about this or you think it is yust a peace of crap not worth mentioning.

Share this post


Link to post
Share on other sites
It certainly isn''t "a piece of crap," but octrees are really more practical for 3D applications. 2D applications that have limited sizes (i.e. without scrolling) could use it, however. The problem with your system isn''t that approximations aren''t faster than with a tree, it''s that it can''t resolve the problems I put in my last post.

Again, your approximation is O(1), or constant time... that is a very good thing. But, it really cannot be implemented in a 3D game due to the problems I mentioned.

Share this post


Link to post
Share on other sites
Not true (at least not at all of it)

You mis understud my idea (completly)

1.) It is not used for Collision detection alone
it yust culls out the uneded detection betwen two objects that are to far away widouth "if" comands (using pointers) and when you cull out the unnedded objects you get the objects that shoud be checked with box, sphere ... or another coalision detection algoritam

2.) You can scale it during runtime - all you need to do is incrise/decrease the metric unit used for dividing the space


3.) And for culling of render

OOOOOOOOOOO
OOOOOOOUUUU
OOOOX->UUUU
OOOOOOOUUUU
OOOOOOOOOOO

the X in the uper matrix is the player camera and the arow
("->") is the direction of viewing so if you render the "U" signs by the pointer you don''t even need to check all if the other "0" are in player view - so you cut back on position comparing (no "if''s") becouse they are all aranged in the matrix (it is why i built it in the first place)

4.) I hawe wrote somthing that you cuod call engine and coallision and culling is not the problem in it

So the only problem lies in the memoy and I hawe yust got an idea how to reduce its size.

so you hawe a square struct

struct MatSquare
{
Character *Chars;
int nChars
Objects *Obj;
int nObjects;
int ObjAloc; //Count of memory alocated
}

but it is not wery good for moving static models (objects)

so you separate the moving objects from non moving

struct MatSquare
{
Character *Chars;
int nChars

Objects *NM_Obj;
int NM_nObjects;
int NM_ObjAloc; //Count of memory alocated

Objects M_*Obj;
int M_nObjects;
int M_ObjAloc; //Count of memory alocated
}

the NM_ prefix is for non moving and the M_ is for moving so if you want to so you can hawe exact num of non moving objects and for moveing you do the folowing
You check the near cordinates for moving objects and alocate the number of moving objects in this square + suraunding squares /2 becouse it is higly unlikely that they wil all be moved in the one square and if this does hapen you keep the old allocation cheking code

M_nObjects++;
if (M_nObjects >= M_ObjAloc)
{
// Hear we woud bil a temporery memory to delit the square then alocate more memory for objects and then copy the data back (prety time consuming)
}

so the ting you did with chapter 4 is avoid this function unles apsolutly nesesary.

P.S.
I am about to write an article becouse most of you people did not understand what i ment to say.

But if you think that the article is a waste of time write in and explain so i might save time (i go to school you know )

Share this post


Link to post
Share on other sites
The problem is I don''t know other ways of this if I knew i woud not think of a new way to do this.
So in a couple of weeks you will get a source with an article becouse my summer vication is only 1 month away and wright now I am so dedicatet to game developing so much that my grades in school are so low that I yust might hawe to go on extended summer class (hopfuly it won''t come to that).
Theoreticly the my idea shoud work faster becouse it eliminates all unneeded data widouth any if arguments ("Matrix culling").
"Matrix culling" - it is what i am about to call it
is faster (probably) buth somwer inacurate and memory consuming. So if you prefer speed over memory consumation the "Matrix culling" is a choice that you might consider.

Please don''t stop sending any questions & ideas to this forum if you hawe som bceouse i hawe put only basic teory about this , and the practical use is still far away.

If you want to contact me
marino.munitic@public.carnet.hr

Rafael Munitic - The Red Drake

Share this post


Link to post
Share on other sites
I''m not sure if you understand all the considerations that sirSolarius has brought forward. What happens if more entities are positioned inside the same box? What if an entity occupies two boxes?

Or are you saying that each box is dynamically created to encompass groups of entities? In that case, you could take a look at Recursive Dimensional Clustering (Game Programming Gems 2).

Sorry that most of us here are skeptical, but there aren''t very many new things under the sun. Not that we should give up altogether but, it seems that you''re crying wolf since you haven''t put your theory to the test.

It could be that countless others have done the exact same thing with deplorable results. Hopefully that''s not the case =p DO work out your theory and then we''ll see.

Share this post


Link to post
Share on other sites
What red drake is talking about is a simple 2d grid that is typically sized to contain only one game object. Such games this could be used for are isometric RPG games. It is quite easy to determine the cells included in the view frustrum and the fact that each grid is of a set size it is easy to test the neighbours for collision/action etc, and its is also easy to move game objects into differrent cells without having to alter a quad tree. As long as the dimensions (ie number of cells) of the grid is set at a small managable amount then it is quite a good system to use.

And sorry red drake, this system was and is being used quite extensively. It was the precursor to quadtrees after all

Share this post


Link to post
Share on other sites
I''ve tried this system before - its not even slightly as good as a proper oct or quad tree. The main problem being that you don''t take into account the sizes of the objects. Any object spanning a cell boundary gets ignored by others in adjacent cells even though they actually intersect.

If you manually try and compensate then you end up checking adjacent cells. But then it breaks down when you get objects bigger than a cell in size, and don''t even think about detecting collisions between two large objects.

Generalising it by taking into account object sizes ends you up reinventing a quad tree.

Share this post


Link to post
Share on other sites
I implemented a similar collision detection system about 10 years ago. The big difference between what you're thinking of doing and what I did was that my bins were spherical shells rather than boxes. I calculated the distance of each object from an arbitrary point (the arbritrary point might aswell be the camera position) and placed each object in a shell bin according to the distance. Only objects that were in the same bin or in the 2 adjacent bins were checked for collision. Large objects that spanned more than one shell were placed in all the bins they spanned.

It was for a space game with lots of rocks flying around, since the rocks were fairly evenly spaced the system worked very well.

I hadnt even heard of octree/quadtrees back then so I cant make any performance comparisons.

The advantage of using shells is that you only need a 1 dimensional array so the memory usage is less. The disdavantage being that potentially objects a long way away could be in the same shell. This isn't really a big issue though since you're still culling a lot of objects that cant be in collision, very efficiently.

[edited by - AdrianL on May 20, 2004 1:16:00 PM]

Share this post


Link to post
Share on other sites
Sory if I did not anwser a questions in past couple of houers - i was in school.

Lets go for anwsers:

1.) I realized i caled this topic the wrong way - it shoud be caled Collision CULLING
Why ?
Becouse it does not check for coalision it yust eliminates the objets that are too far away widouth any IF comands so you detirmine the objets that are best candidates for Collision

2.) SoulSpectre your thinking is so limited .
How can you put 3D space in 2D map - BLUEPRINT (i don't know if i writed that down corectly ) you watch your map from above (imaginary) and flaten the terain so you actualy ditch the height cordinate . This is not wery efective but the theory stil speeds up things (theoreticaly) and it is dedfinetly not the stuf you said (about one object in one square) it can store multiple objects in one cel - Read the cel structure in uper post - it contains a pointer to an struc object so you ccan dinamicly alocate the memory neded for objects in that cell.

P.S. So you se I did think of somthing that goes beyond the limits of 2D

3.)AdrianL you totaly mised the point of the matrtix - it main purpose is the 2D positioning of object in array i dont see how can you use spherical objects but i use SQUARES - 2D not 3D ( again read 1. ). Then you probably did not do the same thing as I do.

4.) OrangyTang - not true.
Lets say that i hawe an object thet goes in to one Square/Cell end ends 3 cels away . Why can't i put a pointer to this object in all the cell that the object pases ??? The trought is that i can and it is exactly what i said in the previus posts

5.) Darkor - See nunmber 1.) at this post THIS IS NOT COLLISION DETECTION it is CULLING WIDOUTH IF COMANDS WITCH BUSTS PREFORMANCE

Men this debating has been so entartainig that i am starting to have fun

So any more Questions
But please read the all posts before you ask and try to understand what i am saying to you ! Then ask becouse i hate repeating things


[edited by - Red Drake on May 20, 2004 1:55:23 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Red Drake
Why can''t i put a pointer to this object in all the cell that the object pases ??? The trought is that i can and it is exactly what i said in the previus posts


You could do that (and I''ve tried it), but it makes maintaining the entire structure a nightmare. You''ll end up doing so many pointer removals and re-insertions that you''ll kill your performance. One of the main advantages of a quad or oct tree is that objects are stored once *and only once* which makes rearranging a snap.

Plus it means that you''ve now got many more pointers stored in your structure, vastly increasing the memory used. And intersection testing now has to maintain lists of objects checked against - when an object is found it needs to scan the entire list to check if its already been found, and then insert into this intersection list if not.

Share this post


Link to post
Share on other sites
By OrangyTang :
"Plus it means that you''ve now got many more pointers stored in your structure, vastly increasing the memory used. And intersection testing now has to maintain lists of objects checked against - when an object is found it needs to scan the entire list to check if its already been found, and then insert into this intersection list if not."
(I dont qnow how to use quote)

Not true.

You can create a two lists of objetc''s that are checked for coalision :
1. The first list shoud be the objects that are in only one Square
2. The second is for objects with more than one square size

so you only need to check 2. list and bost preformance and as for checking the list it is stil a lot faster then checking the cordinates of another object

Men I yust figured that up!

Second : About the pointer removals WHY IS THAT ?? Can you explain!
Are you are tinking about the destroying the object??
If you are - a simple solution - you yust add a bool value to the object and call it "ObjVisebal" - so at the begining of your coallision test you put
if (ObjVisebal== TRUE)
{
// Check for coalision
}

Share this post


Link to post
Share on other sites
It is good for rpg/strategy games, where the terrain is grid based and the usual objects occupy a single cell, games like turn based hex strategy games and the old turnbased rpg games spring to mind. However for a world where the objects are of various size and the movement isn''t grid based then a oc/quad tree would be better.

Share this post


Link to post
Share on other sites
quote:
Original post by Red Drake
You can create a two lists of objetc''s that are checked for coalision :
1. The first list shoud be the objects that are in only one Square
2. The second is for objects with more than one square size

so you only need to check 2. list

That would help somewhat, but its still inefficiant compared with a quad tree. Also, that means adding special case code all over the place, which will make the whole code much less elagent.

quote:
Second : About the pointer removals WHY IS THAT ?? Can you explain!

Because when an object moves you''ve got to regenerate all the pointers in the array. That involves finding which cells the object previously occupied (about as much work as a regular quad tree bounds check) then finding which cells it now occupies. Then you''ve got to go though all the ones that have changed and remove it from the lists, and add it to the cells it newly occupies.

Compare with quad tree: check bounds. If needed, remove from (single!) parent and add to new parent.

Share this post


Link to post
Share on other sites
To : SoulSpectre

NO!
Read up.
First you position your objct in 2D matrix.
Then you check all the cels/squares around the object (including the one with you in it of course)
Then you check if the the most lower vertex (the tird aixs) on your object is lower than your player object top and higher than higer than players botom.
Then you check the most higer vertex as above and you get about and if any of this conditions are true you chek for Collision.
FOUR NUMBERS COMPARING witch isn''t that much i think if you can cut out an entire Collision test.

I did think of this before but you hawe to realize that i hawe ben thinking about this algortam for about a month.

Share this post


Link to post
Share on other sites
red drake, trust me the grid based method is old school. You can even replicate the grid method by stopping the quad tree subdivision at a predefined grid size, so in effect you would have your grid system yet the CULLING effiency for both collisions and view from an octree structure.

Share this post


Link to post
Share on other sites