[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.

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.

[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.

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.