All Questions
Tagged with collision-detection optimization
60 questions
1
vote
0
answers
217
views
Sweep and Prune algorithm performance
I just managed to implement my Sweep and Prune algorithm together with AABB and it's working correctly in the first axis (I haven't implemented second and third yet to complete the collision detection)...
- 63
2
votes
1
answer
163
views
How to set up high-performance collisions for level geometry in Unity?
I'm new to Unity. I was wondering what the best workflows were for placing colliders.
I'm going for high performance, and I've heard that mesh colliders aren't as performant as just placing down box ...
0
votes
3
answers
151
views
Reduce processing time of image to shape
I'm making a simple game engine using Java and have found a major issue.
To create accurate collision detection I decided to convert a transparent image into a ...
0
votes
1
answer
46
views
Change of computing power/ time needed when imported Mesh triangle number changes
I am doing a Unity project, that makes it necessary to import a mesh consisting of triangles.
As it is possible to reduce the amount of triangles in a mesh and keeping the structure similar, I am ...
- 11
2
votes
1
answer
738
views
Efficiently find all points within a circle
I am writing code that requires me to find all points within circle on certain parts of the screen hundreds of times per frame. I wrote a quadtree for this and have 1 method called query_circle that ...
- 67
3
votes
1
answer
4k
views
Efficient way to check collisions for many objects
I am making a Bloons tower defense game and I came across a problem with regards to collisions. The way my code currently works is all the current bullets on the screen(could be potentially thousand) ...
- 67
0
votes
0
answers
22
views
More smaller scripts or less larger in Unity 2d Development? Better or worse performance? [duplicate]
In my unity 2d game I had large amount of scripts which were components of different enemies and obstacles. All of them were checking for collison, had FixedUpdate, Start and OnCollisionEnter2D and ...
1
vote
0
answers
87
views
Is treating object meshes as nav meshes a sensible strategy for grounding characters?
It bothers me that a lot of character controllers are written to rely on raycasting for movement along the ground. While this solution is very straightforward and general (especially in the sphere ...
- 181
1
vote
1
answer
490
views
How does a game like slither.io handle collision?
This question can be generalized to "how does one efficiently determine if a collision has taken place between curvy lines"
On https://slither.io there are snakes that players play as that ...
- 235
0
votes
1
answer
280
views
How can I keep track of which "rooms" characters and NPCs are in?
I have a Unity 2D project which has a player character and numerous NPCs all potentially moving (top-down) at the same time during play. The number of NPCs is not to exceed 100 (and will be, probably, ...
- 103
5
votes
1
answer
3k
views
Quadtree for AABB collision boxes
I have a whole bunch of entities constantly being processed and testing for collisions. I've tried to optimize this by stopping certain entity types from checking each other, dead entities not being ...
- 87
0
votes
0
answers
341
views
Cache friendliness of AABB-Tree: binary vs N>2
I found that state-of-the-art physics engines like Bullet and Box2D all use binary AABB-Tree for broad-phase collision detection.
I wonder, did anybody tested AABB-tree with >2 branches per node ?
...
- 193
0
votes
3
answers
3k
views
How to optimize collisions
I'm building a 2D MORPG using JavaScript, Node JS and socket.io
To prevent cheating, I have to run all collisions for all players on my server.
I'm currently doing fairly simple square collisions ...
- 139
4
votes
1
answer
3k
views
Efficient minimum distance between two axis aligned squares?
I have two 2D arbitrarily-positioned axis-aligned squares.
I need to find the minimum distance between those squares – i.e. if you were to draw them, what's the length of the shortest line you could ...
- 143
3
votes
2
answers
3k
views
How does layer based collision affect performance
In Unity3D, and others, there are Layer Based Collision System which makes collisions only happen between specified Layers.
It defaults to all layers colliding with all others.
Does making use of ...
- 309
1
vote
1
answer
184
views
Scalability/Performance of physics-based character animation
I am asking this question because I am currently at the point where I have to think about how the characters in the game that I am making will be animated and I want to check if my desired approach ...
- 145
0
votes
1
answer
325
views
optimizing collision detection with stationary objects (walls, floors, obstacles, etc.)
For detecting collisions between sprites, I know a 2D spatial hash is a way to optimize the number of collision checks that need to happen. But is there a way to optimize even further for objects that ...
- 103
0
votes
1
answer
549
views
What's the fastest collision detection
I want to build a simulator using Game Maker in which there are many (up to hundreds) of obj_Cell, each has a radius of 10, (they don't have sprites, they just draw ...
- 416
0
votes
2
answers
534
views
Does it matter who does the collision detection?
I gave an answer to How to decide which GameObject should handle the collision?, and received a lot of negative feedback on it, claiming that it does not matter who does the collision detection. I am ...
- 5,881
0
votes
1
answer
177
views
How to combat exponential growth in sprite messaging?
In my 2D platformer game, I have a number of sprites moving around the world. When two sprites collide with each other, I calculate how deep the collision is and then call a virtual method on both ...
- 203
1
vote
1
answer
711
views
Frustum culling takes ages c++
I have two ways of doing frustum culling taken from different web sources. First one takes 200ms to check 10k AABBs, second around 50ms for the same box count.
I read some forum answers, people say 0....
- 282
10
votes
1
answer
2k
views
In a 2D physics engine, how do I avoid useless collision resolutions when objects come to a rest?
In a physics engine I'm developing (for learning) using love-2d, I implemented collision resolutions in this way:
...
- 3,470
14
votes
4
answers
14k
views
How do I efficiently check if a point is inside a rotated rectangle?
Part for the sake of optimization, part for learning purposes, I will dare to ask: How can I most efficiently check whether a 2D point P is inside a 2D rotated ...
- 569
1
vote
3
answers
264
views
Best collision algorithm for Axis Aligned Bouding Boxes [duplicate]
I have a number of quads (suppose like 20-40) and i want to quickly check the collisions between any of them. I would like to know if there's a quick algorithm to do that 60 times per second without ...
user51054
0
votes
2
answers
545
views
Efficient Collisions Iteration?
My project has upwards of 3000 2D objects but not all of them collide with each other. Between each object that can collide, a CollisionPair is created and stored inside a flattened array.
Currently, ...
- 2,031
1
vote
2
answers
295
views
Game lags when my player collides with a specific object (solution known, unsure how to implement)
I'm developing a game in Android using LibGDX (although this is more of a JAVA problem than an engine problem). My aim is to have my player bounce off one spring onto another that will eventually take ...
- 197
0
votes
2
answers
185
views
Collision detection enhancement
I am developping a spaceinvader-like game. There comes the problem of how to handle collision detection.
At first I was doing like that :
...
- 1,057
1
vote
2
answers
1k
views
Optimizing Collision Detection in a 2D Game
I am optimizing my "little" Java (LibGDX) shooter game, and perhaps unsurprisingly, collision detection is a "bottleneck"; I've kind of reached my performance goals already, but I want to tweak the ...
- 559
3
votes
1
answer
332
views
How do I efficiently collide and match groups of coloured circles?
I am new to game programming and working on clone of this game in libgdx.
The game has some static balls and one ball that moves. I want to check if the moving ball collides with any static ones, but ...
- 161
4
votes
2
answers
2k
views
How should I choose quadtree depth?
I'm using a quadtree to prune collision detection pairs in a 2d world. How should I choose to what depth said quadtree is calculated?
The world is made mostly of moving objects1, so the cost of ...
- 161
6
votes
2
answers
8k
views
How can I improve my collision detection's performance?
I'm new to programming and want to speed up the collision detection in my C++ 2D platformer game engine.
Currently, only the player's collision detection works: Every frame, the player's update ...
- 63
1
vote
1
answer
2k
views
Can I use a list sorted by Morton Code for broad phase collision detection?
Until now I used a list of objects sorted by a single axis for limiting the amount of objects that collisions are checked against.
The idea is simple: if the x coordinate of two objects differs by ...
- 6,869
2
votes
0
answers
302
views
Storing rigid body collision shapes in local or world coordinates
I'm writing the beginnings of a lightweight 2d rigid body engine (in javascript, as a hobby project), and i'm debating whether to store collision shapes in local or in (updated as needed) world ...
- 36
1
vote
1
answer
1k
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, ...
- 339
24
votes
6
answers
8k
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 ...
- 3,131
17
votes
3
answers
12k
views
Small, High-Speed Object Collisions: Avoiding Tunneling
EDIT/UPDATE: My biggest question right now is whether step 3's "t=..." equation is a good idea or there a better way to do it. Most other issues have been partially or fully addressed, but no ...
9
votes
4
answers
7k
views
How do collision meshes work in games like Zelda on the N64?
I was recently reading about the technology of Ocarina of Time/Majoras Mask and discovered that world collision is done using a single triangle mesh (vertices, normals, etc) for an entire area. There ...
- 292
13
votes
5
answers
5k
views
How can I optimize a collision engine where order is significant and collision is conditional based on object group?
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 ...
- 1,190
20
votes
3
answers
12k
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, ...
- 5,253
7
votes
1
answer
2k
views
Automatically generate low detail collision meshes
I lately integrated Bullet Physics into my little game engine, but for now I only use basic shapes as spheres or boxes for collision checks. For more realistic physics I need collision meshes for all ...
- 5,751
5
votes
2
answers
3k
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) space. ...
- 165
1
vote
0
answers
285
views
Updating physics for animated models
For a new game we have do set up a scene with a minimum of 30 bone animated models.(shooter)
The problem is that the update process for the animated models takes too long.
Thats what I do:
Each ...
- 165
1
vote
2
answers
596
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 ...
- 657
1
vote
1
answer
354
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 ...
- 657
5
votes
1
answer
14k
views
How to detect collision in Unity3D without rigid bodies?
The target platform of my game is mobile devices therefore I try to develop it performance oriented. It will be a strategy game so I don't really need physics in it, consequently I did not add ...
- 822
2
votes
4
answers
8k
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 ...
- 91