Efficient Collision detection for polygons (fleet) on Android

0
votes

I'm trying to make an RTS for android using libgdx. I would like to have collision detection to be able to detect ships inside the range of weapons and collision between my bullets and the ships.

So far my strategy has been to use a PM QuadTree that I coded myself to store every segment of every polygons. A polygon being the hitbox of a ship.

Every frame I clear and add all the segments back in the quadtree. Every segment has a reference to the ship it belongs to. When I add a ship, I add it recursively to the nodes of the quadtree based on the intersection with the bounds of a node.

Detection collision is done by polling every polygon inside a rectangle that look into every node that fit entirely or partially inside the rectangle.

My problem is that adding every ship every frame gives bad result on Android. On Desktop it is fast enough but on Android it can takes up to 100 ms just to add around 200 segments.

Is there something wrong with my implementation (it shouldn't be this slow ?) or should I use another strategy for collision detection ? I thought about clearing the quadtree only every 5 frames but it would make the detection unprecise.

I have measured that some simple math operation to calculate intersection takes up to 50 more times on my android and I'm not sure why. Surely my phone cpu is not 50 times slower than my laptop, is it ?

EDIT: It's a sufficiently fast moving RTS. Often the whole fleet is moving, thus every segment. In that case it won't speed up much my insertion. I need a consistent speed-up of around 50 or a 100 to obtain 100 frame per second.

1
androidlibgdxcollision-detection
I have done a lot of research on openGL and FPS on ANdroid before moving to Libgdx, but everything that uses OpenGL has one problem: OpenGL drawing forces V-Sync. You can't get a faster framerate than the update interval of the screen. So you are stuck with 30 or 60 frames (some may have higher though). That is what delta is for, to accurately get things like acceleration consistently over different frame rates. This is not an answer to the question, but my point is you cannot get 100 FPS on a phone unless the display update frequency of the display is 100 (don't remember the unit here) - Zoe

1 Answers

1
votes

I believe insertion time on a quadtree should be O(lg n) in the average case for a balanced data set and O(n) in the worst case. So by rebuilding the quadtree every time you're doing an O(n lg n) or O(n2) operation every frame.

For video game data, this is probably a lot of wasted computation, because in general your entities are going to be positioned in the same location or a nearby location from frame to frame; that is, their position in the tree is unlikely to change.

The first optimization I'd try is adding one pass over the tree to find segments that are no longer correctly located within the tree, remove those, then reinsert into the tree. When the number of segments that need to be moved is small, this will save you time; when it is large, the cost of the extra pass will be small compared to your reinsertion cost anyway.