1

I'm making a 2D game in XNA, and the NPC sprites are all grouping together into one mass, appearing to be one sprite. I thought that a way around this would be to do collision detection on all of the sprites, and just move them away from each other, but that meant doing hundreds of checks a frame.

I then decided to break up the game window into a grid (6*6), and put each sprite into one of 36 arrays, so I'd only have to check each sprite against each other sprite in the same quadrant. This is now my problem, as I'm checking the position, which is a Vector2, and I have no idea how to put them all in the relevant grid square.

If I've been unclear anywhere, please let me know, and I'll do my best to improve it.

2 Answers 2

3

It's surely not the most optimized way to do it, but the following could be a simple approach. Felix K.'s answer might provide you more performant solutions. In case you want more than one element to share the same position in the grid, you can tweak the sample by changing the type of the grid from Vector2 to Vector2[] or the collection type which sounds most convenient to you.

//Size of each square
const int squareSize = 10;
const int gridSquares = 6;
var grid = new Vector2[gridSquares,gridSquares];
//Sample vectors
Vector2[] vectors =
    {
        new Vector2(0, 0),
        new Vector2(25, 0),
        new Vector2(20, 40),
        new Vector2(59, 59)
    };
foreach (var vector in vectors)
{
    var x = vector.X/squareSize;
    var y = vector.Y/squareSize;
    grid[x, y] = vector;
}
1

First: Why not use Box2d? If you don't want to use it you might looking for a quad-tree, there are some good implementations of a quad-tree for games. I prefer a full expanded quadtree which is faster than the normal ones but i can't find any article online about it. I have a scanned article about this in my mailbox but i won't post it here.

Basically you can do this to check the relevant nodes in a quad tree:

  • Check if the object fits inside the root node (If not the object is in the top node)
  • Check the 4 subnodes if the object fits into one of them. Process this until the object does not fit in any of the subnodes, then add it to the current node.
  • When processing the scene find the node (save it in the containing object) which contains the actual object, now walk up to the parent nodes until you reach the root and check for collisions in each of them.
  • Example of quad-tree

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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