1
vote
0answers
66 views

Speeding up point-in-polygon for Python

In researching collision detection methods for non-Rect-like objects I came across point-in-polygon -- specifically, the even-odd rule. The one presently on Wikipedia claims it is written in Python, ...
18
votes
6answers
2k views

How to optimize the distance function?

While developing a reasonably simple RTS-like game, I noticed my distance calculations were causing an impact in performance. At all times, there are distance checks to know if a unit is in range to ...
13
votes
4answers
1k views

Optimizing collision engine bottleneck

If this is your first time on this question, I suggest reading the pre-update part below first, then this part. Here's a synthesis of the problem, though: Basically, I have a collision detection ...
8
votes
3answers
806 views

Are collision detection always O(n^2)?

Are physics engine able to decrease that complexity, for example by grouping objects who are near each other and check for collisions inside this group instead of against all objects ? (for example, ...
4
votes
2answers
320 views

Space-efficient data structures for broad-phase collision detection

As far as I know, these are three types of data structures that can be used for collision detection broadphase: Unsorted arrays: Check every object againist every object - O(n^2) time; O(log n) ...
0
votes
2answers
440 views

My grid based collision detection is slow

Something about my implementation of a basic 2x4 grid for collision detection is slow - so slow in fact, that it's actually faster to simply check every bullet from every enemy to see if the ...
1
vote
1answer
209 views

Grid based collision - How many cells?

The game I'm creating is a bullet hell game, so there can be quite a few objects on the screen at any given time. It probably maxes out at about 40 enemies and 200 or so bullets. That being said, I'm ...
-1
votes
4answers
1k views

Collision detection between many objects

I'm working in a 2d environment and have hundreds of objects, brute force collision checking would be out of the question, but would my method below work? For example, lets say I have a ...
1
vote
2answers
274 views

Boolean checks with a single quadtree, or multiple quadtrees?

I'm currently developing a 2D sidescrolling shooter game for PC (think metroidvania but with a lot more happening at once). Using XNA. I'm utilising quadtrees for my spatial partitioning system. All ...
3
votes
1answer
243 views

Collision Detection Efficiency

I've just written my first successful collision detection code, and it works great for a small scene of actors (player + 4-5 obstacles). However, I realize that since it checks every possible ...
0
votes
2answers
629 views

Detecting if line crosses rectangle in python. Need speed boost

I am currently writing a top down man vs robot shooter. The game works now, but if I have a decent sized level it runs slowly when you are being chased by robots. While just roaming around it can go ...
2
votes
3answers
855 views

Coarse Collision Detection in highly dynamic environment

I'm currently working a 3D space game with A LOT of dynamic objects that are all moving (there is pretty much no static environment). I have the collision detection and resolution working just fine, ...
2
votes
1answer
250 views

Collision filtering by object, team

I am looking for a good method to determine which objects will be considered for collision with other objects. My current idea is that each object has the following properties: alwaysCollidesWith = ...
27
votes
9answers
21k views

What is the fastest way to work out 2D bounding box intersection?

Assume that each Box object has the properties x, y, width, height and have their origin at their center, and that neither the objects nor the bounding boxes rotate.