0
\$\begingroup\$

I am trying to make a top down shooter that could potentially have hundreds of objects at once at one point. I need to check collision with projectiles, walls, and enemies. I am currently using ArrayLists which probably won't suffice later on and was wondering if someone had a good method or knows a good method for checking all of those objects at once. This is going to be a game for smartphones and is built in java. Any ideas would be great or if you could point me in some direction that would be fantastic.

Thanks in advance!

\$\endgroup\$
5
  • \$\begingroup\$ Is there a java port of Box2D? otherwise, time to go read up on spatial partitioning schemes. \$\endgroup\$ – Matt D Mar 10 '14 at 3:35
  • \$\begingroup\$ Im using the built in Circle and Rectangle classes that come with libgdx. \$\endgroup\$ – G3tinmybelly Mar 10 '14 at 3:43
  • \$\begingroup\$ And yes there is a java port of box2d but I don't think there is a way to implement that in my game. \$\endgroup\$ – G3tinmybelly Mar 10 '14 at 3:47
  • \$\begingroup\$ Did you read about uniform grids? They are easy to implement. \$\endgroup\$ – AturSams Mar 10 '14 at 7:55
  • \$\begingroup\$ Many other space partitioning options exist. This answer lists some others. gamedev.stackexchange.com/questions/21607/… \$\endgroup\$ – Seth Battin Mar 11 '14 at 3:30
1
\$\begingroup\$

When I've got huge worlds where enemies can move freely, I tend to create and 2D-array representing e. g. 8x8 tile chunks (I've you're not using tiles, than just take the base unit) and whenever enything is moving, I put a pointer to that object into the specific part of the array the moving thing has been moved into. When doing collusion, I simply do the collusion for object A, I just check intersection with all the other objects in the specific cell of the array and eventually the adjected ones, too.

\$\endgroup\$
1
  • \$\begingroup\$ That's called a uniform grid as mentioned in the comments. \$\endgroup\$ – AturSams Mar 10 '14 at 10:03
0
\$\begingroup\$

Using chunks like user2241553 suggested is a valid approach. But when you have some algorithm skill, you might want to store any immovable objects in a 2d-tree. A 2d-tree is a binary tree where nodes with even depth are sorted by x-coordinate and nodes with odd depth by y-coordinate. Searching for objects in such a tree which are inside a specific area takes only logarithmic time.

2d trees don't perform that well for objects which move, because whenever an object changes its position it needs to be removed and re-inserted.

\$\endgroup\$
1
  • \$\begingroup\$ Yes, it's logarithmic but unless there are very populations of objects (which is unlikely in a game) then a uniform grid is O(1) \$\endgroup\$ – AturSams Mar 10 '14 at 11:34

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