Making Balls Bounce off of Walls in a Labyrinth

http://ssodelta.wordpress.com/2014/06/17/balls-bounce-labyrinth/

by lettergram • 12 years ago

27 18 12 years ago

ssodelta.wordpress.com

joshu2• 12 years ago

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.

sillysaurus34• 12 years ago

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.

joshu2• 12 years ago

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.

userbinator2• 12 years ago

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.

sillysaurus34• 12 years ago

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.)

javajosh2• 12 years ago

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.

jerguismi• 12 years ago

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.

spuz• 12 years ago

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.

IanCal• 12 years ago

Really? I'd have thought using vectors would be much simpler.

The reflection R of an incident vector I hitting a wall with normal N is 2(N.I)N - I

userbinator2• 12 years ago

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.

lacker• 12 years ago

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."

w0utert• 12 years ago

This is exactly how I implemented almost the exact same thing in the iOS clone of a classic DOS game (Snipes!) I made (shameless plug: https://itunes.apple.com/nl/app/snipes!/id428845764?mt=8)

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).

chipsy• 12 years ago

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.

joshvm• 12 years ago

There are still some bugs in the final output - I saw a ball bouncing between two tiles a few times.

frownie• 12 years ago

Given enough time, can a ball bounce out of the labyrinth ? Obvously, not always. So, in which condition can this happen ?

Making Balls Bounce off of Walls in a Labyrinth

Related Stories