Jump to content
  • Advertisement
Sign in to follow this  
Splinter of Chaos

One list to hold every sprite on screen, or many lists?

This topic is 3610 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

OK, I'm managing all my sprites in one C++ STL list and I started doing collision detection. Before, it hasn't been all that bad because all of my objects were circles. Now, I've got circles, triangles, and squares, oh my! It would actually be more convenient to have my objects in separate lists so I could say... for everything in the bullets list ...for everything in the bubbles list ......Circle and triangle collision? Collide. ...For everything in the ship list ......Square and triangle collision? Collide. Instead, I have to do one dynamic cast per bullet on screen plus the number of items checked against times the number of bullets. On the other hand, I only have to iterate down one list to move objects and draw them. If I make many lists, every time I add a type of sprite with a new type of collision, I'll have to add that list to the move, draw, and collision detection iterations. I feel like the simple answer is in front of me and flashing me its obviousness, yet somehow eluding me. Is it? I'll accept keywords to google for answers. This seems like something I won't have been one of the first million to deal with. It's just that google searches of "collision detection" reveled, mostly, solutions for worlds of polygons only, not mixed worlds.

Share this post


Link to post
Share on other sites
Advertisement
It sounds like a good solution to your problem is to have one list and then do double dispatch.

Say you have three kinds of shape: T for triangle, C for circle and B for box.


public interface Visitable {
public void accept(Visitable shape);
}

public interface Visitor {
public void visit(T shape);
public void visit(C shape);
public void visit(B shape);
}

public class T implements Visitable, Visitor {
public void visit(T shape) { /* triangle-triangle collision test */ }
public void visit(C shape) { /* triangle-circle collision test */ }
public void visit(B shape) { /* triangle-box collision test */ }
public void accept(Visitor shape) { shape.visit(this); }
}

// and so on for class C and B.

for(Shape a: shapes) for(Shape b: shapes) {
a.accept(b); b.accept(a);
}



You probably want to do something smarter at some point than the n^2 loop at the bottom, but that's an unrelated problem.

Share this post


Link to post
Share on other sites
Quote:

On the other hand, I only have to iterate down one list to move objects and draw them. If I make many lists, every time I add a type of sprite with a new type of collision, I'll have to add that list to the move, draw, and collision detection iterations.


This is not necessarily true. You could have separate lists for move and draw which would be independent of the collision lists.

Share this post


Link to post
Share on other sites
Ahnfelt: I can see how this would help me in Java, where it looks like Java keeps a better track of what a variable's type is, but I still feel that C++ would require I do the same number of dyn_casts. Maybe I'm just missing it.

Barius: Interesting idea. Then, I'd have to add the object to its respective list and take it off when it's done... Might be closer to what I feel like doing.

Share this post


Link to post
Share on other sites
Oh, it's exactly the same in C++. Every object oriented language supports the visitor pattern. You're only relying on standard object oriented single dispatch (that is, when you call a method on an expression of static type A, if the runtype type of the expression is a subtype B, B's version of the method will be invoked, not A's). And overloading, but that's not strictly required, nor is it absent from C++, so no worries.

There are no need for any "instanceof" or casts (I tend to avoid that like the plauge). You can translate the Java example directly to C++. No new code will have to be added (see the example below).

The "magic" happens in the accept method. The code above exploits that you always know the exact type of "this" within a method, which guarentees that the right overload will be called. But it can be written equally well without overloading (although there is no reason for this in C++):


class Triangle: Visitable, Visitor
{
public:
void visitTriangle(Triangle& shape) { }
void visitCircle(Circle& shape) { }
void visitBox(Box& shape) { }
void accept(Visitor& shape) { shape.visitTriangle(*this); }
}


[Edited by - Ahnfelt on August 2, 2008 11:40:35 AM]

Share this post


Link to post
Share on other sites
just use inheritance.. ie


class shape
{
... basic stuff...
}

class circle : public shape
{
... circle stuff ...
}

std::list<shape *> shapes;




that way you can hold all your shapes in one container. You can go even futher and make two seperate list for collidables and non collidables. and you really should have different types of collisions for every object, but instead look into basic onvex polygon collision.

if you're doing this in 2D you can download Box2D form box2d.org and look through cattos source to see how he deals with circles and convex polygons.

Share this post


Link to post
Share on other sites
class world:
layers = []

class spritelayer:
sprites = []

class sprite:


world contains
__a list of spritelayers that contais
____a list of the sprites

spritelayers are have lists of sprites that use the same texture, this improves the performance by reducing the texture changes

Share this post


Link to post
Share on other sites
Quote:
Original post by arthurprs
*** Source Snippet Removed ***

world contains
__a list of spritelayers that contais
____a list of the sprites

spritelayers are have lists of sprites that use the same texture, this improves the performance by reducing the texture changes


Doesn't that go back to one of my original statements about adding a new type? How I don't want to have to update every loop that iterates through the array?

Although, in actuality, I'd use a list and overload the '<' and '>' operators and sort it. (The advantage of using a list being that the data doesn't have to keep getting transfered everywhere. Just update pointers.) Still, I don't see how that doesn't stop me from having to use a dyn_cast every iteration in the for loop.
Quote:
Original post by freeworld
just use inheritance.. ie

*** Source Snippet Removed ***
and you really should have different types of collisions for every object, but instead look into basic onvex polygon collision.


Did you mean convex polygon collision? A little more complicated than what I need, and a circle, which over half the objects I'm working with are, is not a polygon.

PS: Yeah, I get what you mean about inheritance. I've had a system that might work in my head for several days, but it still doesn't mean I wouldn't be using dyn_casts.

Share this post


Link to post
Share on other sites
for a large variety of collision shapes :

- visitor pattern.
- collision shape table and manual RTTI.

The first solution can be a pain with the dependencies and the extra junk you have to provide every time you add a new type.

I like both, the second solution is quite elegant too.


namespace Collision
{
enum
{
TYPE_NOT_SET=-1,
//-----------------------
TYPE_POINT,
//TYPE_SEGMENT,
TYPE_SPHERE,
TYPE_TRIANGLE,
//TYPE_RECTANGLE,
//TYPE_OBB,
//TYPE_POLYGON,
//TYPE_POLYLINE,
//-----------------------
TYPE_COUNT,
};


struct Shape
{
Shape(int typeId) : m_typeId(typeId) {}
const int m_typeId;
};

struct Sphere: public Shape
{
Sphere() : m_typeId(TYPE_SPHERE) {}
};

struct Triangle: public Shape
{
Triangle() : m_typeId(TYPE_TRIANGLE) {}
};


struct Table
{
typedef bool (*collideFunc)(Shape* a, Shape* b) CollisionFunc;

static bool collide(Shape* a, Shape* b);
static bool collidePointSphere(Point* a, Sphere* b);
static bool collidePointTriangle(Point* a, Triangle* b);
static bool collideSphereSphere(Sphere* a, Sphere* b);
static bool collideSphereTriangle(Sphere* a, Triangle* b);
static bool collideTriangleTriangle(Triangle* a, Triangle* b);
};


bool Table::collide(Shape* a, Shape* b)
{
static CollisionFunc s_collisionFunctionTable[TYPE_COUNT][TYPE_COUNT] =
{
// TYPE_POINT
{
NULL,
collidePointSphere,
collidePointTriangle,
},

// TYPE_SPHERE
{
NULL,
collideSphereSphere,
collideSphereTriangle,
},


// TYPE_TRIANGLE
{
NULL,
NULL,
collideTriangleTriangle,
},
};

if(a == NULL || b == NULL) return false;
if(a->type() < 0 || b->type() < 0) return false;
if(a->type() >= TYPE_COUNT || b->type() >= TYPE_COUNT) return false;

CollisionFunc func = s_collisionFunctionTable[a->type()][b->type()];

if (func != NULL)
return func(a, b);

func = s_collisionFunctionTable[b->type()][a->type()];

if (func != NULL)
return func(b, a);

return false;
}
};


[Edited by - oliii on August 5, 2008 4:18:18 AM]

Share this post


Link to post
Share on other sites
That solution is pretty neat, although I actually figured out a solution that uses neither OR collision table thingy.

I have no concave shapes, so I can make a member function that requires a pointer to the other object, and it will return the point closest to the other object. If the points go passed each other or touch, the objects are colliding.

But, still, there are some interesting things in this thread, so I'm saving it as a reference.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!