Jump to content
  • Advertisement
Sign in to follow this  
altich88

C++ templates, polymorphism and inheritance

This topic is 2505 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

[color=#000000][font=verdana, arial, helvetica, sans-serif]

Hi,[/font]

[color=#000000][font=verdana, arial, helvetica, sans-serif]

I'm not sure how to go about this one. I have a class "Grid", which has a 2D vector of "GridTile" objects. GridTile is a base class from which "UiTile" inherits. I want to write the Grid class so that the 2D vector can store GridTile tiles or any type that inherits from GridTile.[/font]

[color=#000000][font=verdana, arial, helvetica, sans-serif]

Would templates be the best way to do this? [/font]

[color=#000000][font=verdana, arial, helvetica, sans-serif]

This is what I have attempted so far. I've read that the implementation must be in the same file as the declaration, so it is all in Grid.h:[/font]



// Base class 2D grid
template <class GridTile> class Grid
{
public:

// boring fields etc not included...

vector< vector<GridTile> > tileTable; // 2D array of cells
};

template <class GridTile>
void Grid<GridTile>::drawCellsAll_Wireframe()
{
// body of code not included...
}



[color=#000000][font=verdana, arial, helvetica, sans-serif]

I've tried this with both GridTiles and classes that inherit from GridTile and it seems to work ok. Am I about right in my approach?[/font]

Share this post


Link to post
Share on other sites
Advertisement

I want to write the Grid class so that the 2D vector can store GridTile tiles or any type that inherits from GridTile.


vector< vector< GridTile* > > grid;

Better to use a smart pointer though.

Share this post


Link to post
Share on other sites

[quote name='altich88' timestamp='1328701718' post='4910867']
I want to write the Grid class so that the 2D vector can store GridTile tiles or any type that inherits from GridTile.


vector< vector< GridTile* > > grid;

Better to use a smart pointer though.
[/quote]

Thanks for your reply. Why is it better to use a pointer here?

(I'm coming to C++ from Java so please excuse my ignorance with pointers - I've used a few basic examples but am still learning on when best to use them!)

Share this post


Link to post
Share on other sites

[quote name='Rene Z' timestamp='1328704884' post='4910875']
[quote name='altich88' timestamp='1328701718' post='4910867']
I want to write the Grid class so that the 2D vector can store GridTile tiles or any type that inherits from GridTile.


vector< vector< GridTile* > > grid;

Better to use a smart pointer though.
[/quote]

Thanks for your reply. Why is it better to use a pointer here?

(I'm coming to C++ from Java so please excuse my ignorance with pointers - I've used a few basic examples but am still learning on when best to use them!)
[/quote]

Templates are used for generic programming like lists in which you want to be able to store any datatype. And you only define the storage container and it's operations but not the data type.
What you want however is polymorifsme, and to store classes that derive from the same type but are in a hetreogeneous collection, you need a pointer to the base class as the data type of your list.

You could use a void* pointer but thats not very nice and you lose all functionality to loop over the list and call commenly defined functions (defined in the base class or interface) on it.

Share this post


Link to post
Share on other sites

Thanks for your reply. Why is it better to use a pointer here?


The SomeType* means a pointer to SomeType, but that's a raw pointer. Raw pointers can easily cause problems in large codebases like dangling pointers, memory leaks, heap corruption just to name a few.

A smart pointer is a small class or struct that manages the data it's pointing to. Basically, this means the pointed-to data will automatically be deleted as soon as there's no longer a pointer pointing to it, and no sooner than that. Most high quality code bases will almost exclusively use smart pointers.

As NightCreature said, if you want to use polymorphism you must use pointers or references. If you want to understand why, look up the 'slicing problem'. The following answer on StackOverflow explains nicely:
http://stackoverflow...lem-in-c#274636

Share this post


Link to post
Share on other sites

...


...



Thanks for the links, very useful. So it seems polymorphism is the way to go rather than templates. Does this mean I will have to cast to the derived class like so to gain access to the derived class members etc?

I've had a play with the following which seems to work.



class Base
{
public:
int a;

Base()
{
a = 1;
}
};

class Deriv : public Base
{
public:
int b;

Deriv() : Base()
{
b = 2;
}
};

Base* pBase;
Deriv* pDeriv;

Deriv deriv1;

pDeriv = &deriv1;

pDeriv->a = 100;
pDeriv->b = 200;

pBase = pDeriv;

cout << ((Deriv*)(pBase))->b << endl; // works



Firstly would this be the correct approach?

Secondly, if so, let's say you had an array of base class pointers, some of which pointed to objects of the base class type, but some pointed to objects of derived class type. In this situation how would you know what to cast to? Do you have to have some kind of ID field defined for each type of object? e.g.


#define BASE_ID 1
#define DERIV_ID 2
int type = BASE_ID;
for example?

Many thanks for your help so far, much appreciated.

Share this post


Link to post
Share on other sites
It depends what your goal is.

If you want to hold both GridTile and UITile in the same Grid instance, then you have to use base class pointers like everyone has been saying (there are other non-standard "hacks" you could do, but are tricky and subject to a lot of caveats, so I won't go into that).

However, if just one type of tile will be stored per Grid instance, then you can indeed use templates. The pros of templates are that you'll save memory (you only have to store tiles, not tiles *and* pointers), you'll avoid dynamic allocation and manual memory management (pooled allocation and smart pointers help when these things can't be avoided, but its always better to not have a problem at all, than to have to fix it), and that your Tiles will be in contiguous memory and so won't thrash your CPU cache (pooled allocations can help here too, but again, the simplest solution is to avoid the problem in the first place.) The cons of Templates are that both Grid types (one for GridTiles, the other for UITiles) are more or less identical, but completely incompatible -- you won't be able to copy data directly from one to the other, you won't be able to write a function which can take both types as parameters (but you can write a template function, or overload on both types), and you end up with two copies of the code for each (in practice, the compiler will minimize the amount of redundant code, but there is almost always some); complex templates can also take a while to compile, but this case is simple.


All that being said, the bigger question is how different a UITile actually is from a GridTile. Its possible, if not likely, that by dividing the duties of these classes differently, that you might be able to avoid this problem altogether. It's very common to reach for inheritance almost as a reflex, but this can lead to deep hierarchies and the diamond inheritance problem if you're not careful. Experienced developers using the OOP paradigm know that a limited use of inheritance is typically a sign of good code, and that you can get there by dividing responsibilities clearly and keeping classes focused on a single task. You shouldn't avoid inheritance by creating your own version of it, mind you -- use the real thing when its the right solution -- just don't start with the assumption that its always the right solution.

If you share how your tile types are different, we might be able to come up with an altogether different solution.

Share this post


Link to post
Share on other sites

If you want to hold both GridTile and UITile in the same Grid instance, then you have to use base class pointers like everyone has been saying (there are other non-standard "hacks" you could do, but are tricky and subject to a lot of caveats, so I won't go into that).


GridTiles and UiTiles will not be stored together in the same Grid instance. As a quick aside though, was I correct in thinking that there is no way to tell if a base pointer is pointing to a base or derived object without some sort of ID field in the base class?

Back to the main point however. Yes that's correct,

just one type of tile will be stored per Grid instance.

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I'll describe the overall problem to give an idea of what I'm attempting. Basically I'm making my own basic user interface for a 2D map editor. The interface will consist of various windows/panels that can be dragged about the screen. I refer to these as UiContainers. The containers have within them various types of UiElement[/font][color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

, such as buttons, sliders and the like.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I had planned to split up the OpenGL window using a 2D grid to minimise collision detection tests between the mouse and the various UiWindows floating about the screen. The idea was that the tiles in this big grid would contain pointers to the UiWindows. As the windows would move about the screen, so the pointers in the big grid would be updated.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

Once it had been established which UiWindow was in the same tile as the cursor, further collision detction could be conducted on this single UiWindow to see which elements of it may be being controlled/clicked on by the mouse. I was going to use another grid to subdivide each UiWindow so we wouldn't have to check each UiElement on the window in question. As such these smaller grids (made ofUiTiles) would contain pointers to the buttons/sliders contained within them.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I guess because a 2D regular grid is such a commonly used thing I thought it would be best to have a generic Grid class that could be further specified in other classes. The GridTile for example only has a midpoint and has no real use save for providing a base class to inherit from for more specific grids. [/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

In short the UiTile would have a pointer to any possible ui elements for an individual ui wondow.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I've attached an image incase I haven't explained it very well. [/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

Thanks for your help so far, very useful stuff and it's much appreciated.[/font]

Share this post


Link to post
Share on other sites

[quote name='Ravyne' timestamp='1328715503' post='4910923']
If you want to hold both GridTile and UITile in the same Grid instance, then you have to use base class pointers like everyone has been saying (there are other non-standard "hacks" you could do, but are tricky and subject to a lot of caveats, so I won't go into that).


GridTiles and UiTiles will not be stored together in the same Grid instance. As a quick aside though, was I correct in thinking that there is no way to tell if a base pointer is pointing to a base or derived object without some sort of ID field in the base class?

Back to the main point however. Yes that's correct,

just one type of tile will be stored per Grid instance.

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I'll describe the overall problem to give an idea of what I'm attempting. Basically I'm making my own basic user interface for a 2D map editor. The interface will consist of various windows/panels that can be dragged about the screen. I refer to these as UiContainers. The containers have within them various types of UiElement[/font][color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

, such as buttons, sliders and the like.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I had planned to split up the OpenGL window using a 2D grid to minimise collision detection tests between the mouse and the various UiWindows floating about the screen. The idea was that the tiles in this big grid would contain pointers to the UiWindows. As the windows would move about the screen, so the pointers in the big grid would be updated.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

Once it had been established which UiWindow was in the same tile as the cursor, further collision detction could be conducted on this single UiWindow to see which elements of it may be being controlled/clicked on by the mouse. I was going to use another grid to subdivide each UiWindow so we wouldn't have to check each UiElement on the window in question. As such these smaller grids (made ofUiTiles) would contain pointers to the buttons/sliders contained within them.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I guess because a 2D regular grid is such a commonly used thing I thought it would be best to have a generic Grid class that could be further specified in other classes. The GridTile for example only has a midpoint and has no real use save for providing a base class to inherit from for more specific grids. [/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

In short the UiTile would have a pointer to any possible ui elements for an individual ui wondow.[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

I've attached an image incase I haven't explained it very well. [/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

Thanks for your help so far, very useful stuff and it's much appreciated.[/font]


[/quote]
There is and there isn't when you turn RTTI on the runtime can tell you which type it is, without it there is no way to find out. But you usually don't care about it because the base class defines the public interface for what you want to do. You can override the functions in a derived version and in those you can actually access your derived members as well.

Share this post


Link to post
Share on other sites
In this particular case it sounds like you're optimizing something that doesn't need to be optimized -- since any reasonable UI is built on parent-child relationships, its already got a good way to minimize the work that goes into mouse selection. When you consider the overhead of moving controls around the grid as a window is dragged around, this approach is costing you more than its worth, IMHO (certainly in terms of code-complexity, if not performance). Furthermore, a click on a unique control happens perhaps every few seconds, so its hardly something that needs to be optimized *at all*. I also worry, but can't confirm based on information given, that this indicates tight and unnecessary coupling between the UI and other program logic.

There are better ways to optimize this. For starters:

  1. Each time you click (or mouse-over), store a pointer/handle to that control. The next time you click (or move the mouse) check that item first (and its children, if it has any) before doing anything else. If you find a match this way, you're done (but be careful to reset if a window pops over that control). This will probably catch 70% of clicks, and 99% of mouse-over-like changes -- and its dead-simple to implement.
  2. Instead of this grid approach, do a recursive search starting with the main window (assume a window is rectangular, and do finer detection as a second step only if the rect matches), descending into each child that matches, and repeat for its children until no child is a better match. Wherever you end is the control that is under the cursor. This, combined with the first suggestion, will already be very highly optimal.
  3. If (and only if) performance is still unacceptable (maybe if this were applied to many small units in an RTS with hundreds+ units on screen) then you can also sort the controls for quicker detection -- for each child control, add to a list that controls y coordinate (relative to its parent), its height, and a pointer to the child control (or just do the list of child controls this way). This list should be sorted by the y element. You then iterate over the list and add controls where mouse.y >= list[n].y and mouse.y < list[n].y + list[n].height, and early-out as soon as mouse.y > list[n].y. Now do the same using the x/width elements against the list of candidates (not the list of all controls). If your system allows multiple collisions to occur (such as due to overlap or transparency, choose the control with the nearest z element). I've described this as a list for simplicity, but better still would be to do this using a binary search tree.

You were right to think that partitioning things in a grid can help by reducing the number of items that need to be checked, but where you missed out was not exploiting the natural parent-child relationship here. Grids or other spacial partitioning techniques (BVHs in general, like quadtrees or octrees) are more suitable when a great number of entities (usually moving) occupy a single, large parent space -- for example, its common to split up a 2-D or 3-D gameworld using grids/quadtrees or octtrees, respectively.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!