Zuma,Luxor ball movement!

Discussion in 'Game Development (Technical)' started by sparkyboy, Aug 19, 2005.

  1. sparkyboy

    Original Member

    Joined:
    Mar 3, 2005
    Messages:
    346
    Likes Received:
    0
    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.
     
  2. HairyTroll

    Original Member

    Joined:
    Jul 29, 2004
    Messages:
    582
    Likes Received:
    0
  3. digriz

    Original Member

    Joined:
    Mar 24, 2005
    Messages:
    532
    Likes Received:
    0
    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.
     
  4. ggambett

    Moderator Original Member Indie Author

    Joined:
    Jul 26, 2004
    Messages:
    1,982
    Likes Received:
    6
    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.
     
  5. sparkyboy

    Original Member

    Joined:
    Mar 3, 2005
    Messages:
    346
    Likes Received:
    0
    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!
     
    #5 sparkyboy, Aug 19, 2005
    Last edited: Aug 19, 2005
  6. C_Coder

    Original Member

    Joined:
    Dec 21, 2004
    Messages:
    297
    Likes Received:
    0
    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.
     
  7. sparkyboy

    Original Member

    Joined:
    Mar 3, 2005
    Messages:
    346
    Likes Received:
    0
    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! :eek:

    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
     
  8. luggage

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    2,132
    Likes Received:
    0
  9. Bmc

    Bmc New Member

    Joined:
    Dec 12, 2004
    Messages:
    1,088
    Likes Received:
    2
    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/
     
  10. C_Coder

    Original Member

    Joined:
    Dec 21, 2004
    Messages:
    297
    Likes Received:
    0
    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.

    No problem man!
     
  11. Bmc

    Bmc New Member

    Joined:
    Dec 12, 2004
    Messages:
    1,088
    Likes Received:
    2
    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.
     
  12. svero

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    3,392
    Likes Received:
    6
    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)
     
  13. sparkyboy

    Original Member

    Joined:
    Mar 3, 2005
    Messages:
    346
    Likes Received:
    0
    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.
     
  14. DGuy

    Original Member

    Joined:
    Jul 28, 2004
    Messages:
    131
    Likes Received:
    0
    From PopCap programmer who worked on Zuma:

    HTH
     
  15. James C. Smith

    Moderator Original Member

    Joined:
    Aug 21, 2004
    Messages:
    1,768
    Likes Received:
    0
    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?
     
  16. Bmc

    Bmc New Member

    Joined:
    Dec 12, 2004
    Messages:
    1,088
    Likes Received:
    2
    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.
     
  17. DGuy

    Original Member

    Joined:
    Jul 28, 2004
    Messages:
    131
    Likes Received:
    0
    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 over at the PopCap dev forums:

     
  18. Kruzoe

    Original Member

    Joined:
    Aug 3, 2005
    Messages:
    5
    Likes Received:
    0
    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.
     
  19. Jim Buck

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    1,158
    Likes Received:
    0
    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. :) )
     
  20. sparkyboy

    Original Member

    Joined:
    Mar 3, 2005
    Messages:
    346
    Likes Received:
    0
    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.
     

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer