• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Vincent_M

Generic Datatypes --Are Templates the Way to Go?

12 posts in this topic

I developed my own linked list for C++ that has a few features in it that I like over STL lists. The idea is that I have this abstract LinkedItem class, which holds pointers to the previous and next element in the linked list. Then, I have the LinkedList class that manages this class. LinkedList is able to add and remove elements, and more importantly, get an element from a specific index. LinkedItem also contains a virtual method, GetType(), that returns a literal string, and LinkedList contains a "key" field, which is also a string. When LinkedItem is subclassed, GetType() should be overridden to return some other unique string, such as "item_definition", "character_definition", "map_character", etc. and LinkedList instances with the matching key will allow only LinkedItem subclasses with the matching type to be added to the list. That way, it's guaranteed. I think templates might be an even smarter way to go, but I'm not sure how to use them yet...

 

Here is another example:

LinkedItem and LinkedList also also subclassed by DictionaryItem and Dictionary, respectively. DictionaryItem provides an additional "name" field, and when Dictionary attempts to add a DictionaryItem to the list, it'll check the name field against items currently in the list to make sure it's unique (checking duplicates can be turned off, though).

 

Then, I have the last subclassed pair: UniqueItem and UniqueList. When an item is successfully placed into the list, a unique number, called "primaryKey", is generated, and stored in that item.

 

I have all three classes working, but a lot of casting is required to make it work... I plan on using these three classes, mainly Dictionary, as an abstract class where I can override my ValidateAdd method to implement further code for the situation. But then, if I was to use GetItem() to retrieve anything, it'd return abstract datatypes depending on the base class that implemented them.

 

For example:

LinkedItem *GetItem(int index); // implemented by LinkedList
DictionaryItme *GetItem(string name); // implemented by Dictionary

If I were to make a Dictionary subclass called CharacterController, that managed a list subclassed DictionaryItem's called Character, then GetItem(int) and GetItem(string) would return LinkedItem and DictionaryItem pointers of the actual Character instance actually there. I could write wrapper methods, but that seems messy.

 

Would templates work for this situation?

 

1

Share this post


Link to post
Share on other sites

Okay, this is an paradigm for implementing containers that I recently came across:

struct list_item { list_item *prev, *next; };
struct list {
list_item* head; // list of list_items
void add(list_item* item);
list_item* get(void);
};

To have a list of objects of type, say, my_widget, you derive from list_item:

struct my_widget : list_item { /* inherits prev, next pointers */ };

Additionally, you derive from list to hide casting:

struct my_widget_list : list {
// note how my_widget_list acts as a filter
void add(my_widget* item) { list::add((list_item*)item); }
my_widget* get() { return (my_widget*)list::get(); /* safe cast, only my_widgets in the list! */ }
};

Okay, great! But you certainly don't want to write a XXX_list class for every possible type XXX by hand. Luckily these classes can

be easily generated with templates:

template<class T>
struct concrete_list : list {
void add(T* item) { list::add((list_item*)item); }
T* get() { return (T*)list::get(); }
};

Okay, the code has probably some errors in it, but you get the idea how to hide the casting

and get pointers to derived types.

 

By the way, list implementations like these are often(?) called intrusive lists.

So you can ask Google how other people solved this.

2

Share this post


Link to post
Share on other sites

Yes, these are "intrusive lists" and I would use caution when deriving from a type to add 'next' and 'prev' pointers to your object. What do you do when you want the object to be in more than one list? Also, how do you keep code from looking confusing - going this route, if you add an object to a list, you have to remember you're implicitly removing it from any list it was in previously.

2

Share this post


Link to post
Share on other sites
First of all as rdragon1 points out, that's a rather poor design for a list. Usually list containers are implemented as a bunch of nodes that contain the element held. The element type can vary, so this requires a class template.

Secondly, it sounds like it would be more fitting for CharacterController to contain a Dictionary, but have it's own methods that cast the dictionary elements to the proper type.
0

Share this post


Link to post
Share on other sites

Boost has intrusive containers: http://www.boost.org/doc/libs/1_54_0/doc/html/intrusive.html.  They have their uses but I usually prefer the standard containers for most things.  They're generally most useful when you want an item to belong to multiple lists, or if the items are large, or have special construction, destruction, copying, or moving constraints that renders them unusable to normal containers.

0

Share this post


Link to post
Share on other sites

I would consider all the things you've mentioned as downsides compared to the standard containers. Having to derive from a given superclass is something I like to avoid. The "get type" idea sounds brittle and pushes what could be compile time checks to runtime string comparisons. Providing a "get by index" member function means you probably are trying to use linked lists where a dynamic array would be more appropriate. The dictionary appears to be a case of using linked lists where a sorted list, sorted tree or hashing data structure would be more appropriate. There seems to be a lot of inheritance for no real reason.

 

To directly answer your question, yes templates would be the recommended way to do this. This kind of code is party why templates were added to the language.

 

It is fun to write your own containers as a learning experience. But I would not recommend using them. I would recommend you try build your game on top of the standard containers instead. You should be able to implement CharacterController easily in terms of std::vector<> and/or std::map<>, if you simply want to be able to look characters up by name and "index".

2

Share this post


Link to post
Share on other sites

I think the concrete_list is something along the lines of what I was originally aiming for, but there were quite a few good points brought up about using standard containers over building my own intrusive ones.

 

The reason I wanted my own type of lists is mainly due to std::list iterators. Having to declare an iterator every time I want to get to a specific element is just plain annoying. It takes like 3 or 4 lines of code to get to that specific element I already know I want. I've thought about vectors since I'd be able to refer to my elements by index, but then everything's aligned in memory. Although memory alignment has its benefits, adding elements to a vector could cause the entire array to relocate in memory to ensure everything is memory-aligned. This can be slow when adding data --especially larger elements.

 

Honestly, though, the current code base uses an old version of LinkedList called Collection and CollectionItem which did everything that Dictionary does. Just about everything was built on top of the use Collection and CollectionItem. Back then, Collection wasn't inherited either; it was used as a field per class and had wrappers to add, remove, clear and get everything. Lots of redundant code...

 

I'll try my luck with map and see how it works for me. Looks like it'll be my heavy hitter for most things.

0

Share this post


Link to post
Share on other sites

The reason I wanted my own type of lists is mainly due to std::list iterators. Having to declare an iterator every time I want to get to a specific element is just plain annoying. It takes like 3 or 4 lines of code to get to that specific element I already know I want. I've thought about vectors since I'd be able to refer to my elements by index, but then everything's aligned in memory. Although memory alignment has its benefits, adding elements to a vector could cause the entire array to relocate in memory to ensure everything is memory-aligned. This can be slow when adding data --especially larger elements.

Sounds like a use case for std::deque. It has an index operator, and in blocks of continuous memory, so it has most of the benefits of a vector (like good cache performance), but it won't reallocate the whole thing when it grows in size.
0

Share this post


Link to post
Share on other sites

LinkedList is able to add and remove elements, and more importantly, get an element from a specific index.

That's rather unfortunate that you have done that, because giving a linked-list the ability to access items by index is generally regarded as a design blunder.

It turns any innocent loop using such functionality into a Schlemiel the Painter's algorithm.

 

LinkedItem and LinkedList also also subclassed by DictionaryItem and Dictionary, respectively. DictionaryItem provides an additional "name" field, and when Dictionary attempts to add a DictionaryItem to the list, it'll check the name field against items currently in the list to make sure it's unique (checking duplicates can be turned off, though).

Generally this is a further mistake. using a linked-list for dictionary-based lookup causes every lookup to be O(n), which get slow very quickly as the number of items increases. It again leads to more occurrences of Schlemiel the Painter's algorithm.

 

There is a very good reason that the standard library does not do any of this. It totally kills performance for any half decent usage of the container. For containers where key-based lookups are required, you want such an operation to be at most O(sqrt n), and ideally O(1). Typically O(log n) is chosen.
As much as you have a personal attachment to these features that you believe are useful, or even needed, you do need to accept that your implementation will be vastly inferior to the standard C++ library. Your best bet is to spend more time understanding the standard library containers, and come to a better appreciation of just how brilliant they really are.

 

Would templates work for this situation?

Templates are the solution to making a container generic.
 

1

Share this post


Link to post
Share on other sites

Unlike everybody else at Gamedev I am one of those guys who want to use both templates and inheritance at once so that I can replace the generic ItemContainer with different implementations and see how well they perform.

 

Many people have said that it doesn't make sense to do it.

Probably they are right when you can afford to invest time in reading the documentation and doing the math (as opposed to using trial and error).

 

What I'd like to add is that you will probably run into problems when you try to use both static and dynamic polymorphism in C++.

If you decide to still go for it ... maybe because you worked with another language that way and liked keeping things generic ... you should know that it might not be possible to work that way in C++.

0

Share this post


Link to post
Share on other sites

I have decided against using LinkedList/Item, etc. Many good points were brought up, and it's totally convinced me that vector and map are by far, the best solutions. Looking up by index is indeed a slow, iterative process, and the STL seems to do what is needed. It turns out that this Collection system I started using two years ago is a bad habit, and now that I have time to implement map over CollectionItem/Dictionary, things are coming along well! In fact, it seems that using map has even cut down the amount of wrapper code I need to write every time I use a map.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0