1
\$\begingroup\$

I'm trying to build an RPG worldbuilder. I have seperate classes for images. Like this.

Object1::Object1(int x, int y, CSDL_Setup *sdl_set, int *p_CamX, int *p_CamY)
{
    X_pos = x;
    Y_pos = y;

    MouseX = 0;
    MouseY = 0;

    CamX = p_CamX;
    CamY = p_CamY;

    Object = new CSprite(sdl_set->GetRenderer(),"data/Trees/Tree3.png", X_pos, Y_pos, 100, 200, CamX, CamY);

}

I've created a vector of objects of the class Object1 and pushing it back when I create a new image. I draw them here.

void DrawObjects()
{
    for(std::vector<Object1*>::iterator i = Object.begin(); i != Object.end(); ++i)
    {
        (*i)->Draw();
    }
}

Now the rendering is done by the order the objects are created. I want to do the rendering based on y values of each object. I did a lot of research but couldn't find any example code. I also have other classes for other images. So I tried something on my own to sort y values and detect which y value corresponds to which object. But I'm stuck here.

int a;
void DoChanges()
{
    if(ChangeMade)
    {
        a = 0;

        for(std::vector<Object1*>::iterator i = Object1.begin(); i != Object1.end(); ++i)
        {
            ObjectArray[a] = (*i)->GetY();
            a++;
        }
        for(std::vector<Object2*>::iterator i = Object2.begin(); i != Object2.end(); ++i)
        {
            ObjectArray[a] = (*i)->GetY();
            a++;
        }
        ...

        SIZE = Object1.size() + Object2.size() + Object3.size() + ...;

        sort(ObjectArray, ObjectArray + SIZE);

        for(size_t i = 0; i < SIZE; i++)
        {
            for(size_t j = 0; j < SIZE; j++)
            {
                if(tree1[j]->GetY() == ObjectArray[i])
                {
                }
                else if(tree2[j]->GetY() == ObjectArray[i])
                {
                }
                ...
            }
        }

        ChangeMade = false;
    }

Is there a way to create an array of pointers to store the addresses of objects to different classes by their y values and use this array to do the rendering? Or do you have any suggestions on how to handle creating objects to the sprite class and rendering or any useful links?

Thanks.

\$\endgroup\$
  • \$\begingroup\$ Not to discourage you, and maybe your idea of a "RPG worldbuilder" isn't as grandiose as mine, but I think you might be biting off more than you can chew right now. As someone who has abandoned numerous overambitious personal projects undertaken as a means of learning a new language, I think you'd do yourself a favor by taking on a few smaller projects first; maybe reading a book or two on C++, data structures, algorithms, design patterns, software architecture, etc. \$\endgroup\$ – bcrist Aug 11 '15 at 5:31
1
\$\begingroup\$

I would forget right away the option to create the sprites in order based on their y coordinate as it will create a hell for you because it's not a flexible design.

You look like you need a common way to handle the drawing process. You can achieve this using polymorphism.

I would probably create a IDrawable interface, which requires children to have getY() and draw(), and would derive all the things that can be drawn on screen from it (Object1 and Object2 in your case).

When you're ready to draw, get all your IDrawable in a single vector, and sort that vector based on the getY().

Once sorted, call the draw() method on each of your drawables.

For instance, if you have something like these base classes:

class IDrawable
{
public: 
  double getY() const = 0;
  void   draw() = 0;
};

class Object1
{
private:
  double Y_pos;

public: 
  double getY() const { return Y_pos; }
  void   draw() { /* draw Object1 in a way that makes sense for it. */ }
};

class Object2
{
public: 
  double getY() const { double y; /* compute y */ return y; }
  void   draw() { /* draw Object2 in a way that makes sense for it. */ }
};

You could manage it like this:

class MgrDraw
{
private:
  std::map< int, std::vector<IDrawable*>* > mDrawableReferences;

public:
  // This would be called by entities that know of Object1 or Object2
  void addDrawableReferences(int aIdentifier, std::vector<IDrawable*>* aDrawableForType )
  {
    auto it = mDrawableReferences.find(aIdentifier);
    assert( it == mDrawableReferences.end() );
    mDrawableReferences[aIdentifier] = aDrawableForType;
  }

  // Call this when you're ready to draw.
  void draw()
  {
    std::vector<IDrawable*> allDrawables;
    for ( auto vec : mDrawableReferences) 
    {
      for ( auto drawable : vec )
      {
        allDrawables.push_back( drawable );
      }
    }
    // for the XXX below, check the second form: 
    // http://en.cppreference.com/w/cpp/algorithm/sort
    std::sort(allDrawables.begin(), allDrawables.end(), XXX); 
    for ( auto drawable : allDrawables )
    {
      drawable->draw();
    }
  }
};

Now, please note that this might not be the best way to achieve it, but at least it seems to solve your current issue. You could probably improve the execution by making allDrawables member of the class to avoid having to re-create it/resize it each frame.

And XXX could look like this:

struct {
  bool operator()(Drawable* a, Drawable* b)
  {   
    return a->getY() < b->getY();
  }   
} comp;

Edit

I have created a fully functional example of that. It runs as a command line program and works in visual studio. I've added comments to try to answer OP's questions.

// main.cpp
// Runs correctly with visual studio 2013. 

#include <iostream>

#include <vector>
#include <map>
#include <algorithm>
#include <random>
#include <memory>
#include <assert.h>
#include <chrono>
#include <thread>
#include <Windows.h>


// Notes
// This simple program draws numbers on the console. It sole purpose is to 
// demonstrate how multiple kinds of objects can be drawn on screen based on
// a particular rule, in this case a pseudo Y coordinate. 
// 
// The implementation has been drawn from the OP's implementation and may not be
// the best archicteture ever as I slapped this example only for the purpose
// of the question. 

/// Comment this out to see the "real-time" effect
/// Un-comment to see the order in which stuff is drawn. 
#define IS_SLOW_MOTION

static const int MIN_RANGE = 1;
static const int MAX_RANGE = 10;

// http://stackoverflow.com/a/1670911/637987
// Used to draw stuff on the console.
void gotoxy(int x, int y)
{
  COORD coord;
  coord.X = x;
  coord.Y = y;
  SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}

/// Global services; singleton that must be initialized before being used. 
class Global
{
private:
  Global()
    : mIsInitialized(false)
  {}

  /// Flag indicating if the singleton has been initialized
  bool mIsInitialized; 

  /// Random generator. 
  std::default_random_engine mGenerator; 

  /// Distribution for random position generation
  std::uniform_int_distribution<int> mDistributionPosition; 

  /// Distribution for random duration (in frames)
  std::uniform_int_distribution<int> mDistributionDuration; 

  /// Variable used to keep the count on unique identifier generation.
  int mIdGenerator; 

public:

  /// Way to access the single instance of this class.
  static Global& GetReference()
  {
    static Global Instance;
    return Instance;
  }

  /// Initialize the singleton. 
  /// This is not done in the constructor because we want to explicitely do the 
  /// construction. 
  void init()
  {
    if (mIsInitialized)
      return;
    else
      mIsInitialized = true;

    // see http://www.cplusplus.com/reference/random/ for more details on the 
    // random number generation. 
    mDistributionPosition = std::uniform_int_distribution<int>(MIN_RANGE, MAX_RANGE);
    mDistributionDuration = std::uniform_int_distribution<int>(2, 4);
    mIdGenerator = 0;
  }

  /// Destroy what has to be destroyed in the singleton. 
  void tearDown()
  {
    if (!mIsInitialized)
      return;
    else
      mIsInitialized = false;
  }

  /// Retrive the next 'unique' id. 
  int getNextId()
  {
    assert( mIsInitialized );
    if ( !mIsInitialized )
      return -1;

    ++mIdGenerator;
    return mIdGenerator;
  }

  /// Generates a random position. 
  int getRandomPosition()
  {
    // Generates a value in the range specified in the init method.
    return mDistributionPosition(mGenerator);
  }

  /// Generates a random duration. 
  int getRandomDuration()
  {
    // Generates a value in the range specified in the init method.
    return mDistributionDuration(mGenerator);
  }
};

/// Item that can be drawn; drawn according to a y position. 
class IDrawable
{
public:
  virtual double getY() const = 0;
  virtual void   draw() = 0;
};


/// This class makes children have a unique identifier. 
class Uidable
{
public:
  Uidable() : mUid(Global::GetReference().getNextId()) {}
  int getUid() const { return mUid; }
private:
  const int mUid;
};


/// One of the things that we can draw. 
/// The casual mover moves up and down with a predicatble path. 
class Object1CasualMover : public IDrawable, public Uidable
{
private:

  /// Here it is a int because it's easier to manage in the update function.
  int mYpos;

  /// Flag specifying if the item is going up (true) or down (false)
  bool mIsGoingUp;


public:
  Object1CasualMover(int aStartY, bool aShouldGoUpFirst)
    : mYpos(aStartY), mIsGoingUp(aShouldGoUpFirst)
  {}

  double getY() const { return static_cast<double>(mYpos); }

  void   draw() { 
    gotoxy( getUid(), getY() );
    std::cout << getUid();
  }

  void update() { 
    // dummy method that makes the object move up and down.
    if (mIsGoingUp)
    {
      ++mYpos;
      if (mYpos >= MAX_RANGE)
        mIsGoingUp = false;
    }
    else
    {
      --mYpos;
      if (mYpos <= MIN_RANGE)
        mIsGoingUp = true;
    }
  }
};


/// One of the things that we can draw. 
/// The houdini spawns at a random spot and stays there for a random number of 
/// frame before vanishing and spawning again.
class Object2Houdini : public IDrawable, public Uidable
{
private:

  /// Here it is a int because it's easier to manage in the update function.
  int mYpos;

  /// Frames left in the current Y position
  int mFramesLefInThisPosition;

public:

  Object2Houdini()
    : mYpos(0), mFramesLefInThisPosition(0)
  {
    update();// One call to update to set it in place
  }

  double getY() const { return static_cast<double>(mYpos); }

  void   draw() { 
    gotoxy( getUid(), getY() );
    std::cout << getUid();
  }

  void update() {
    // dummy method that makes the object move up and down randomly at random 
    // times (frames).
    if (mFramesLefInThisPosition == 0)
    {
      mYpos = Global::GetReference().getRandomPosition();
      mFramesLefInThisPosition = Global::GetReference().getRandomDuration();
    }
    --mFramesLefInThisPosition;
  }
};


/// Draw manager. Used to keep a reference to everything that needs to be drawn,
/// and sort and draw items.
class MgrDraw
{
private:
  /// References of stuff to draw. 
  /// This is _my_ way of implementing it. This was done like this for the purpose
  /// of this example. Depending on your own implementation you may need to do it
  /// in another way. I did it this way because you seemed to keep your drawables
  /// in separate vectors. 
  /// 
  /// The idea is to keep track of all the drawables.
  /// The idea of the map is to be able to retreive stuff later. (It's not needed
  /// in the current example, however.)
  std::map< int, std::vector<IDrawable*>* > mDrawableReferences; 

  /// Structure used to sort the IDrawable based on their Y coordinate.
  /// see http://en.cppreference.com/w/cpp/algorithm/sort for more details. 
  struct compareWithY{
    bool operator()(IDrawable* a, IDrawable* b)
    {   
      return a->getY() < b->getY();
    }   
  };

public:
  // This must be called by entities that know of the objects to draw. 
  // Refer to the doc of mDrawableReferences for more details. 
  void addDrawableReferences(
    int aIdentifier, 
    std::vector<IDrawable*>* aDrawableForType)
  {
    // sanity checks: don't add something that was already added.
    auto it = mDrawableReferences.find(aIdentifier);
    assert(it == mDrawableReferences.end());
    if ( it != mDrawableReferences.end() )
      return;

    // keep a reference to the vector of items.
    mDrawableReferences[aIdentifier] = aDrawableForType;
  }

  /// Call this when you're ready to draw.
  void draw()
  {
    system( "CLS" ); // Windows console call to clear up the console.

    // Gather all the drawables in a single vector. 
    std::vector<IDrawable*> allDrawables;
    for (auto vec : mDrawableReferences)
    {
      for (auto drawable : (*vec.second))
      {
        allDrawables.push_back(drawable);
      }
    }

    // Notes on the 'for ( auto vec : mDrawableReferences )' line.
    // This is c++11 code. Traditionnally, you would have written this:
    //for ( 
    //  std::map< int, std::vector<IDrawable*>* >::iterator it = 
    //    mDrawableReferences.begin();
    //  it != mDrawableReferences.end(); 
    //  ++it )
    //{
    //  std::pair<const int, std::vector<IDrawable*> *> vec = *it;

    //  // .. do stuff with vec
    //}
    //
    // The current loop is using advantage of the auto keyword which deducts 
    // the type at compile time, and the for ( bla : iterable ) with takes
    // is equivalent to a "for each" in other languages. 
    // See these pages for more detail
    // http://en.cppreference.com/w/cpp/language/auto
    // http://en.cppreference.com/w/cpp/language/range-for

    // Sort the drawables according to the algorithm in compareWithY operator()
    // You delegate the logic of the sorting to a functor. 
    // See this for more details:
    // http://www.cprogramming.com/tutorial/functors-function-objects-in-c++.html
    std::sort(allDrawables.begin(), allDrawables.end(), compareWithY());
    for (auto drawable : allDrawables)
    {
      drawable->draw(); // Draw the item. The item knows how to draw itself.
#if defined(IS_SLOW_MOTION)
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
#endif
    }
  }
};


/// Since we don't have any user interaction, this example is more a 
/// simulation than a game. I called it Sim. 
class Sim
{
public:

  /// Performs clean up tasks. 
  ~Sim()
  {
    for (auto item : mCasualMovers)
      delete item;
    for (auto item : mHoudinis)
      delete item;
    mMgrDraw.reset();
    Global::GetReference().tearDown();
  }

  /// Initializes our simulation
  void init()
  {
    Global::GetReference().init(); // According to the doc, the singleton must
                                   // be initialized. 
    // Create 5 instances of each class of drawable. 
    for (int i = 0; i < 5; ++i)
    {
      mCasualMovers.push_back(
        new Object1CasualMover(i, (i % 2 == 0) ? true : false));
    }
    for (int i = 0; i < 5; ++i)
    {
      mHoudinis.push_back(
        new Object2Houdini());
    }


    mMgrDraw = std::make_unique<MgrDraw>(); // Create the draw manager

    // Add the elements to be drawn. The numbers 1 and 2 have been chosen 
    // without any particular reason. . 
    mMgrDraw->addDrawableReferences( 1, &mCasualMovers ); 
    mMgrDraw->addDrawableReferences( 2, &mHoudinis );
  }


  /// Run a simulation frame.
  bool run()
  {
    // Update all the know objects.
    for ( auto obj1 : mCasualMovers )
    {
      static_cast<Object1CasualMover*>( obj1 )->update();
    }
    for ( auto obj2 : mHoudinis )
    {
      static_cast<Object2Houdini*>( obj2 )->update();
    }

    // Draw them.
    mMgrDraw->draw();

    // In a real game, you'd probably want an exit condition (user wants to quit
    // the game, for instance). 
    return true;
  }

  std::unique_ptr<MgrDraw> mMgrDraw;     ///< The draw manager
  std::vector<IDrawable*> mCasualMovers; ///< All the casual movers
  std::vector<IDrawable*> mHoudinis;     ///< All the houdinis
};


int main(void)
{
  Sim sim;
  sim.init();

  while ( sim.run() ) // as long as the simulation wants to run, it runs!
  {

#if defined(IS_SLOW_MOTION)
    std::this_thread::sleep_for(std::chrono::milliseconds(1000));
#else
    std::this_thread::sleep_for(std::chrono::milliseconds(500));
#endif
  }

  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for going through all the trouble to help me but I could use some more help. I'm actually not good with STL classes. Because I find them confusing I avoid using them. Okay my questions are: what addDrawableReferences exactly do? Specificly this line: mDrawableReferences[aIdentifier] = aDrawableForType; And in the for loops what does "auto vec: mDrawableReferences" mean and how does it work? And the XXX struct. What does it do how does it work with the sort() function? \$\endgroup\$ – bfkjohns Aug 9 '15 at 8:17
  • \$\begingroup\$ I did go through the code and read some articles to understand your code. I have never used the features you used before and I don't think I fully understand the concept. It's my lack of knowledge. Can you please add comments line by line explaining the code(MgrDrawClass). Thank you. \$\endgroup\$ – bfkjohns Aug 9 '15 at 21:33
  • \$\begingroup\$ @bfkjohns I have added a fully working example and tried to answer your questions in there. You'll want to try it and read the comments. Try commenting and un-commenting the macro (#define) to have a better idea. For more questions, I would suggest you try and get enough reputation (20) so you could ask in a chat room. Oh, I have not specified that there, but I would strongly suggest you get familiar with the C++ Standard Library as this will save you time and, eventually, headaches of having to re-code the wheel by yourself. \$\endgroup\$ – Alexandre Vaillancourt Aug 10 '15 at 17:17
  • \$\begingroup\$ With your help and wodra's suggestion I was able to get my code working. Thanks a lot! \$\endgroup\$ – bfkjohns Aug 11 '15 at 19:30
  • \$\begingroup\$ @bfkjohns glad I could help! \$\endgroup\$ – Alexandre Vaillancourt Aug 11 '15 at 19:33
1
\$\begingroup\$

You could re-order your std::vector<Object> by creating a function that sort it by Y position of your objects

void SortObjects()
{
   std::sort(Object.begin(), Object.end(), CompareYAxis);
}

bool CompareYAxis(const Object first, const Object second)
{
    //Do the comparison here
}

I think this would work.

\$\endgroup\$
0
\$\begingroup\$

To expand @Alexandre Vaillancourt answer, I would even consider using a collection that keeps your data sorted, instead of re-sorting it every frame.

struct Drawable_compare {
    bool operator() (const IDrawable& d1, const IDrawable& d2) const{
            return d1.y < d2.y;
    }
};

class Renderer
{
private:
  std::multiset<IDrawable*, Drawable_compare > objects;

public:
  //similar for Unregister
  void RegisterObject(IDrawable* drawable) {
     objects.insert(drawable);
  }

  void drawAll() {
  for (auto i = objects.begin(); i != objects.end(); i++)
     i->Draw();
  }
}

Where did the std::vector<Object1*> go? The renderer does not need it now - its IDrawable for it, and if you do, you would probably have to duplicate the references data anyway and this way you can separate actual and logical order/storage of you data.
Why suggesting this solution? Even though, judging from your code, you dont aim for performance, this spares you re-sorting every frame and makes you code simplier. If you are looking for faster solution you should rather change design of your engine to be more data-driven.
Note: I did not check the syntax, and in the end which solution is better depends on personal preferences, on your preferences.
While it performs great for mainly static scene, the fact that you cannot change keys makes this solution worse if nearly all objects are moving (moving in Y axis requires re-adding the object to the collection - you need Move() method instead of writing to the data directly).
Alternatively, you can keep only static objects(trees, building, etc.) in this set as it handles inserting and deleting for you, and do manual re-sorting every frame for your your moving objects(orcs, player,...) .

\$\endgroup\$
  • \$\begingroup\$ std::multiset does not keep data sorted; it assumes that the data used as a criterion for sorting will not change while it is in the set. As soon as you change an object's y after inserting it in the map, you've invoked undefined behavior. In order for this system to work properly, objects must either never change their y position, or they need to be removed from objects before changing y and reinserted after. \$\endgroup\$ – bcrist Aug 11 '15 at 6:02
  • \$\begingroup\$ @bcrist Good point, key values cannot change(after all its in documentation), it would require additional logic. If (nearly) all object are (nearly) always changing key between frames, sorting each frame would be better. However contrary to you I would not expected answers contain complete code ready to ship. Re-adding is still LogN complexity contrary to NlogN sorting. \$\endgroup\$ – wondra Aug 12 '15 at 10:37
  • \$\begingroup\$ I'm not sure where you got the idea that I think answers should contain production code. But I do believe answers should explain any caveats that wouldn't be immediately obvious to the intended audience, and I don't consider the equivalent of "RTFM" as an excuse for not explaining them. \$\endgroup\$ – bcrist Aug 12 '15 at 15:23
  • \$\begingroup\$ Reinserting a single object is O(log(N)), but there's not necessarily just one object moving every frame, so the overall worse case complexity is still O(N*log(N)) Best-case complexity is better, but there are also plenty of sorting algos with best-case complexities better than N*log(N) when the data is "mostly" sorted already. Sorting all at once is much more cache-friendly, which drastically increases the minimum size at which the overall complexity begins to dominate. \$\endgroup\$ – bcrist Aug 12 '15 at 15:31
  • \$\begingroup\$ Even if keeping your drawlist sorted all the time is more performant (I'm not convinced it is for the OP's use case), optimizing for slightly better algorithmic complexity before you know you have a performance problem is generally a bad idea, especially if you're already doing better than O(N^2). At the very least, it wastes development time, at worst (and in this case) it introduces new assumptions and requirements on other parts of the codebase, leading to code that's harder to understand and maintain. \$\endgroup\$ – bcrist Aug 12 '15 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.