FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Sprite design issues...

 
Post new topic   Reply to topic     Forum Index -> ArcLib
View previous topic :: View next topic  
Author Message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Thu Sep 07, 2006 4:56 pm    Post subject: Sprite design issues... Reply with quote

Here are the issues I am trying to think about for Sprite's collision detection design.

----
First off I will get rid of the per pixel collision code because it is
1) Limiting to the user (Collision gaps must be defined), slow to load it up
2) Does not lend itself well to a physics system (polygons do)
3) Infected with LGPL
----

-----
I want to implement Polygon collision in its place. However, polygon collision has these problems...

1) Concave polygons don't lend themselves well to collision, so I will triangulate all polygons into a series of triangles, this creates a lot of points, all which must be rotated for the polygon. Triangulation also allows for 'doughnut shaped polygons'

2) Efficient polygons must be user defined, however computer defined is possible.

-----

So, overall polygon collision will require more computation time for 'rotating' these points once every frame at max.

Now, my other problems...
1) Box and Circle collisions are nice but they do complicate my sprite class which leads to less maintainable code. I could

A) Remove Box and Circle and only allow for Polygons, with options of auto-generating boxes and circles

B) Keep Box's and Circles, and when I collide a polygon against a circle, first quickly autogenerate a circle polygon shape and then use poly-poly collision detection methods.

B will be more expensive when I collide circles with polygons, but A will be more expensive because keeping track of points is harder than keeping track of rotated circles.

I really would like to simplify my sprite class and I am tempted to only allow polygon collision outlining, but I also want the speed of box and circle collisions.

The main tradeoffs would be

Simplicity and Maintainability of Code (polygon) vs Flexibility and Speed (poly + box + rad).

In addition, only allowing polygons will greatly simplify a future physics system implementation.

I cannot decide...
Back to top
View user's profile Send private message AIM Address
Phr00t



Joined: 03 Mar 2006
Posts: 203

PostPosted: Fri Sep 08, 2006 9:19 am    Post subject: Reply with quote

I'd go for simplifying your code. This means you will have less bugs and more efficient code. If you can make me polygon collisions that operate at about the same speed as box / circle collisions, why do we need support for box / circle collisions? In addition, simplifying your code will allow you to better actually finish the code. Smile

You could just remove that COLLISION_TYPE enum (box, circle, pixel etc.) and have a detail variable. Like 1 - 10. 1 will make very simple polygons that match speeds of circles / boxes, 10 will make insane polygons.

On another note -- what about creating collisions with "invisible" sprites? Like if I wanted an empty sprite of size 100x100 to collide with a sprite with a graphic?

- jeremy
Back to top
View user's profile Send private message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Fri Sep 08, 2006 12:25 pm    Post subject: Reply with quote

Simplicity it is then Very Happy

I do not quite understand your question...

If you are saying, how to collide a transparent sprite of size 100-100 with another graphic, you will have multiple options...

1) Autogenerate box or cirlce polygon
2) User define polygon

Also, a polygon will be stored for each frame of the sprite, to allow for different polygon outlines for different frames. This is a tradeoff to allow more flexibility for more memory.
Back to top
View user's profile Send private message AIM Address
pragma



Joined: 28 May 2004
Posts: 607
Location: Washington, DC

PostPosted: Fri Sep 08, 2006 2:26 pm    Post subject: Re: Sprite design issues... Reply with quote

clayasaurus wrote:

B) Keep Box's and Circles, and when I collide a polygon against a circle, first quickly autogenerate a circle polygon shape and then use poly-poly collision detection methods.

B will be more expensive when I collide circles with polygons, but A will be more expensive because keeping track of points is harder than keeping track of rotated circles.


Honestly, I'd stick to supporting box and circle collision detection. You're not likely to need much more than that.

AFAIK, in game programming, these are the two that are used most frequently for 2D gaming, and they're almost never used in a mixed mode like you suggest. It's usually one or the other. You could impose this in your library by saying that collisions only occurr between like boundary types - then leave it up to someone else with more free time to improve matters. Wink

At worst, you support mixing box and circle style "bounding boxes", and deal with only three possible collision types:

1) box vs box (easy!)
2) circle vs circle (easier)
3) circle vs box (???)

How to solve #3:

First take the degenerate case: two circles. Intersection is determined by the distance between the two center points, minus the two radii. If you get a number less than zero, they intersect.

Now a box is a very cartesian animal. Luckly, there's a way to get a 'radius' out of it, but it's not trivial. However, it's easier if you switch coordinate systems first.

If you convert the bounding box from a cartesian to a polar equation, then you can treat it like a circle/ellipse with a non-constant radius: that is, the radius is computed by a function of theta. Theta, in turn, is determined as the angle between the center of the box and circle on the cartesian plane.

The hard part is that there is no single equation (that I'm aware of) that defines a rectangle in polar coordinates. Instead, I'd reccomend finding a way to break down a rectangle into four arcs (corner to corner) and use a polar line equation along each arc, to make up each side.

For example, a square will have four 90-degree arcs for it's sides. For rectangles, you'll have to calculate how wide the arcs are for the small and large sides.

(in case you're wondering, provided your box rotates about it's center, rotation can be handled by adding/sutracting the amount of rotation to theta in your function for the above)

As long as you can plug theta in, and get r out, you've succeeded. You can take that formula, apply it to any box, and use it to bounds-check against any circle. You'll also find that ellipsoidal intersections (again, non-constant radii) can also become an extension of this method.

Polar Coordinate Resources (if you don't have 'em already):
http://www.ping.be/~ping1339/polar.htm (<-- polar line equation here)
http://archives.math.utk.edu/visual.calculus/0/polar.6/index.html

Edit

What the heck, I went ahead and rolled some equations for ya. To the best of my knowledge, these are correct.

Given a rectangle with a center (Xc,Yc) and a corner (Xn,Yn).
Code:

double y = Yn - Yc
double x = Xn - Xc

Keep X and Y at all times, and recalculate if the rectangle changes shape.

Calculate an angle, Beta, that we use to determine our four arcs for the radius function:
Code:

double beta = tan(y/x);


Last we'll need theta, the angle between the centerpoints of our two bodies. Those are located at Xc,Yc (this object) and Xa,Ya (other object).

Code:

double theta = tan((Yc-Ya)/(Xc-Xa));


Now comes the radius function. We'll do this by testing four ranges against theta, one for each arc. Each arc uses a different variation of the polar line function to yield a 'radius' for he angle theta.
Code:

double rectRadius(double theta, double x, double y){
   if(theta >= -beta && < beta) return x / cos(theta);
   if(theta >= beta && < pi - beta) return y / cos(theta-pi/2);
   if(theta >= pi - beta && < pi + beta) return x / cos(theta-pi);
   /*if(theta >= pi + beta && < (2*pi) - beta)  */
   return y / cos(theta - ((3*pi)/2));
}


And there you have it. These ranges correspond to the right, bottom, left and top sides of the rectangle, respectively. This also assumes that 0 radians points to the right, and pi/2 radians is down.
_________________
-- !Eric.t.Anderton at gmail
Back to top
View user's profile Send private message Yahoo Messenger
Phr00t



Joined: 03 Mar 2006
Posts: 203

PostPosted: Fri Sep 08, 2006 9:38 pm    Post subject: Reply with quote

Woah, go pragma! Smile

I know we don't /need/ more than box / circle collisions... but if they could be replaced with one collision system that could be flexible and fast, I'd rather take that route. I have some large sprites in my FreeUniverse game (e.g. space stations) and circle collisions with these isn't ideal... If clay has some cool auto-polygon-generating code -- cool! This might make it easier for him to integrate physics stuff later...

For the 100x100 box thing -- if I created that sprite, and it was just empty, the auto-polygon-collision-generator wouldn't make any polygons for it, correct? So I'd have to manually create one?

If I'm not mistaken, clay already has box vs. circle etc. collisions working in ArcGames :-\
Back to top
View user's profile Send private message
JoeCoder



Joined: 29 Oct 2005
Posts: 294

PostPosted: Sat Sep 09, 2006 8:58 am    Post subject: Reply with quote

Also, some people might want to make indoor environments. It would be quite limiting if every wall / object had to be made of squares and circles.
Back to top
View user's profile Send private message
Logwad



Joined: 27 Dec 2004
Posts: 18

PostPosted: Sat Sep 09, 2006 8:43 pm    Post subject: Reply with quote

While I have little experiance with CD, I would say from a practical standpoint that having good maintainable code is wisest for a "immature" project.

Plus to me, it seems that polygons are more flexible for game design, even if they may take a little more work on the game coders part.



Is there no good way to be able to set up the library, so you can leave room for both kinds of CD? What I mean is, design the library to let the coder choose which kind of CD would be suit him? Not to say you would have to work on both at the same time, but then you could focus on one kind, and save the other kind for later, or let someone else do it.
_________________
BZFlag.

You know you want to.
Back to top
View user's profile Send private message
JoeCoder



Joined: 29 Oct 2005
Posts: 294

PostPosted: Sat Sep 09, 2006 9:01 pm    Post subject: Reply with quote

Maybe I've oversimplified things in my mind, but what about this?

Write a line intersection function that takes two lines as arguments. Each line is defined by a start and end point. The function returns true if there's an intersection and false otherwise. Next, check every line in polygon A against every line in polygon B for collision, stopping if collision is found.

A second instance of collision would be when one object is completely inside another object. For this case, choose an arbitrary vertex of polygon A and use it against the point-inside-a-polygon algorithm. Repeat with a vertex of B checking inside of A.

This should work the same for both convex, concave, and "donut" polygons as long as all vertices are defined in the proper order. Let me know if I've missed something totally obvious with this aproach. Bounce-back physics may still be difficult.
Back to top
View user's profile Send private message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Sun Sep 10, 2006 7:58 am    Post subject: Reply with quote

JoeCoder - I may try your polygon collision approach as it would save me a lot of vertices.

Logwad - Maybe... but I'd rather either implement it or not.

Phr00t - Yes, but I could have the autogenerator check for this case and generate a box

pragma - whoa that's pretty cool. I already contrived my own method for circle/box collisions, maybe I should speed test the two against eachother.. hrm.

----------------------------------

I think I'll only do poly-poly for simplicity but I will keep my algorithms for circle-box,box-box,and box-circle in a handy place in my lib.
Back to top
View user's profile Send private message AIM Address
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Mon Sep 11, 2006 5:36 am    Post subject: Reply with quote

About simplifying the sprite class: perhaps it's an idea to factor out the sprite components that involve collision detection to a seperate or embedded 'hull' type? Sprite already involves animation and sound too, so this might make it somewhat clearer and more flexible by keeping Sprite more focused.
Back to top
View user's profile Send private message
Phr00t



Joined: 03 Mar 2006
Posts: 203

PostPosted: Mon Sep 11, 2006 8:39 am    Post subject: Reply with quote

Lutger -- the side-effect of doing that is more programming complexity. I, the programmer, would then have to manage hull and sprite objects for every on-screen graphic that I want performing collision detection...

I think things like graphics / sounds / animation / collision are all things people will want to do with a sprite, so it makes sense to have it packaged up -- good to go!
Back to top
View user's profile Send private message
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Mon Sep 11, 2006 9:37 am    Post subject: Reply with quote

Phr00t wrote:
Lutger -- the side-effect of doing that is more programming complexity. I, the programmer, would then have to manage hull and sprite objects for every on-screen graphic that I want performing collision detection...

I think things like graphics / sounds / animation / collision are all things people will want to do with a sprite, so it makes sense to have it packaged up -- good to go!


I didn't mean that it would be up to the programmer to manage sprite and hulls, it's just that if you're not careful, the sprite will become too bloated. It's just a minor reorganization, I had something in mind where you could do things like this:

sprite1.hull.collide(sprite2.hull);

Then you could let the hull be constructed by the sprite, and you could swap in a different hull type as needed. It would also be easier to extend collision detection to other types than sprites (in fact there is no work needed).
Back to top
View user's profile Send private message
Phr00t



Joined: 03 Mar 2006
Posts: 203

PostPosted: Mon Sep 11, 2006 10:58 am    Post subject: Reply with quote

Hrm, that doesn't sound too bad then Very Happy I don't know if it is worth the reorganizing now? Clay will figure it out...
Back to top
View user's profile Send private message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Tue Sep 19, 2006 5:42 pm    Post subject: Reply with quote

More sprite design issues... I want a single way to define polygon outlines for a sprite (besides the game designer programatically doing it himself).

1) Should there be algorithm to automatically generate polygon outline for each frame?

This algorithm will not be terribly easy and will be expensive (like determining if the pixel is part of the hole or the outline, or what to do with single pixels?) I'm not sure this is the best approach...

2) User custom designs collision outline for each frame, using a 'sprite editor'

People can better design sprite collision outlines per frame than computers can, this seems to be a good option but it will take some time on the designers part.

To make things easier, I'll give the person a 'sprite editor' and allow the sprite to be saved and then loaded through an XML file, and XML file loading is a lot quicker than scanning each pixel of an image when loading. Using this I would have no real excuse to use SDL_image and could switch to use the developers image library so i can save PNG's.

3) Computer-generated patterns

Use the computer to generate Circles, Boxes, Ring shapes, etc. IMO this isn't much better than BOX and CIRCLE collision types and is a waste of computer memory if the polygon outline is just 'approximate,' I could use other algorithms for approximations...

I'm leaning towards number 2 but just posting this here to see what others think.
Back to top
View user's profile Send private message AIM Address
sonicbhoc



Joined: 05 Sep 2006
Posts: 11

PostPosted: Wed Sep 20, 2006 9:09 am    Post subject: Reply with quote

I'll put a vote in for choice number two. It'll take longer but it is way better than choices 1 and 3.
Back to top
View user's profile Send private message Send e-mail Yahoo Messenger MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> ArcLib All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group