Zuma,Luxor ball movement!

[sparkyboy]

Hi guys,
Been pondering this for a day or so, after playing all of these types of games, and think I've figured out how it's done! :)
My first thought was that the paths could be generated dynamically using COS and SIN etc, and using PIXEL COLOR collisions on the edges of the balls in order to keep them 'on track' so to speak.
Then I thought, hold on, what about our friends the ARRAY and/or STRUCTS.So here's my brief understanding of how it's done!
Each path NODE is stored in an array, and a copy of the array is assigned to each of the balls.As the ball moves, it advances back or forth through the nodes. ;)
I also believe that the in game AI would account for skipping nodes in order to increase the speed of the balls!
So guys, am I on the right track?, close but not quite?, or waaaay off target? ;)

If close enough, I would have thought the paths would be drawn with the mouse correct?, and if so, how are the paths SO SMOOTHE?

Thanks guys for any insight into this matter!!

All the best

Mark.

[HairyTroll]

Bezier Curves (http://www.moshplant.com/direct-or/bezier/)

[digriz]

Do you know, i'm sure that someone asked a similar question recently...It's worth a search.

How it's done, i assume, is by using b-splines or bezier-curves. This allows you to generate smooth curve paths. You only need to store a 0.0-1.0 value to remember your position on the spline. A calculation will give you an x, y, z co-ordinate for where you are in your world on that spline.

Sensibly you should normalise your spline, otherwise you will get speed differences going round the curves. Using a method similar to yours, i'd also look at storing evenly spaces points along the curve to help speed up the calculations. Spline maths can be processor intensive if you have a lot of objects tracking on a spline.

For the collision between balls, i'd say, use sphere-sphere or circle-circle collision detection. If you fire a ball into a queue of other balls, the math to work out how the other balls seperate will be easy enough; they are tied to a path, so they can only move in one of two directions.

I haven't written a zuma style game(too many versions already out or coming out), but that's how i'd approach it.

[ggambett]

I think you're in the "waaaay off target" category :)

Assuming you use a parametric curve (cubic beziers are a popular choice) you first need to generate equally-spaced nodes (which is not as easy as generating nodes with equally-spaced parameter values). This is called "arc length parametrization". Once you have a linear map from position in the curve (real value) to curve point in space (2D point) the merging, matching and splitting problem is reduced to a 1D problem. Except for the collisions. But colliding circles is trivial (calculate the distance between the centers and compare to the sum of the radius).

All of this works even better if you have subpixel rendering so you don't have to round the coordinates. Your ball 1D coordinates could still fall between curve nodes; in that case you can linearly interpolate the position between them. For sufficiently close nodes (which you need anyway to have a smooth curve) this would give a good approximation.

Lastly, you need the "angle" of the curve at all points. If you evaluate from the parametric representation (as opposed to using an algorithm like De Casteljau's) then the tangent vector is (x(t)dt, y(t)dt) from where you can easily (ie atan2()) get the angle.

[sparkyboy]

Thankyou very much so far guys!!Have never looked into bezier curves etc, because everything I've done in the past required just simple paths.
I agree that the collision between the sprites would be easy enough to work out, and judging by the way they interact, it seems to me to be first a 'BOUNDING BOX' test ( because it's normally fast), then if that is true, it then tests 'PIXEL PERFECT' collision and repositions the various balls that are included in the tests! :) (But that's just my 2 cents worth.)

As for making any more 'ZUMA CLONES', I agree that it's a type of gameplay that is going to appear again and again, but the mechanics of how the balls move can lend itself to many other types of games I feel! :)

Thanks again guys most enlightening.Any more theories? ;)


All the best


Mark

P.S.
Gabriel, your post came in as I was writing this!Whooah, next time could you use plain English please bud!! :p Thanks again y'all!

[C_Coder]

As for collision detection with spheres just use spherical collision detection. no need for bounding boxes or pixel-perfect detection. Also for the distance check, you do not need to do the square root for more optimization.

My 2 cents.

[sparkyboy]

Thanks C_coder.'Spherical' collisions you say......man I'm further behind than I first thought.Don't remember that type of collison for 2D years ago! :o

Anyone go any 'GOOD 'N' EASY' tutorial linkies to this type of collison that I can get my teeth into? ;)

Thanks again guys. :)

All the best

Mark.

P.S.
I'll send those screenshots for your perusal later today, when I get my freakin' email to work again.......Damn technology!!! :p

[luggage]

I just found this one that might help...

http://www.mvps.org/directx/articles/using_bounding_spheres.htm

[Bmc]

if I was to search for how to normalize a curve what would I look for, is it similar to normalizing a vector or? Math isn't one of my stronger points, but I'm curious of how to do this.

any help would be greatly appreciated

PS - I've googled it already and haven't found much usefull info/

[C_Coder]

Thanks C_coder.'Spherical' collisions you say......man I'm further behind than I first thought.Don't remember that type of collison for 2D years ago! :o

Anyone go any 'GOOD 'N' EASY' tutorial linkies to this type of collison that I can get my teeth into? ;)


Visualize two circles. Draw a line from the center to the circumference. The is the radius. Let this be 'r'.

Now you know the radius of your 'spheres' which in 2D you see them as circles. Calculate the distance between the center points of the 2 circles that you are making the collision check for. Let this be 'd'. So:

if ( d <= ( r * 2 ) ) then we have a collision.

That's it plain and simple. As for the distance you have to use pytagoras (did I write it correctly?) theorem for right-angled triangles.

Now this formula contains a square root which you can remove for optimization as follows. Let the distance without the square root calculation be 'D'. So:

if ( D <= ( ( r * 2 ) * (r * 2) ) ) then we have a collision.

There you go.


P.S.
I'll send those screenshots for your perusal later today, when I get my freakin' email to work again.......Damn technology!!! :p

No problem man!

[Bmc]

Ok, after reading ggambett's post again I guess I'm looking for "arc length parametrization"

i've done some googling and I'm getting results but it's all gobbely-gook to me. can anyone point towards an easy to understand link or spell it out for me.

[svero]

Well I can tell you more or less exactly what I did.. which may be a little different to what other people came up with.

The path itself is just a series of points. I have an editor I can draw bezier type curves with and it spits out a bunch of points. The points are just points on the curve though and not bezier anything at that point. Then when the game loads the points it cuts them up into smaller evenly separated points which are used in the game. At the same time a rotation value is assigend to each point by looking at points behind and ahead to see where something should be facing if it were travelling along the curve.

The distance of things on my line is basically pixels. That is to say.. a ball at a distance of 100 is 100 pixels along the curve more or less. Each ball on the curve has a distance parameter and nothing more to identify its position or rotation.

Then for the ball motion. Balls are added at the back of the line. The furtherst ball to the back pushes all the other balls forward.

For an arbitrary line of balls I will start at the back and iterate through the chain towards the front splitting the chain into subchains. A new subchain occurs whenever there is enough distance between two balls. I allow for small gaps but other games used hard connected chains and dont allow any gaps. The small gaps make the problem more difficult and introduce some subcases I wont discuss.

Then I iterate through the chains assigning each chain a motion. The back chain is being pushed.. but the forward chains are either collapsing or staying still depending on whether the gaps between the chains match in color. There's a few other complexities here to do with catching bonuses and reversing or pausing due to them.

For the back chain speed is the real issue. Generally you want the balls to slow down a bit as they approach the exit to keep the game tension on while still giving the player a chance to win. You can do a e^-x or 1/x type speed drop but then you also have to deal with gaps. Like how fast do balls roll in if there's a big gap in the middle? For me its mostly based on the balls being pushed but there is some element of the total number of balls on the screen and how close the player is to dying that is factored in to balance the chain a little better. I've tried several algorithms though and its hard to say which is best.

Just to be really clear.. once I've got my speed calculated I inch the furthest ball forward and then iterate from back to front moving the other balls forward based on the position of the back ball. So say the back ball is at position 0 and the diameter of a ball is 50 pixels.. Id move the back ball to position 2, and then check the next ball.. which might now be at position 50.. and shift it to 52 (ie the back balls position + the diameter.. and NOT the speed)

[sparkyboy]

Thankyou Steve, that is indeed extremely insightful (seeing as you have created a game of this genre :) )Thankyou so very much!

When you go private beta, I would be very privileged to take part in the testing process if at all possible! ;) (It will be very nice to see some real bugs and not just balls called bugs)Hehe!


Anyway, I would just like to finish with a huge THANKYOU to ALL of you that responded to my post.( and that goes for anyone else who wants to offer their expertise) ;)

May the Indie gods reign showers of gold on all of you (and me :D )

All the best


Mark.

[DGuy]

From PopCap programmer who worked on Zuma:

I used piecewise cubic curves between key points. I solved for the coefficients of the cubic curves by getting a bunch of linear equations that satisfied the following constraints:

- The end point of one curve was equal to the start point of the next curve.
- The derivative at the end point of one curve was equal to the derivative of the start point of the next curve.

As for arc length, I just stepped through the curves a little bit at a time and wrote out a point every time I had moved 1 pixel in length. At one point I had tried to accurately calculate the arc length of the cubic curves but I ran into some sort of integration problems.HTH

[James C. Smith]

From PopCap programmer who worked on Zuma:

DGuy, Thanks for passing the information along. But how about including the guy’s name. He was nice enough to share those details but you don't give him credit by name? Or did he post in anonymously?

[Bmc]

DGuy, Thanks for passing the information along. But how about including the guy’s name. He was nice enough to share those details but you don't give him credit by name? Or did he post in anonymously?

it's ace, his real name is Brian I believe. all those popcap guys are champs by my books. releasing the framework and helping out whenever they can.

[DGuy]

The programmer is Brian "Ace" Rothstein :) (had to look at the Zuma credits list as he just post as "Ace")

And here's some more from this thread (http://developer.popcap.com/viewtopic.php?t=346) over at the PopCap dev forums (developer.popcap.com/forums.php):

Yeah. So I parameterized the curves like this:

X(t) = At^3 + Bt^2 + Ct + D
Y(t) = Et^3 + Ft^2 + Gt + H

And then I had curves X1, X2, X3, X4, etc... and Y1, Y2, Y3, Y4, etc... for the different piecewise curves. Then the constraints were:

X1(0) = the first key point's x-coord
X1(1) = X2(0),
X1'(1) = X2'(0),
X1''(1) = X2''(0) (Looking back, I see that I also forced the second derivatives to be equal.)

So these translate into equations like

A1 = P1 (P1 = first key point)
A1 + B1 + C1 + D1 = D2
3A1 + 2B1 + C1 = C2
6A1 + 2B1 = 2B2

Note that on the last key point, you can't use the final two constraints since they refer to the point after. But you still need two more constraints to have the same number of equations as variables (4 per curve). So two extra constraints are that the first curve has a derivative of 0 at 0 and the last curve has a derivative of 0 at 1. These are

X1'(0) = 0
XN'(1) = 0

or

C1 = 0
3AN + 2BN + CN = 0

That gives you 4N equations and 4N unknowns which you can solve using Gauss-Jordan elimination. Do this for both the X curves and the Y curves and then you plug in the coefficients and it all works.

[Kruzoe]

Thank DGuy for passing along this information. I asked the same question in this forum not so long ago. This is very useful for me. :D

And also thank popcap for theire framework and greatly useful respone from Brian "Ace" Rothstein.

[Jim Buck]

And for anyone that ever says something along the lines of "c'mon, making a game like that would be a piece of cake", point them to this post and ask them if *they* know what Gauss-Jordan elimination even is. :) (Of course, I'm referring to family members, friends, etc that have no idea what it takes to make a game but think it's not "real" work. :) )

[sparkyboy]

The programmer is Brian "Ace" Rothstein :) (had to look at the Zuma credits list as he just post as "Ace")

And here's some more from this thread (http://developer.popcap.com/viewtopic.php?t=346) over at the PopCap dev forums (developer.popcap.com/forums.php):

That is indeed an interesting read........tho' it may as well be in Chinese for me!! :D However, here's a nice site I found the other day that can help with mathematics!

http://www.teacherschoice.com.au/


All the best


Mark.

[mooktown]

source code (http://mooktown.blogspot.com/2007/08/source-code-for-zuma-paths.html) for zuma paths! :cool:

moved to its own thread (http://forums.indiegamer.com/showthread.php?t=11516)