Timeline for Are collision detection always O(n^2)?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2013 at 13:55 | history | tweeted | twitter.com/#!/StackGameDev/status/347714283158790145 | ||
| Jun 15, 2013 at 22:58 | comment | added | ratchet freak | @sm4, if the movements is limited then a few passes of bubble sort can take care of that (just mark the moved objects and move them forward or backward in the array until they are sorted. just watch out for other move objects | |
| Jun 15, 2013 at 16:36 | answer | added | bobobobo | timeline score: 2 | |
| Jun 15, 2013 at 15:11 | comment | added | MartinTeeVarga | @Byte56 Sweep and Prune has complexity O(n log(n)) only if you need to sort every time you test. You want to keep a sorted list of objects and each time you add one, just sort it to the correct place O(log(n)) therefore you get O(log(n) + n) = O(n). It gets very complicated when objects start moving though! | |
| Jun 15, 2013 at 14:34 | comment | added | House | You bet. I believe both have implementations of SAP (Sweep and Prune) (among others) which is a O(n log(n)) algorithm. Search for "Broad Phase Collision Detection" to learn more. | |
| Jun 15, 2013 at 14:30 | answer | added | MartinTeeVarga | timeline score: 21 | |
| Jun 15, 2013 at 14:29 | comment | added | jokoon | byte56: so, are box2d and bullet faster than O(n^2) ? | |
| Jun 15, 2013 at 14:28 | history | edited | jokoon | CC BY-SA 3.0 |
extended my question for popular physics engine
|
| Jun 15, 2013 at 13:35 | answer | added | luiscubal | timeline score: 9 | |
| Jun 15, 2013 at 13:29 | comment | added | House | See here: gamedev.stackexchange.com/questions/14373/find-nearest-object | |
| Jun 15, 2013 at 13:22 | comment | added | House | Two words: Spatial partitioning | |
| Jun 15, 2013 at 13:15 | history | asked | jokoon | CC BY-SA 3.0 |