0
\$\begingroup\$

I am trying to implement grid-based collision in a 2d game with moving circles. The canvas is 400x400 pixels. Below you can see the code for my Grid class. What I want it to do is check inside which box the entities are located and then run a collision check if there are 2 or more entities in the same box.

Right now I do not know how to find the position of an entity in a specific box. I know there are many tutorials online, but I haven't been able to find an answer to my question, because they are either written in C/C++ or use the 2d array approach.

Code snippets and other help is greatly appreciated. Thanks.

public class Grid {

ArrayList<ArrayList<Entity>> boxes = new ArrayList<>();
double boxSize = 40;
double boxesAmount = 10;
...
...
public void checkBoxLocation(ArrayList<Entity> entities) {

      for (int i = 0; i < entities.size(); i++) {
// Get top left coordinates of each entity         
            double entityLeft = entities.get(i).getLayoutX() - entities.get(i).getRadius();
            double entityTop = entities.get(i).getLayoutY() + entities.get(i).getRadius();

// Divide coordinate by box size to find the approximate location of the entity
            for (int j = 0; j < boxesAmount; j++) {   //Select each box
                if ((entityLeft / boxSize <= j + 0.7) && (entityLeft / boxSize >= j)) {
                    if ((entityTop / boxSize <= j + 0.7) && (entityTop / boxSize >= j)) {
                        holdingBoxes.get(j).add(entities.get(i));
                        System.out.println("Entity " + entities.get(i) + " added to box " + j);
                    }
                }
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ You never declare holdingBoxes. What is the spatial interpretation of a box? You need 2 dimensions to handle most 2d scenes, which is why all the references use 2d arrays. What is the meaning of 0.7? You need to compare the entities bounding box with that of the box, search for AABB collision detection. \$\endgroup\$ – user41442 Feb 10 '14 at 4:11
1
\$\begingroup\$

The purpose of the box is just to speed up finding potential collisions. You don't want to think of positions within the boxes at all. Use your normal collision code once you've determined which entities are potentially colliding.

\$\endgroup\$
  • \$\begingroup\$ Indeed, you are basically implementing your own quad-tree structure here. Google for quadtree for the basic principles and why they are useful in collision prediction. \$\endgroup\$ – Felsir Aug 4 '15 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.