# reverse grid?

This topic is 3542 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I talked to a colleague today about my QuadTree [for dynamic collision detection purposes]. He suggested for performance issues that I should rather use a grid. He showed me an example: instead of having a struct for each gridcell which holds a list of objects, he created another struct representing the objects, containing a reference to a node. When I move an object and have to calculate the reference node, it seems faster. Does anyone know if this technique has a name? He didn't know it himself, he just came up with it. But I can think of some advantages which may come with this method. There must be an optimized version of this somewhere. I can't believe that noone thought of this before. So, who can help me out?

##### Share on other sites
It's called a "grid."

It's a good method for simple cases, but riddle me this: what happens when an object is too big to fit inside a grid space? what happens if an object is not entirely enclosed by its grid space?

For some applications, this is not an issue.

But you shouldn't just rely on what seems faster. Profile and compare the two methods, then pick the winning one.

Also, I've come to learn that no matter how obscure a problem, or how innovative a solution, there was some guy from 1962 that already wrote a whitepaper about it. :)

##### Share on other sites
The 1st method: each grid cell has a list of objects that are inside it
The 2nd method: each object knows the index of the grid cell that it is in

Both are useful, depending on what you are doing, but the 2nd method will be much slower for all the cases that make grids useful (mainly adjacency of objects).

Location: What grid cell is object X in?
Method 1: O(1)
Method 2: O(1)

Adjacency: What objects are in grid cell X,Y?
Method 1: O(1) - look in the grid cell X,Y
Method 2: O(n) - linear search

Adjacency: What objects are within a Z grid cell radius of cell X,Y
Method 1: O(1) - look in the grid cell X,Y and the surrounding cells
Method 2: O(n) - linear search

Note: in nearly all grid implementations, objects will be in multiple cells, otherwise you will get really weird collision anomalies when objects are near grid lines.

Personally, I save "curentGridCell" with all objects and the corresponds to the the cell that the center of the object is in.

##### Share on other sites
Quote:
 Original post by erissianIt's a good method for simple cases, but riddle me this: what happens when an object is too big to fit inside a grid space? what happens if an object is not entirely enclosed by its grid space?

For those cases there's the hgrid (hierarchical grid) which is similar to a quadtree/octree except that the top levels are missing (besides some storage methods, maybe).

Another possibility would be to use recursive grids, i.e. you start with a coarse grid and refine the cells that need to be refined. The level of refinement is up to you and could also depend on the objects within the cell. That's still similar to a quadtree/octree but each node/cell doesn't necessarily have 0, 4 or 8 but might hava abn arbitrary number of children.

##### Share on other sites
Thank you for your replies.
@EJH: I didn't quiet understand your example. What do you mean by O, and for which number of processes does 1 or n stand for?
Of course, if an object is overlapping into another cell it should be in both cells, so I can have a clean cd.

I guess I really just have to find the best way myself.
My situation is, that most of the objects are constant for the most time. I'm working on an animation editor, where I only need to check for collision between the mouse and the vertices. I might use an Octree which seems like the fastest way of doing things, since an Update of the tree won't happen too often.

##### Share on other sites
EJH is using Big O notation to describe how long the various methods take to complete. It's a standard and widely used notation in the computer programming field, particularly in computer science. Getting familiar with Big O - and, more specifically, with the performance characteristics of your algorithms and how to measure those characteristics - will be an essential addition to your programmer's toolbox.

##### Share on other sites
You just made your grid an intrusive container.
Nothing special.

Quote:
 @EJH: I didn't quiet understand your example. What do you mean by O, and for which number of processes does 1 or n stand for?

How can you even use algorithms and data structures, let alone design new ones, when you don't even understand basic notions of complexity?

##### Share on other sites
wow, you really know a lot loufoque. I hope I can be like you someday.

This thread is sort of done, my question is answered.

##### Share on other sites
Quote:
 Original post by loufoqueHow can you even use algorithms and data structures, let alone design new ones, when you don't even understand basic notions of complexity?

Not everyone learns how to do things in the Ivory Tower. And every program "uses algorithms and data structures" - just perhaps not particularly well or in a particularly sophisticated way.

I really think you ought to adjust the attitude you convey in your posts. In my official moderator capacity, you know. You are crossing the line beyond "constructive criticism" with comments like this.

##### Share on other sites
I was being honest and pragmatic, not insulting.
I do not see how you can do any algorithmic work without understanding how the algorithm efficiency varies depending on input.

Quote:
 Not everyone learns how to do things in the Ivory Tower

Basic complexity principles such as these are taught in Computer Science 101, if not earlier, such as in mathematics in high school.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 28
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634112
• Total Posts
3015566
×