Organizing objects for collisions - hobby game engine

Started by
3 comments, last by Zakwayda 4 years, 8 months ago

Hi,

as some here i'm working on my own, little and insignificant game engine based on sfml. It's more as a general training than anything else.

I've got to a decent point, here's what i already have if you dont want to go straight to the quesiton:

Spoiler
  • Game engine class
    • Game objects list (list<Object*>)
    • Main game loop, fixed timestep dynamic drawing. Each step:
      • Call input(event) passing sfml events as they're polled for each object.
      • Call move (see later)
      • Call step for each object
      • Handle objects destruction (objects aren't explicitely destroyed by user code, instead they set a flag and are deleted here.
  • Object class
    • virtual functions for input, step, draw.
    • animated sprite class
  • Resource manager
  • Async logger

Now, each Object has a private "move" method that is called each step for movement.

I then wanted to give a simple interface for collisions, but its getting difficult to do. (collision itself is already ready).

Ideally i wanted an actual game to define its own objects as children of Object, overriding the desired methods and adding any variable the user needs. However this goes in conflict with the way i wanted to structure collision. My idea for collision was:

  1. Add a list of "collider list" to game engine.
  2. Each "collider list" is a list of objects.
  3. When you create an object that will need to be checked for collision with by something, you add it to a collider list (for example i could have a collider list holding all walls).
  4. When i create a moving object which must perform a specific action on collision with a specific collider list, i add a pointer to that collider list to that object's "collisions list", and a function pointer to a function that takes (here comes the difficult part) Object* other as argument?
  5. While the game is running, when applying movement to a specific object a, the engine internally checks if there's a collision for each object b of each "collider list"  c inside a's "collisions list", and for each b which collides, call the function associated with that c inside a.

Simplified base classes to follow this sequence (c++ looking pseudocode written on the fly, i might have missed something and don't look at memory management or private/public things, it's not actual code i'm using):

Spoiler


class Collider_list
	{ 
	std::list<Object*> list;
	void remove(std::list<Object*>::iterator it)
		{ list.erase(it); }
	void insert(Object* o)
		{ list.push_back(o); }
	}
	
class Collisions_list
	{
	std::vector<Collider_list*> collider_lists;
	std::vector<std::function<void(Object*, Object*)> > functions;
	
	void add_collision(Collider_list* collider_list, std::function<void(Object*> function)
		{
		collider_lists.push_back(collider_list);
		functions.push_back(function);
		}
	void check(Object* self)
		{
		for(size_t i = 0; i<collider_lists.size(); i++)
			{
			auto list = collider_lists[i];
			for(auto other : list)
				{
				if(self.bounding_box.collide(other.bounding_box)
					{
					*(functions[i])(self, other);
					}
				}
			}
		}
	}

class Object
	{
	std::vector<Collider_list::iterator> collider_lists; //know your position in all collider lists to remove yourself.
	std::vector<Collider_list*> collider_lists_it; //know your position in all collider lists to remove yourself.
	Collisions_list collisions_list;
	
	~Object
		{
		for(size_t i = 0; i<collider_lists.size(); i++)
			{ collider_lists[i].remove(collider_lists_it[i]); }
		}
	
	void move()
		{
		x += x_speed;//it's more complex but doesnt matter here
		y += y_speed; 
		collisions_list.check(this);
		}
	
	public: 
		void add_collision(Collider_list* collider_list, std::function<void(Object*, Object*)> function)
			{ collisions_list.add_collision(collider_list, function); }
	}

 

The problem is i can only have Object* as an argument for collisions, and the user should instead be able to access the variables he set on his class that inherits from Object. Also even if i knew (and i dont) all the classes that a game based on the engine was going to make, i wouldn't be able to put the functions in that list, because the list specifies std::function<void(Object*, Object*)>, and not std::function<void(Ball*, Wall*)>

Example:


class Wall : public Object { bool sticky = false; } //sitcky is needed to explain the problem i have
class Ball : public Object{}

...
  
Collider_list* walls = Engine.create_collider_list();
Wall* tmp = nullptr;
for(size_t i=0; i<10; i++)
	{
	//create at {x, y} coordinates
	tmp = Engine.create(new Wall({i, 0}));
	walls.insert(tmp);
	}
tmp->sticky = true; //here's a variable specific to Wall, not present in Object, that Ball will need when it handles the collision.


Ball* ball = Engine.create(new Ball({30, 30});
ball.add_collision(walls, /*some bouncing function that stops ball's movement if the wall has sticky set to bool*/);

I'm not sure if it's possible to work around this through some template metaprogramming. I never dug into that, and if it's possible i'd gladly take some advices for that.

 

The other option that came to my mind (which solves everything but i dont like), is the following:

A game actually uses Object directly, no inheritance with virtual functions overriding etcc. Instead Object will have a function pointer for all custom events that previously were virtual (input, step, etcc), and a map string-to-float. The user will always deal with Object, and "defining a new class" like a Ball would consist in creating a new instance of Object and assigning it a defined set of functions and pseudo-variables in the map.

Assuming the user knows what he's doing it's perfect, but the result is a sadly javascript-object feeling, which i totally dislike, with no safety nor type checks, where anything can be anything and you have to manually keep track of what is what. Yeah it would work, but yeah i'd prefer solutions that don't make c++ become javashit javascript for the rest of the program.

So, can templates do the magic?

Advertisement

Since no one's responded to this yet, I'll offer some comments.

I realize what you've posted is pseudocode or example code, but one thing you might consider if you haven't already is avoiding duplicate collision checks (that is, checking A against B and later, redundantly, B against A). It may not matter depending on the cost of the collision checks and the number of checks performed, but it's a typical and often straightforward optimization to make for the narrow phase.

As for your specific problem regarding collision callbacks, a simple and low-tech solution might be to downcast as needed. Downcasts are sometimes frowned upon, but are nevertheless sometimes used for this sort of thing, even in widely used frameworks. (dynamic_cast can offer some safety here. It may incur some performance cost, but that may or may not matter, depending.)

There's also the issue of baking the collision system into the object system. I won't go into detail here, but I can think of some criticisms of this design choice (such as that it seems to assume all objects are interactive, which doesn't seem like would necessarily be the case).

There might be some other design patterns that could be leveraged here, but I'll move on to some more general suggestions.

I don't want this post to be excessively long, so without going into great detail I'll just mention a couple other things that might be worth looking into: the often controversial entity/component-based approach, and the possibility of introducing a scripting system (I know you were critical of JavaScript and dynamic typing in your post, but I wouldn't necessarily dismiss such languages or scripting in general). You may not want to make such significant architectural changes at this point, but I think either or both of these could help address some of the issues you're facing.

On 8/21/2019 at 12:26 PM, Zakwayda said:

(such as that it seems to assume all objects are interactive, which doesn't seem like would necessarily be the case).

My idea is to exactly avoid that. Every object would have its pointer to collider list of things it can collide with and function for what to do upon collision. With objects you don't interact with, you simply don't have a dedicated list.

if class A can collide with class B, class B with C, i only have a list of B items and a list of C items. A will check collision for the list of B items, B will check for the list of C items, C won't do any check. Plus no collider list of A items exist.

This also solves the 

Quote

(that is, checking A against B and later, redundantly, B against A)

A checks each B and does what it has to do. B doesn't have to check A.

 

The engine step would be:



for each object
    for each collider list IN that object (so not every collider list of the engine)
	    for each element in that list
		    if collision then call function associated with that list in this object

I further elaborated he idea, my problem now is storing somewhere lists of pointers to different classes. I guess i'll go for the dynamic cast, but tbh it seems weird. After all the compiler *could* know at compile time the type of each collider list.

32 minutes ago, Michael Marchesan said:

My idea is to exactly avoid that. Every object would have its pointer to collider list of things it can collide with and function for what to do upon collision. With objects you don't interact with, you simply don't have a dedicated list.

if class A can collide with class B, class B with C, i only have a list of B items and a list of C items. A will check collision for the list of B items, B will check for the list of C items, C won't do any check. Plus no collider list of A items exist.

This also solves the 

A checks each B and does what it has to do. B doesn't have to check A.

 

The engine step would be:




for each object
    for each collider list IN that object (so not every collider list of the engine)
	    for each element in that list
		    if collision then call function associated with that list in this object

 

I see. Separating the collision system from the game object system could have other advantages, such as easier testing, better modularity, and possible performance gains (in that you don't even have to iterate over noninteractive objects - although you might be able to accomplish something similar by storing interactive objects in a separate container). But, I'm sure arguments could be made for rolling it all together as well.

Quote

After all the compiler *could* know at compile time the type of each collider list.

I'm not sure off the top of my head how that would work without seeing an example ?

In any case, maybe there's a better solution that would both avoid casting and fit nicely into your current architecture, but if so it's not apparent to me at the moment.

If it helps at all, the redoubtable Box2D appears to more or less require casting in collision callbacks, assuming the API hasn't changed since this article was published:

https://www.iforce2d.net/b2dtut/collision-callbacks

And it's not even downcasts - it's just a 'void' user data pointer. As sketchy as downcasts might seem, void pointers are arguably even sketchier ? And yet (in my experience at least) using void pointers for generic 'data packages' is fairly common.

To be clear, I'm not saying these idioms (downcasts, void pointers, etc.) are best practice necessarily, just that there's plenty of precedent for their use, even in widely used and well regarded software. You'll have to gauge your own comfort level of course, but maybe the fact that there's precedent will put you at ease a bit.

This topic is closed to new replies.

Advertisement