Making Balls Bounce off of Walls in a Labyrinth

Re:Making Balls Bounce off of Walls in a Labyrinth by joshu on Wednesday June 18, 2014 @11:50PM (#7914369)

This seems like an intricate implementation for a very specific case. What if you wanted to have moving walls or non-rectilinear walls, etc? There are more appropriate data structures for storing a set of lines and efficiently seeing if another line (eg the dot's trajectory) has intersected one of them.

[ Parent | on HN ]

Re:Making Balls Bounce off of Walls in a Labyrinth by sillysaurus3 on Thursday June 19, 2014 @12:17AM (#7914465)

If your walls and balls are both moving, you'll need to do collision detection by making the ball into a capsule (integrate its bounding sphere's position over current timestep) and make the wall into a quadrilateral (integrate wall's position over current timestep). If the ball's path intersects the quadrilateral, its velocity needs to be reflected at the intersection point. When your collision is dynamic like that, your performance isn't going to be O(1), which is what the poster was trying to achieve. You can make it sublinear, but when there are fewer than ~100 objects the speed gain isn't really worth the complexity. 100x100 is still only 10,000 ops, which can probably be done in javascript without performance problems. It's definitely a fun learning exercise though, and it will give you some valuable insight into how physics libraries work.

[ Parent | on HN ]

Re:Making Balls Bounce off of Walls in a Labyrinth by joshu on Thursday June 19, 2014 @07:40PM (#7918885)

i think the usual way is to advance the timestep, see if the item penetrates the other item, and then go back and advance half a timestep.

but my point is, you don't need to check the entire world if you are using a quadtree or rtree or whatever.

[ Parent | on HN ]

Re:Making Balls Bounce off of Walls in a Labyrinth by sillysaurus3 on Thursday June 19, 2014 @09:55PM (#7919194)

I don't think that's the usual way, because it will completely miss collisions for fast-moving balls.

They don't need a quadtree or an rtree if the number of objects is fewer than 100.

Also, when using a quadtree/rtree etc with dynamic objects, you'll need to rebalance the tree as objects move around. If the rebalancing is more expensive than the speed gained by using it, then those datastructures can be harmful, not helpful. This is case is relatively rare but something to keep in mind.

[ Parent | on HN ]

Re:Making Balls Bounce off of Walls in a Labyrinth by userbinator on Thursday June 19, 2014 @01:09AM (#7914558)

storing a set of lines and efficiently seeing if another line (eg the dot's trajectory) has intersected one of them.

This is the basic principle behind raytracing and the variant raymarching, which can be used to create some very interesting images with very compact descriptions:

http://iquilezles.org/www/material/nvscene2008/rwwtt.pdf

Applied to things bouncing around on other things, this technique would enable calculating exactly when the collisions are, which is a possible optimisation to requiring collision checks at each time step. It is very similar to the principle of a discrete event simulator.

[ Parent | on HN ]