Many questions: Arkanoid Ball physics

Game Mechanics
#1

im programming a clone of arkanoid/breakout. my biggest problems are collision detection and the movement of the ball.

up to now im handling the movement like this:

for a clean collision detection the ball movement is calculated several times a frame (+collision detection) and then drawed. so if the ball has a speed of 5, his way is calculated 5 times and then drawed to the screen.
with this technique he flies fast enough for the human eye but is calculated exactly and doesnt jum in 5 pixel steps.

but i dont think, it is the best way to move him.
im doing it this way because of the following problem :

if i would only calculate, where the ball has to be drawn next frame and he is very fast (e.g. x+=7, y+=7) then it could be that he “jumps” over an object with which he should collide. so i try in my method to calculate every step in between.

now my second big problem:
i find it very easy to handle if i command the direction of the ball by passing him an angle as parameter, so i wrote this movement calculating routine :


dir_x =  Math.cos(alpha*(Math.PI/180));
dir_y =  Math.sin(alpha*(Math.PI/180));
....

ball.pos_x+=dir_x ...
ball.pos_y+=dir_y ...

alpha is my angle parameter, dir-vars are double

for my method of movement i have to be sure that this formula calculates a line-path without gaps (so that the ball wont jump)

i have many further questions, but i want to know, if my way could be improved =)

#2

The method you described is probably the easiest way to do it, and should work just fine.

There are other ways, but they are more complicated. You could “draw” a line between the balls movement endpoints. This would make sure you check all pixels, and you can find out where on the pixels the ball enters/exits.

Although a bit overkill, you could also do collision detection between sircles and lines as described in this article: http://www.gamedev.net/reference/articles/article1026.asp

#3

Rather than wasting calculations with extra-fine steps, or drawing a line (same thing)… Why not just “do the math”?
The ball moves in a straight line. The blocks are rectangular. Solve for the intersection of the line segments involved… That means the line form the last ball position to the new position and the lines that make up the boundary of blocks.

You don’t have to test for every block since you can use some heuristics to eliminate blocks that are obviously too far away from the action, or “behind” other blocks relative to the balls movement.

#4

Last time I did one of these, I used raycasting through a grid of block-positions to establish which blocks might have been hit (for N maximum blocks per level, typically reduces it to root-N possible hits). NB> this works because arkanoid/breakout games normally arrange their blocks in a perfectly tesselated rectangular grid of positions. I haven’t yet seen a clone where the blocks could be at arbitrary alignments - and hence not tesselate. I suspect the main reason is that simple algos like this no longer work in such situations :).

It also gives you the block-locations in the exact order you will pass through them (and hit a block, if there is a block at that location), so you just go along the list of “possible hits” and check “is there actually a block here?”.

The amusing thing of course is that the fastest way to do this raycasting is to use line-drawing algorithms - but to be drawing “block locations” instead of pixels. So we come full-circle ;D

#5

This will also fail if there are “power-ups” that change the ball trajectory - like a magnet or gravity, so that it follows an arc for instance.

Now that I think about it, it probably is easiest to plot the entire line of the balls path from one frame to the next and just deal with collisions on a pixel co-ordinate basis. (still using a bounding box for a block, no actual pixel collisions).

#6

[quote]This will also fail if there are “power-ups” that change the ball trajectory - like a magnet or gravity, so that it follows an arc for instance.

Now that I think about it, it probably is easiest to plot the entire line of the balls path from one frame to the next and just deal with collisions on a pixel co-ordinate basis. (still using a bounding box for a block, no actual pixel collisions).
[/quote]
True, but surely you can stick with simple curves (like quadratics) at least until you want multiple simultaneous gravity sources etc?

Once you go beyond the standard arkanoid/breakout design (which didn’t do variable gravity, although straight-line random changes of direction and speed were allowed IIRC?) you can do most things you’d want to in vector-maths, which has all sorts of miscellaneous advantages (assuming that if you’ve already got this complex then you probably want to go even further… :)).

E.g. you can trivially render your projected-movement arcs to screen, giving a kind of training mode (and I’m sure someone can think of some more interesting uses for it).

Incidentally, inspired by this thread, I sketched a design for a circular breakout clone, provisionally entitled “The Well” (because it’s got a well in the middle, and the aim is break down the intervening bricks and then knock your opponent’s ball down the well). Hopefully I can actually write a prototype over the coming days whilst sitting here watching our game doing it’s self-testing runs (it’s MMOG, and we’re doing semi-automated testing to exercise all the features; every 10-30 minutes it needs developer intervention, but otherwise you’re just sitting there watching it…this explains why I’ve had so much time to post recently :))

#7

hmmmm, this topic is a little confusing so i try to sum up.
first of all i should replace my tactic by replacing my pixel per pixel moving by using only vector math and vector intersection points …

so far, but than i have to refresh a little math =) and to understand, how i can really implement this.

@blah…:
i would be very happy to get some code from you

btw:
my arkanoid level creator allows it to place the blocks wherever you want ;D

#8

[quote]hmmmm, this topic is a little confusing so i try to sum up.
first of all i should replace my tactic by replacing my pixel per pixel moving by using only vector math and vector intersection points …
[/quote]
…don’t take that as read. I haven’t looked deeply into a vector-based implementation, I’m waiting to see what swp has to say :).

Personally, I’d first of all go with the raycasting approach. It’s fast, it’s simple, and it’s clever. I’m pretty sure it’s how the majority of BO games worked (until recent years when you had so much spare CPU power you could afford to be lazy :)).

It’ll get you as far as implementing a game with everything “normal” in it. When you want to add attractors/repulsors and “curved shots” etc, then you could come back to this thread and think about the vector maths.

Or, if you know you want the curving shots in from the start, or very soon after the start, then I’d suggest using an implementation based on vector maths (not raycasting) to get simple version working, and by the time you want to add curves you should find the changes necessary to your code are not too great.

But I really wouldn’t recommend this unless you’ve done a couple of small games before - getting your first/2nd/3rd game working, working fast, and fun to play is hard enough…trying to invent a new game with curved balls and work out how to make that “fun” is going to be a real big challenge in itself (correct me if I’m wrong, but there aren’t any BO games where you have curved shots? So you’ll have few (if any) examples of what makes them fun to help you make sure yours is fun…)

are they all axis-aligned though? I.e. all in the same orientation, no rotation allowed? If so, I’d seriously consider making them only placeable on a grid (that can cover the whole gaming area) so that you can use the simple raycasting algo.

#9

[quote]I’m waiting to see what swp has to say :).
[/quote]
Oh, I guess I should speak up then… or else you will be waiting for quite a long time.

It is true that you could start using more advanced math for curves etc… but I think you don’t get that much for the added complexity in the maths.

If you think of how trivial it is to update the ball coordinates, even when the ball is moving very fast you can calculate all of the positions at pixel size steps between frames. I would just use a distance calculation at each position of the ball… if the distance from the center of the ball to the nearest edge line is less than the ball’s radius then count the hit on that edge.
If you wanted you could make a fancy edge list that was appropriately sorted so that you can easily short circuit your collision checking loop.
This will make things like gravity and magnets, steering power-ups, etc. all work without needed to update the collision routine as teh ball trajectory becomes more complex.
With a good data structure for your block positions, arbitrary placement shouldn’t be a problem either. I would go with maybe 4 lists…

  • Bottom edges sorted bottom to top
  • Top edges sorted top to bottom
  • Left edges sorted left to right
  • Right edges sorted right to left

Maintain a position or iterator in each list based on the current ball position, checking for collisions as you update the position of these iterators. You will know which block you hit by comparing the distance to the edges in the list that are around the iterator and within one ball radius. Just remember that if you are one ball radius or less away from the edge at the iterator, you must still check the next edge until you hit an edge that is farther than one ball radius from the current balls position.
Multiple balls mean multiple iterators in the edge lists.
You would have to use your own custom list structures and iterators likely.
Because you are only checking against edges near the ball you have much less checks than there are blocks and can often stop checking after only one edge if the first edge at the iterator position is already too far away.

Blah, you could use a similar technique but based on a polar co-ordinate system for your ‘Well’… have rings of different radius for each level of brick, and another list of sectors based on angle or something.

Dang, now I want to write a breakout game :wink:

#10

An excellent suggestion. I was thinking of having arbitrary orientations, shapes, and sizes, just for the hell of it…but that’s pretty stupid because I don’t have much time.

:). It’s infectious.

#11

ok, many aspects, i have to bring my brain in movement (hard day and its night in germany =)

your suggestions are focusing on making a faster and more effective collision detection. i alredy thought about using a quad-tree with sectors etc.
an important thing about my arkanoid is, that i dont want only to create a smooth arkanoid (who needs another one ?)
but to learn the main techniques about 2d-game programming. so i dont want to fit the code in all manors to the arkanoid topic, rather to build a little engine.

therefore i had(?!) elemental questions about how a 2d-sprite should be moved. main idea was, that if i use vector math with “pre-collision-detection” (getting the intersection of vector-rays widly before the collision is happing) i can save a lot of calculating time.

so, with your agreement, i can my method of moving my sprites pixel per pixel but improve my collision detection.

but ! dont think that my problems are gonna end.

next problem i hoped to solve with vector math:

i have a little formula for the collision reaction of my ball of it hits a block or the paddel:
i need to know where exactly the ball hit the block so that i can change his angle in relation to this point, eg.: it hits the mid of the paddle it is going to reflect 0°, but if it hits the right side-corner, it reflcets with perhaps 50°

but there is a problem with my bounding-boxes. they are rather usable for a boolean result of collision.

so im very ashamed about my very first solution (which hasnt changed yet =)
the ball isnt a real box, it is a circle of 8 hotspots arranged to a circular form. so if one of these spots collides with the edge of a block, i can exactly determine, where it collided.

this is a terrible solution with many collision problems and furthermore it needs 8times of detection … =(

#12

[quote]main idea was, that if i use vector math with “pre-collision-detection” (getting the intersection of vector-rays widly before the collision is happing) i can save a lot of calculating time.

so, with your agreement, i can my method of moving my sprites pixel per pixel but improve my collision detection.
[/quote]
Actually I reversed my earlier idea to do all that vector math because I came to the conclusion that it didn’t help much at all. You still have to animate the ball along the path before it ever gets to the collision, so solving for the collision point like that might not be worth much.

Since you must step the ball along a path anyway, for animation, you can just as easily use the animation stepping as your collision detection by checking when the ball will pass boundaries as a result of stepping. I suggested that such checks would be very quick so it wouldn’t do any harm to do them every step of animation. The end result could be a more robust solution as it might be easier to adapt to different environments… e.g. moving blocks or something.

[quote]the ball isnt a real box, it is a circle of 8 hotspots arranged to a circular form. so if one of these spots collides with the edge of a block, i can exactly determine, where it collided.

this is a terrible solution with many collision problems and furthermore it needs 8times of detection … =(
[/quote]
8 hot spots don’t work either - I think - It sounds like you are assuming that the ball will only travel on angles that are multiples of 45 degrees. The solution can be simplified to check the distance from the point of the ball to the edge of a block and see if it is less than the ball radius. Since block edges are aligned with the coordinate system, this is really easy.

This general solution can work for other styles of 2D game… for instance where the object that might collide can move freely. You can do the simple check you thought of earlier - the bounding box collision, then do more accurate collision detection when the boxes are colliding.

#13

ok, i can calculate the distance of the ball point to the edge of a block. but do i have then automatically the exact point of collision (necessary for calculating my reflection) ? hmmm …

another suggetion from me:

both of you helped me a lot, but perhaps it would be more effective if you could see the applet and the source.
unfortunately my only web account doesnt permit applets.
so i can upload full scource (html / zip) or i could send it to you.

only if you guys are interested in some extra work … =))

#14

[quote]ok, i can calculate the distance of the ball point to the edge of a block. but do i have then automatically the exact point of collision (necessary for calculating my reflection) ? hmmm …
[/quote]
I think you do, at least as good as can be expected. There will be some amount of penetration of the ball into the block. But basically you will solve for the intersection of the line that is perpendicular to the block edge that goes through the center of the ball. This is the same line that you will measure along to get the distance to the block… so you can likely get everything you need out of the intersection test calculations, maybe with only a few more operations after you know there is a hit.

These calculations are super easy because the block edges are aligned to the coordinate system. the distance is always a simple subtraction of x or y coordinates depending on if you are checking against a vertical or horizontal line. The point of intersection is then always, one coordinate from the block edge and the other coordinate from the ball OR the endpoint of the edge line segment, if the hit is close to the block corner.

You can post your code anyway… if I have time great, if not, maybe someone else will.

#15

so, i have uploaded a zip with the source.

my fh-admin told us, that the server will be down tomorrow
friday in the time from 7.00am - to 7.00 pm

http://zeus.fh-brandenburg.de/~huellein/download.htm

#16

no one loves me …

sorry, but im impatient: is anyone looking at the code ?!

#17

Haven’t really had the time :frowning:

#18

Surely some mistake? Line perpendicular to the block edge is irrellevant…

#19

Yes, I think I got that messed up. I was thinking that where that line intersects the edge of the block could be a reasonable estimation of the collision point, but obviously the line from the ball’s last position to it’s current position is more correct.

I was thinking about the line that divides the ‘reflected’ (deflected?) path and the incoming path, oops. That line is still perpendicular to the block edge - except in the special case of colliding with a block corner which will hit the ball such that the point of impact of the ball and corner and the balls center do not fall on an axis-aligned line. Nor does it fall on a line perpendicular to a block edge. But if you use the line between the corner and the balls center as the line of reflection I think you will end up with a more realistic bounce off of the corners.

#20

A longtime ago, in a galaxy far far away…errrr wrong thread ;D
Anyways, I coded a VERY simple version of breakout months ago that anyone is welcome to try here.
The way I managed to detect collisions will definitely have the Math/Physic gurus endlessly cussing at me :stuck_out_tongue:
Come to think about it, I might as well redo the whole code now that I can perform fast per-pixel collision detection as well as realistic reactions (S -= 2NDot(N,S))

WARNING LAME CODE COMING
…