Hey guys. I'm programming a side scrolling platforming game, and I was wondering if other people go about games the same way, or if my method is horribly inefficient, or what.

Pretty much, for example, my platforms are made up of blocks with variable width and height. I've created a class named 'obstacle' that contains an x, y, width, height, a couple of other variables, and a couple of functions such as drawObstacle().

To draw the obstacles, for instance, I loop through every single obstacle in the obstacle class and call it's drawObstacle() function.

Does this sound about right guys? Is this pretty much how it should be, with classes and such? The reason I am asking, is because I was talking to my teacher about my platforming game, and he was saying something about classes being horribly inefficient and recommended using AVL trees instead, but upon checking what an AVL tree is, I couldn't see how that could possibly be used for my obstacles instead of classes... I'm thinking he didn't know what he was talking about, but I could easily be wrong.

On a side note, are structs noticeably more efficient than classes?

Any ideas or comments would be welcome. I'd be interested in hearing if you guys go about using classes for multiple objects as well like I do, or if you do something different. Thanks for your help!

I had to look it up too.

Seems odd he would use a rare acronym when describing a common technique. He could have said "self-balancing binary search tree."

Secondly, a binary search tree has absolutely nothing to do with using classes for physical obstacles in a game. Your professor needs to lay off the crack.

What you are doing now sounds fine. Structs aren't faster than classes unless you explicitly avoid the virtual lookup table, but even then you aren't saving much. Using classes you should probably try to have a base class that has some draw() method and then make obstacles and whatever else a derived class.

class DrawableThing{
  virtual void draw() = 0;
};

class Obstacle: public DrawabaleThing{
  virtual void draw(); // implement this in a .cpp file
};

class WhateverElse: public DrawableThing{
  virtual void draw();
};

AVL trees don't seem to have any relation to this.

... I'm getting a "variables vs. HTML" vibe from this. Either you misheard or misquoted your teacher, or your teacher is mentally deficient.

You may want to consider using vectors or another type of STL container to store and manage pointers to your objects. Using that method, you can easily iterate through your objects and call appropriate methods on them such as draw ().

This is also efficient because you can easily 'push' objects on the structure and 'pop' them off when you are done with them.

void doObstacleLogic ()
{
  // You don't want to call methods on pointers that don't exist
  if (obstacles.size ())
  {
    // Iterate through the container
    for (int i = 0; i < obstacles.size (); ++ i)
    {
      if (obstacles [i]->isDestroyed ())
      {
        // remove pointer from the container
        obstacles.erase (obstacles.begin () + i) ;
      }
    }
  }
}

This will miss every obstacle after a destroyed obstacle. And I don't believe an iterator + arbitrary_number is standards compliant. The proper way would be:

typedef std::vector<obstacle*> ObstacleVector;
ObstacleVector obstacles;
...
for(ObstacleVector::iterator iter = obstacles.begin(),iter_end = obstacles.end();
    iter != iter_end;/*do nothing*/)
{
    if((*iter)->isDestroyed())
    {
        delete *iter;
        iter = obstacles.erase(iter);
        // iter_end was invalidated by erase(), restore it
        iter_end = obstacles.end();
    }
    else
        iter++;
}

It is. vector's implement the RandomAccessIterator which allows for that sort of thing. Your method is still better though.

I'm thinking my teacher misunderstood what I was telling him, really.

@ (BitCruncher || Kitty Cat):
Is this method you listed substantially more effecient than using classes like I am currently using? Like, twice as good? Or is it just a small improvement as far as speed is concerned?

Using classes is fine. As far as your explanation goes, I assume you're doing the same that BitCruncher said first(though he did bad coding), and Kitty Cat posted the method well.

I doubt there'll be any improvements in speed switching from classes to struct. Also, you'd be crippling yourself from C++ features.

And I think this is what your teacher thought: You told him that you had a list of obstacles, and you iterated through it every frame. I think he thought in the case that your game had about, say, thousands of obstacles, when only 13 were seen at the screen, it would be a waste to check if each one of those was on the screen. The worst case might be when you need to check the collisions. With such a high number of obstacles, you'd need to check for every entity that could move with each of the obstacles.

I don't know if your game has a really big amount of obstacles. If you feel like you need optimizing, there's plenty of threads this has been discussed. And the answers were always the kind like binary search trees.

My opinion? Don't bother with it too much unless you need a really big set of obstacles.

BTW, would you mind illustrating a bit better how this "obstacle" system works? Maybe a tilemap would do a better job if everything in the game is like a grid.

The "proper" way is to do advance(itr, 5)^[1]. This is complimented by distance(itr1, itr2)^[2].

IMO, I think it's much cleaner and clarifying (though maybe slower) to use a separate container for the "dead" objects. Any objects that are pronounced "dead" will be added to this separate container. The actual deletion will be done after the update loop. Something like this:

That's how I handle "dead" objects.

[EDITED]

@ dario ff:
Click here for a basic explanation of how my current system works. So far it's working pretty darn well. I'm programming the game on a 400mhz PC that's over ten years old so to ensure I code as efficiently as I can :] So far I can have more blocks than I'd reasonably need on the PC with an unreasonable amount of objects testing collisions with said blocks, so I won't be switching from classes for this game. Perhaps I'll check it out after I finish this one

Hey, that's pretty cool. You're using a technique I used myself some years ago, and I like recommending that one. It's good to organise your obstacles into sub-sectors. Also, I think that programming on 400mhz PC is a pretty good strategy. I did programming before with a 800 mhz back then, and it's a really good experience to learn more efficient methods.

But I think you didn't get right what's a binary search tree. Think about it like another type of list, optimized for getting what elements you want according to a search criteria. You're not replacing classes, you just add them new members and organize them differently.

But I wouldn't bother with them. Your method proves the idea I always recommend works perfect.

It seems you've got a lot of will to work on your game. Developing an efficient debug mode keeps me from programming sometimes

BTW, if you're having any doubts about programming slopes, you can maybe get away with some maths depending on the x position related to the tile.

@ Falciase,

Very nice work on the engine.

Vectors aren't a substitute for classes; rather they are a method of multiple object handling; similar to arrays.

Vectors

You should check them out.

@ Dustin Dettmer, Kitty Cat,

Thanks for the corrections. I had always coded them that way and I never ran into run-time errors but it may have caused undetected internal memory errors.

@ dario ff:
Thanks for the reassurance, it's nice to know someone else has successfully done the same thing-- and to think I thought I was working on a novel concept, hahah. And yeah, working on slopes as we speak XD definitely simply using the offset x to calculate where the y should be. It's not quite working properly yet, but I'm sure I'll get it eventually-- if not, you are sure to see another post from a noob (me) on these forums XD

@ Bitcruncher:
Thanks! Been working alot on it as of late.

In C++, a class and a struct are exactly the same thing, the only difference is that the default visibility for a class is 'private', while for a struct, it is 'public'. Because of this, there is no runtime performance difference at all.

Avoiding classes or structs for performance reasons is plain silly; whether something is a class or not does not have anything to do with runtime performance at all.

The problem you're actually dealing with (and which you seem to have solved) is a very common one in games: Given a number of objects, how can I detect collisions as efficiently as possible?
The brute-force approach (compare every object against every other object) works, but its complexity is O(n²), in other words, given n objects, you need to perform n² comparisons.
A better approach is your sector-based one; it's easy to program, and it works well for many types of games. Typically the maximum number of objects per sector is limited, so you only need to perform a fixed number of comparisons per item: O(n).
Something like quadtrees is harder to program, and more efficient, but you'll only see real benefits if your scenes are complex and have a rather unbalanced distribution of objects in them (i.e., some hotspots where most of your objects are, and large areas that are almost empty).