# Efficient Collision detection for polygons (fleet) in an RTS

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 ?

It's a sufficiently fast moving RTS. Often the whole fleet is moving, thus every segment.

I heard about RDC in that article. Would that be a better algorithm ? My issue is that some ships are hard to be bounded by a sphere if they're very long but not wide.

• Polygon collision sounds a bit excessive for an RTS. Are you sure simple spheres aren't enough? – Mario Jun 29 '15 at 6:25
• Well I want to do ships that are of various size and possible much longer than wide. – Atol Jun 29 '15 at 8:05
• What about boxes? – wolfdawn Oct 10 '15 at 17:38