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.
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.
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.
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:
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.
Don't represent a ball's velocity with an angle and speed. Use a 2D vector instead.
To bounce left/right:
vel.x = -vel.x
To bounce up/down:
vel.y = -vel.y
This representation also generalizes to 3D. You'll have a lot of trouble trying to represent a 3D heading with angles, whereas using a 3D velocity vector is straightforward. (In 3D space, using angles to represent orientation can also suffer from gimbal lock whenever you try to rotate the orientation.)
This is true, but only for this special case where walls are strictly horizontal or verticle. In the more general case an angle, magnitude representation would be fine.
Wouldn't it make more sense to model also the walls as vectors? Then you mostly need vector-to-vector intersection etc, fairly standard mathematical stuff.
If the maze is not standard but can be anything, the walls can be stored in a quadtree or some similar efficient structure.
>Wouldn't it make more sense to model also the walls as vectors?
Yes. That's why r,theta representation makes more sense computationally because reflection across a normal is just adding and subtracting two angles. Of course, you pay heavily for using only this representation on every tick() during merely linear motion, because in the end our displays are cartesian, and you'll have to convert r,theta to x,y. The solution, of course, is to maintain both representations and use whichever one is faster - a classic space-for-time trade-off.
Not really. That kind of code complexity is simply not worth the tradeoff. You'll waste a bunch of time fixing bugs in your dual representation codebase. It's always better to do the simplest thing first, and then optimize if and only if it turns out to be necessary. In this case, the simplest and most effective way is to use strictly vector representation, because it will result in the lowest complexity codebase.
Modern computers are monstrously fast. So fast that it's hard to imagine just how fast they are. The more time you spend thinking about optimizations before they're necessary, the more time you're not spending on implementing features.
If it's just for fun, though, go for it. A learning exercise is always nice.
I've used both and using vectors for the position and velocity of both the ball and the wall is very much easier for modelling collisions at arbitrary angles in both 2D and 3D. Working out the new angle and magnitude of a ball bouncing off a wall at an arbitrary angle is a nightmare in comparison. Using vectors and vector math also works well when modelling more complex collisions (i.e. solving the problem of balls flying through walls at high velocity) and other physical phenomenon like friction and gravity.
I would've realised that the 16 different wall combinations would've fit well into a 4-bit encoding - e.g. 1 for left, 2 for right, 4 for up, 8 for down. That gets rid of the sets and reduces the check for wall existence to a simple AND.
If you have a "wall" only in one tile and not its adjacent one, that essentially creates a one-way wall, which could be an interesting effect too.
I think there is a simpler way to represent this. Represent each wall as a pair of tiles. Whenever a ball would move from tile A to tile B in a single time step, check if there is a wall whose pair of tiles is A and B. If there is such a wall, the ball bounces. If not, the ball doesn't bounce. I don't think you should need to write any code that handles north/south/east/west with a switch statement, it should all be vector math.
I think the only edge case here would be a ball that hits a corner dead on. You would need code that says "if a ball goes from A to B in a time step, and those are diagonal, treat it as A -> C -> B where C is one of the tiles adjacent to both A and B, for bounce checking."
The linked article is pretty thorough, but a little complex for the nature of the problem I think. What I did was just calculate all tiles (I call them 'cells') intersected by the displacement vector of the projectiles (balls) moving around the maze, which can be done in constant time if your maze dimensions are fixed. Then I look up the walls of intersected cells, and calculate the closest intersection of the displacement vector with any of these walls. This intersection happens somewhere along the vector between t=0 and t=1, so I translate the projectile position back in time using this value, change its direction (invert either x or y based on the orientation of the wall), then move it along (1 - t) * v_inverted to solve the 'fast projectiles skipping walls' problem (this is basically a very simple case of continuous collision detection).
If you allow a tiny bit of non-determinism in very rare cases, the edge case where a ball exactly hits an corner doesn't need a lot of additional work, you just repeat the intersection test iteratively until there are no more intersecting edges (99 out of 100 cases there will be only 1, and in the remaining case there will be 2, provided that your balls don't move faster than 1 unit cell distance per frame).
Some annotations of my own, all coming from memory and experience.
The theoretical basis for most collision algorithms is the separating axis theorem(SAT). It simply states that for any two convex shapes there exists an axis partitioning them - and as a consequence, deriving this axis(the algorithm of which will depend on what kinds of shapes you're working with) gives you the collision boundary of the shapes.
What SAT does not do is specify how to resolve shapes that start in an overlapping position, how to resolve turning more than one axis of movement into a _single_ axis of separation, and how to resolve overlaps of more than one shape. Those things are all where a lot of collision code goes astray. Some solutions to these problems include:
Maintain either a "lookahead" of where shapes will be in the future based on their physics parameters, or a "timeline" of previous shape positions; then the collision resolution can incorporate this information to determine direction of travel prior to the moment of collision(and thus accurately approximate pushout, bounce, etc.)
Perform collision resolution in a buffered fashion: before changing position state, create "plans" for movable objects. Test the plans in multiple passes to ensure that they satisfy all the potentially colliding shapes.
Step along the axes of movement in independent collision steps; e.g. first you test to go up, then you test to go up and right, finally you move. Stacking each axis on top of the previous in a fixed order ensures that at no point is the colliding object "squashing" one of the tests when another passes(which causes typical stuck-in-walls glitches). It causes a distortion to appear when travel is diagonal, but its impact depends on the speed of movement and whether "cutting corners" matters.
Alternately, one may test each ordering and choose a "best" one heuristically so that diagonal movement is consistent in all cases.
18 comments
[ 1.4 ms ] story [ 85.7 ms ] threadbut my point is, you don't need to check the entire world if you are using a quadtree or rtree or whatever.
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.
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.
To bounce left/right:
To bounce up/down: This representation also generalizes to 3D. You'll have a lot of trouble trying to represent a 3D heading with angles, whereas using a 3D velocity vector is straightforward. (In 3D space, using angles to represent orientation can also suffer from gimbal lock whenever you try to rotate the orientation.)If the maze is not standard but can be anything, the walls can be stored in a quadtree or some similar efficient structure.
Yes. That's why r,theta representation makes more sense computationally because reflection across a normal is just adding and subtracting two angles. Of course, you pay heavily for using only this representation on every tick() during merely linear motion, because in the end our displays are cartesian, and you'll have to convert r,theta to x,y. The solution, of course, is to maintain both representations and use whichever one is faster - a classic space-for-time trade-off.
Modern computers are monstrously fast. So fast that it's hard to imagine just how fast they are. The more time you spend thinking about optimizations before they're necessary, the more time you're not spending on implementing features.
If it's just for fun, though, go for it. A learning exercise is always nice.
The reflection R of an incident vector I hitting a wall with normal N is 2(N.I)N - I
If you have a "wall" only in one tile and not its adjacent one, that essentially creates a one-way wall, which could be an interesting effect too.
I think the only edge case here would be a ball that hits a corner dead on. You would need code that says "if a ball goes from A to B in a time step, and those are diagonal, treat it as A -> C -> B where C is one of the tiles adjacent to both A and B, for bounce checking."
The linked article is pretty thorough, but a little complex for the nature of the problem I think. What I did was just calculate all tiles (I call them 'cells') intersected by the displacement vector of the projectiles (balls) moving around the maze, which can be done in constant time if your maze dimensions are fixed. Then I look up the walls of intersected cells, and calculate the closest intersection of the displacement vector with any of these walls. This intersection happens somewhere along the vector between t=0 and t=1, so I translate the projectile position back in time using this value, change its direction (invert either x or y based on the orientation of the wall), then move it along (1 - t) * v_inverted to solve the 'fast projectiles skipping walls' problem (this is basically a very simple case of continuous collision detection).
If you allow a tiny bit of non-determinism in very rare cases, the edge case where a ball exactly hits an corner doesn't need a lot of additional work, you just repeat the intersection test iteratively until there are no more intersecting edges (99 out of 100 cases there will be only 1, and in the remaining case there will be 2, provided that your balls don't move faster than 1 unit cell distance per frame).
The theoretical basis for most collision algorithms is the separating axis theorem(SAT). It simply states that for any two convex shapes there exists an axis partitioning them - and as a consequence, deriving this axis(the algorithm of which will depend on what kinds of shapes you're working with) gives you the collision boundary of the shapes.
What SAT does not do is specify how to resolve shapes that start in an overlapping position, how to resolve turning more than one axis of movement into a _single_ axis of separation, and how to resolve overlaps of more than one shape. Those things are all where a lot of collision code goes astray. Some solutions to these problems include:
Maintain either a "lookahead" of where shapes will be in the future based on their physics parameters, or a "timeline" of previous shape positions; then the collision resolution can incorporate this information to determine direction of travel prior to the moment of collision(and thus accurately approximate pushout, bounce, etc.)
Perform collision resolution in a buffered fashion: before changing position state, create "plans" for movable objects. Test the plans in multiple passes to ensure that they satisfy all the potentially colliding shapes.
Step along the axes of movement in independent collision steps; e.g. first you test to go up, then you test to go up and right, finally you move. Stacking each axis on top of the previous in a fixed order ensures that at no point is the colliding object "squashing" one of the tests when another passes(which causes typical stuck-in-walls glitches). It causes a distortion to appear when travel is diagonal, but its impact depends on the speed of movement and whether "cutting corners" matters.
Alternately, one may test each ordering and choose a "best" one heuristically so that diagonal movement is consistent in all cases.