# Tagged Questions

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, ...
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 ...
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 ...
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, ...
321 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) ...
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 ...
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 ...
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 ...
274 views

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 ...
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 ...
633 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 ...
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, ...