A "new" way for Collision detection
Author
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 ...
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
.
don''t worry, everyone has invented someone elses algorithm at some point in their life
.
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...
Author
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.
(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.
Author
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)
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
Hope this clears it up some...
Dwiel
Go see some hot chicks and vote to see who is hottest: dwiel.no-ip.com
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
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
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.
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.
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
