Jump to content
  • Advertisement
Sign in to follow this  
Calin

Elegant system for menus

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

I'm working on a game that has a menu with 70+ buttons ( it's a 3D modeling type of program). All this buttons switch on and off following a lot of rules. Initially I started with bare arrays and if&for conditional statements. After adding about 30 buttons the code started to get messy and imposible to expand(add new rules etc.) so I placed all my buttons in a STL vector . However now I have a performance problem. I have to iterate through this vector list hundreds of times in different parts of my code to provide the menu data. My question is what kind of systems are usually being used in medium to big scale applications for menu/interface data management?

Share this post


Link to post
Share on other sites
Advertisement
Why do you need to 'iterate through' your vector? Vectors aren't linked lists(thats std list), so you shouldn't be having that problem.

Share this post


Link to post
Share on other sites
That's exactly why I started using vector instead of arrays. I don't have to keep the count of the buttons or their location in the stack.

Share this post


Link to post
Share on other sites
Actually this might solve my problem. I can use the vector list like an array when reading the data and iterate through it when writing. I have a single functon that writes data to list buttons ( this is where my 'rules' are ) in all other places I'm only reading data. Thanks for suggestion [smile]

[Edited by - Calin on January 21, 2006 10:59:48 AM]

Share this post


Link to post
Share on other sites
That sounds better; if a vector is too slow, then you'd be having some serious problems.

Good luck!

Share this post


Link to post
Share on other sites
Quote:
Original post by Calin
... I can use the vector list like an array when reading the data and iterate through it when writing.


What exactly do you mean by that? std::vector is a random access container with random access iterators and is guaranteed to hold elements in memory contiguously. So read/writing/iterating is no different than doing it with an array, whether you where iterating using std::vector's iterator or using it's overloaded subscript operator makes no difference either.

If you want to improve preformance/efficiency of your widget toolkit don't use a linear sequence to hold all elements. Typical structure used for widget toolkits is the composite design pattern (think of it like a heterogeneous n-ary tree). With such a structure you have the ability to cull-out entire branches that are logically and/or spatially *grouped* together.

Share this post


Link to post
Share on other sites
How are you identifying each GUI object? Is there some sort of unique identifier associated with each object? I ask this because you could use a hash_map, using the unique identifier as the key. That way, you don't need to iterate through the map, just do a find() and if the item with the id you pass in exists, it will return an iterator to it. It's much faster than iterating through a vector container.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Typical structure used for widget toolkits is the composite design pattern (think of it like a heterogeneous n-ary tree). With such a structure you have the ability to cull-out entire branches that are logically and/or spatially *grouped* together.


Quoted for emphasis, and to throw in a little Command Pattern as well. Command Pattern will allow you to better handle menu events, and also give you an elegant solution for supporting undo/redo operations.

Share this post


Link to post
Share on other sites
Sorry for late reply. I have been out of town for two days.

Quote:

So read/writing/iterating is no different than doing it with an array, whether you where iterating using std::vector's iterator or using it's overloaded subscript operator makes no difference either.

I know. I was iterating through the list content not because it was faster but because it was easier for me to keep track of things. It's hard to explain with a few words.

Quote:

If you want to improve preformance/efficiency of your widget toolkit don't use a linear sequence to hold all elements. Typical structure used for widget toolkits is the composite design pattern (think of it like a heterogeneous n-ary tree).


This 'composite design pattern' sounded scary when I read your posts. I made some google on it and after a short read I realized it's not that frightening as it seemed to be. Thanks for your guidance.

Share this post


Link to post
Share on other sites
I mentioned the hash_map because it's a very fast and efficient way of locating items with unique ids, which is what windows and controls are. When you create your control or window system using a hash_map, you can have a control manager handle the map of the controls.

Something like this:


#include <hash_map>

using namespace stdext; // the hash_map is part of the extensions to the STL

class ControlManager;

// assuming your base control is Control
class Control
{
friend class ControlManager; // give the ControlManager access to my innards!

protected: // protected to prevent anyone outside of the ControlManager to create me! Yet, still be able to have derived classes.
Control();
Control(const Control& ctrl);

public:
...
};

class ControlManager
{
public:
...
unsigned int createControl(...);
Control* getControl(const unsigned int& uControlId);
...

private:
typedef hash_map<unsigned int, Control*> ControlMap;
typedef ControlMap::iterator ControlMapIterator;

ControlMap m_controlMap; // keep your controls here ;)
};

// Then in your createControl function...
unsigned int ControlManager::createControl(...)
{
static unsigned int uLastId = 0;
unsigned int uId = ++uLastId; // supposed to be a pre-increment of uLastId, but the two plus signs aren't showing up. grrrrr

// do any checks to validate any of the parameters passed in
if (/* something is false */)
uId = -1;
else
{
Control* pControl = new Control(...); // create the new control
m_controlMap[uId] = pControl; // put the new control in the hash_map
}

return uId; // return back either the new id for the new control, or -1
}

// Retrieving a control
Control* ControlManager::getControl(const unsigned int& uControlId)
{
// if the iterator doesn't equal the end iterator of the hash_map, then it will contain the pair<unsigned int, Control*> pair
// if it's valid, then doing it->first() will give you the key, which is the unique id, and it->second() will give you the value of that pairing, which is the pointer to that control
ControlMapIterator it = m_controlMap.find(uControlId);
// then, we just need to check to see if the control exists in the map, and return the pointer to it. if it doesn't exist, then return NULL
return (it != m_controlMap.end() ? it->second() : NULL);
}



Notice how the createControl function returns an unsigned int? That would be the unique id for the control that was just created. You could use a unique string as the unique id for the control; but, I find it better to use an unsigned int, as you have millions of possible ids that you could use. The static uLastId is to ensure that each new control being created will have its own id number, and there's no possibility of two or more controls having the same id. Neat, huh? I thought so.

If you take a look at how Ogre3D handles its mapping of objects, its create functions use a unique string as the identifier for the object, and the functions return a pointer to the newly created object. However, it's all based on preference and your design. I, personally, prefer to return the unique id as opposed to passing one in; but, the size of the variable being returned is the same, since an unsigned int and a pointer both take up 4 bytes.

Now, this probably isn't the most efficient way of doing it; but, it's definitely something that might spark an idea or two. :)

Hopefully I've made some sense, and I've actually gotten my code right. I'm still relatively new to hash_maps, so I might've forgotten a couple things. But, something you have to keep aware of is that if you used a std::vector, in order to find a particular control in that container, you have to iterate through the container and test against each control to see if that's the one you want, which could potentially take up a significant amount of time. Whereas, with a hash_map, you only need to call its find function and pass in the unique id you're looking for, and it will go directly there (assuming, of course, that the item you're looking for exists in the map).

It comes down to the order of magnitude for the container. A vector container has an O(n), whereas, the hash_map has an O(1), which is much faster. If you want speed for accessing your controls, I would highly recommend using a hash_map.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!