Name: Anonymous 2007-12-16 9:12
Hi, I'm relatively new to programming games. In order to teach myself a bit about it, I'm attempting to create a very simple 2-dimensional game.
When planning my game I realized that I would need some sort of collision detection. Though I haven't started coding yet, I've attempted to illustrate my problem on this image: http://img248.imageshack.us/img248/408/picug2.png
Assume that box 0 is being pushed in the direction of box 1. Box 0 would collide with box 1; box 1 would accelerate and collide with box 2 etc.
I had planned my game as running an infinite loop that would update the position of these boxes before drawing them. Therefore, my approach to this would be to check whether any of these boxes collides with any of the other boxes.
I've made a function to test whether two boxes collide or not, but it seems I'll be running this function several times each update. Let's assume I had 100 boxes in my game, I'd have to check whether the first box collided with the remaining 99 boxes. Then I'd check if the next box collided with the remaining 98 and so forth.
It seems to me like I'd end with a complexity like: O((n*(n+1))/2) for something I'd have to run each update. Though my game is rather small, this seems like a heavy way of doing it.
In my example, the boxes would never collide with any box that isn't next to them, but I’m attempting to make a more general solution, that would also work if these boxes have switched place for some reason.
If you've read through my wall of text I thank you. My question is how do I avoid this complexity and still check the collision of all boxes? If there is no simple answer, perhaps someone could point me in the direction of some article dealing with this problem.
I will reply to my own post, telling myself to read SICP in order to get that reply out of the way.
When planning my game I realized that I would need some sort of collision detection. Though I haven't started coding yet, I've attempted to illustrate my problem on this image: http://img248.imageshack.us/img248/408/picug2.png
Assume that box 0 is being pushed in the direction of box 1. Box 0 would collide with box 1; box 1 would accelerate and collide with box 2 etc.
I had planned my game as running an infinite loop that would update the position of these boxes before drawing them. Therefore, my approach to this would be to check whether any of these boxes collides with any of the other boxes.
I've made a function to test whether two boxes collide or not, but it seems I'll be running this function several times each update. Let's assume I had 100 boxes in my game, I'd have to check whether the first box collided with the remaining 99 boxes. Then I'd check if the next box collided with the remaining 98 and so forth.
It seems to me like I'd end with a complexity like: O((n*(n+1))/2) for something I'd have to run each update. Though my game is rather small, this seems like a heavy way of doing it.
In my example, the boxes would never collide with any box that isn't next to them, but I’m attempting to make a more general solution, that would also work if these boxes have switched place for some reason.
If you've read through my wall of text I thank you. My question is how do I avoid this complexity and still check the collision of all boxes? If there is no simple answer, perhaps someone could point me in the direction of some article dealing with this problem.
I will reply to my own post, telling myself to read SICP in order to get that reply out of the way.