Name: Anonymous 2015-06-12 15:07
What are some of the most powerful flexible algorithms you use? Stuff that made a big speedup or something.
Here's a cool one I learned for games: buckets: If you wanted to have a screen full of balls that can each bounce off each other then you'd have to do O(N^2) collision tests. So what you do instead of is divide the screen into buckets about double the size of the character; make a linked list of each cell putting the characters into the right buckets then do the collision tests per bucket O(N) since you generally only between 0 and 2 characters in one cell. Let's you have millions of objects when before you could only have a couple thousand.
Here's a cool one I learned for games: buckets: If you wanted to have a screen full of balls that can each bounce off each other then you'd have to do O(N^2) collision tests. So what you do instead of is divide the screen into buckets about double the size of the character; make a linked list of each cell putting the characters into the right buckets then do the collision tests per bucket O(N) since you generally only between 0 and 2 characters in one cell. Let's you have millions of objects when before you could only have a couple thousand.