Linked List for drawing purposes, and others things

AMCerasoli

Aloha,

I was trying to show a little GUI on my game:

And I realize that is time to make the next step, I need a way to use Linked List to "centralize" all my objects, and have a drawing order.

I read an Evert's post and knew that is the way I want to do my game, a Linked List is very powerful and hopefully my final step about the basic concepts of game programming.

As you can see in the video the drawing order is failing, I hope with linked list I can solve this and another problems that I currently have.

But I have a question... How can I pass different types of "data types" to my linked list?

I think I understand it, I modified a piece of code and came up with this, but before I even try it (isn't going to work), I would like to know if this could work, because I saw other examples but they tend to over complicate everything.

How can I achieve this in a simple way?

#SelectExpand
  1class linklist
  2{
  3   private:
  4
  5         struct node{
  6            
  7            void * data;
  8            node *link;
  9         
 10         }*p;
 11
 12   public:
 13
 14              linklist();
 15         void append( int num );
 16
 17};
 18
 19linklist::linklist()
 20{
 21     p=NULL;
 22}
 23
 24void linklist::append(void *num)
 25{
 26     node *q,*t;
 27
 28   if( p == NULL )
 29   {
 30        p = new node;
 31      p->data = num; // This doesn't work but I don't know what to do :S
 32      p->link = NULL;
 33   }
 34   else
 35   {
 36        q = p;
 37      while( q->link != NULL )
 38           q = q->link;
 39
 40      t = new node;
 41      t->data = num;
 42      t->link = NULL;
 43      q->link = t;
 44   }
 45}

Well, I know that I still need to read a lot, but what I would want is a simple way to pass different types of data (made by me) to a linked list

Thanks in advance.

Yves Rizoud

One classic method is to make "data" a pointer to a base class instead of void*, and have all your elements derive from this class.
The good part is that if this base class has a method draw(), you will be able to call (some_node)->data->draw() : it will call the "right method" for each class.

SiegeLord

AMCerasoli said:

How can I achieve this in a simple way?

Use std::list. Specifically, use templates and then use polymorphism (if you want different types of objects in the list). Specialize the template on the parent class of all your objects.

Timorg

The STL is your friend.

#SelectExpand
  1#include <iostream>
  2#include <list>
  3
  4int main()
  5{
  6    int cat = 24;
  7    int dog = 34;
  8
  9    std::list<void *> voids;
 10
 11    // for append
 12    voids.push_back(&cat);
 13    voids.push_back(&dog);
 14
 15    // go through each item in the list
 16    for(std::list<void *>::iterator i = voids.begin(); i != voids.end(); ++i)
 17    {
 18        std::cout << *i << std::endl;
 19    }
 20    return 0;
 21}

The STL library that comes with C++ has a linked list implementation. What data type you store in the linked list is the real question. If you already have an inheritance model with your GUI elements, you could store pointers to them in the list. (You probably don't want to store plain pointers into a list, you will want some sort of smart pointer, so the elements free themselves on removal.)

Edit
A link to an STL container reference probably wouldn't hurt. http://www.cplusplus.com/reference/stl/

AMCerasoli

Thank you very much, I didn't know about that STL (list). I have object that draw themselves, do you think with the std::list I can call functions of each object?

I'm not using inheritance so far, each window of the game is going to do a very different task, so I'm simplifying the process by just creating a new class with its corresponding object.

When I create similar objects a usually use arrays, you know:

PLAYER player[30];

for(int i=0; i<30; i++)
player[i].Draw();

for(int i=0; i<30; i++)
player[i].Logic();

for(int i=0; i<30; i++)
player[i].input(mouseX, mouseY);

I wish I could use that, but so far I haven't had the chance since each object in my game is completely different... So for that reason I want to use list.

but, can I call member functions using std::list?

SiegeLord

AMCerasoli said:

So for that reason I want to use list.

You don't need a list for that. You need to learn some basic C++ OOP.

#SelectExpand
  1class BaseObject
  2{
  3    virtual void Logic();
  4};
  5
  6class Dog : BaseObject
  7{
  8    virtual void Logic();
  9};
 10
 11class Cat : BaseObject
 12{
 13    virtual void Logic();
 14};
 15
 16std::vector<BaseObject*> Objects;
 17
 18Objects.push_back(new Dog());
 19Objects.push_back(new Cat());
 20
 21for(size_t ii = 0; ii < Objects.size(); ii++)
 22    Objects[ii]->Logic(); //will call the methods appropriately depending whether it is a cat or a dog

EDIT: Similarly with a list:

std::list<BaseObject*> Objects;

Objects.push_back(new Dog());
Objects.push_back(new Cat());

for(std::list<BaseObject*>::iterator it = Objects.begin(); it != Objects.end(); it++)
    (*it)->Logic(); //will call the methods appropriately depending whether 

AMCerasoli

hmm.. I know about inheritance, what I did know was that I can create a vector based on the "BaseObject" and then add other objects derived from it.

But I don't like the inheritance way, I prefer having objects completely independent, I know that each objects is going to have a logic and draw functions, but not all objects need a input function... I don't know I really prefer a lot, not using inheritance in this case...

So, I know this sounds pedant, but there is a way to do what I do using inheritance and vectors, but using lists instead?

I would like to have different loops cheeking for different lists...

{"name":"604116","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/2\/c2bd9b4c857d8dec656f2cf7fdef4782.jpg","w":666,"h":583,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/2\/c2bd9b4c857d8dec656f2cf7fdef4782"}

The circles are objects which have different member functions and since I think I can't check them in the same list I create two list to check objects which doesn't have drawing functions and other list for those which have drawing functions... Sounds logic?

Thomas Fjellstrom

You don't need to put Input in the BaseObject. Have three base classes, one called BaseObject, one called Drawable, and one called InputSink, and do something like:

class BaseObject { /* common methods and properties */ };
class Drawable { public: virtual void Draw() { } };
class InputSink { public: virtual void Input() { } };

class MyObject1 : public BaseObject, public Drawable { public: void Draw() { } };
class MyObject2 : public BaseObject, public InputSink { public: void Input() { } };
std::list<BaseObject *> objects;

for(std::list<BaseObject*>::iterator it = objects(); it != objects(); it++) {
    InputSink *input_sink = dynamic_cast<InputSink *>(*it);
    if(input_sink) input_sink->Input();

    Drawable *drawable = dynamic_cast<Drawable *>(*it);
    if(drawable) drawable->Draw();
}

append: and if you want to separate lists based on if they have logic, or whatnot, you can, and you can skip the dynamic_cast (which can be slow).

AMCerasoli

Thanks man!!! I'm seeing "->Input()" and "->Draw()" so certainly this is what I need, I'm going to be studding your code for the next 5 years... It's because I have no time, of course... of course...

Edit: Ok ok... A little one just to be sure. I'm sending pointers to the list, so when I erase an object (a pointer to an object) I'm not calling the destructor since it's a pointer... So... If I want to really destroy an object using list::erase I should create a list of objects instead of a list of pointers to objects right? sounds logic, just to be sure...

PS: Yves Rizoud, really sorry for give you no credits, you was talking about the exact same thing... I didn't realize by that time... I was so stupid.

SiegeLord

AMCerasoli said:

If I want to really destroy an object using list::erase I should create a list of objects instead of a list of pointers to objects right?

If you want to use polymorphism you must use pointers (or references, iirc). To delete all objects from a list of pointers you'd do:

for(std::list<BaseObject*>::iterator it = Objects.begin(); it != Objects.end(); it++)
    delete *it;
Objects.clear();

If you want to delete a specific object:

for(std::list<BaseObject*>::iterator it = Objects.begin(); it != Objects.end(); it++)
{
    if((*it)->Dead)
    {
       delete *it;
       it = Objects.erase(it);
    }
}

AMCerasoli

Man... I love you... Will you merry me? :-*

Thomas Fjellstrom

AMCerasoli said:

Ok ok... A little one just to be sure. I'm sending pointers to the list, so when I erase an object (a pointer to an object) I'm not calling the destructor since it's a pointer... So... If I want to really destroy an object using list::erase I should create a list of objects instead of a list of pointers to objects right? sounds logic, just to be sure...

calling delete on the pointer will call the object's destructor.

AMCerasoli

That's fine Thomas, but I'm not going to marry you... I already ask it to SiegeLord...

Thomas Fjellstrom

AMCerasoli said:

That's fine Thomas, but I'm not going to marry you... I already ask it to SiegeLord...

I was just trying to help, not get in your pants

AMCerasoli

hahahaha Sure Thomas, Sure...

Oscar Giner

I think no one mentioned this: for the deletion to work correctly (call the proper destructors), you should declare the destructor of the base(s) class(es) as virtual (even if they do nothing).

class BaseObject
{
public:
    virtual ~BaseObject() {}   // This is mandatory, even if the body in the base class is empty.
/* common methods and properties */
};

class InheritedObject
{
public:
    ~InheritedObject() {std::cout << "InheritedObject destructor called!" << std::endl;}
};

This way this will work as intended:

BaseObject *obj = new InheritedObject;
...
delete obj;

If BaseObject didn't have a virtual destructor, the line delete obj would only call BaseObject's destructor, and InheritedObject's destructor wouldn't be called. With the base virtual destructor both destructors will be called appropriately.

AMCerasoli

I have check that and it's true!, thank you!... you have just avoid another thread... Damn, I need to find an English forum, I'm taking my English to the top...

PS: Now I understand why Code::Blocks create always a new class with a virtual destructor.

Tobias Dammers

Oh, and here's a bit that I think hasn't been stressed enough:

AMCerasoli said:

So, I know this sounds pedant, but there is a way to do what I do using inheritance and vectors, but using lists instead?

Interface-wise, lists and vectors are almost equivalent. Everything a list can do can also be done with a vector, and a few things more. Which one you choose depends on what you will be doing with it, and the general rule of thumb is:

lots of random insertions and deletions (that is, anywhere other than beginning and end), but no random access: list
front and back insertions, random access: deque
everything else: vector

And here's why: vector and deque outperform list in everything except random insertion / removal, and severely so; especially random access is really really slow with lists (O(n)), which is why STL doesn't even bother implementing it.

So, rule of thumb boiled down:

use vector for everything, until you're seeing performance problems.

verthex

If you look at BSP trees on Wikipedia they explain how it is used for the painters algorithm. Heres an example B-tree in C++, I modified the one on this page.

#SelectExpand
  1
  2#include <stdio.h>
  3#include <stddef.h>
  4#include <stdlib.h>
  5#include "B_tree_class.h"
  6#include "node.h"
  7
  8int main()
  9{
 10  B_tree_class* BTREE;
 11  BTREE = new B_tree_class();
 12  Node root = NULL;
 13    Node head;
 14
 15  BTREE->treeInsertHead(&root,4);
 16  BTREE->treeInsertHead(&root,2);
 17    BTREE->treeInsertHead(&root,1);
 18    BTREE->treeInsertHead(&root,3);
 19    BTREE->treeInsertHead(&root,5);
 20
 21    head = BTREE->treeToList(root);
 22
 23    BTREE->printList(head);
 24
 25    return(0);
 26}

B_tree_class.h

#SelectExpand
   1
   2#ifndef B_TREE_CLASS_H
   3#define B_TREE_CLASS_H
   4#include "node.h"
   5
   6/* The node type from which both the tree and list are built */
   7typedef struct node* Node;
   8/*
   9 helper function -- given two list nodes, join them
  10 together so the second immediately follow the first.
  11 Sets the .next of the first and the .previous of the second.
  12*/
  13
  14class B_tree_class
  15{
  16    private:
  17
  18      Node root;
  19      Node head;
  20
  21    public:
  22
  23    ~B_tree_class(){}
  24    B_tree_class()
  25    {
  26      root = NULL;
  27    }
  28    void join(Node a, Node b);
  29    Node append(Node a, Node b);
  30    Node treeToList(Node node);
  31    Node newNode(int data);
  32    void treeInsertHead(Node* rootRef,int data);
  33    void printList(Node current);
  34};
  35void B_tree_class::join(Node a, Node b)
  36{
  37    a->large = b;
  38    b->small = a;
  39}
  40/*
  41 helper function -- given two circular doubly linked
  42 lists, append them and return the new list.
  43*/
  44Node B_tree_class::append(Node a, Node b)
  45{
  46    Node aLast, bLast;
  47
  48    if (a==NULL) return(b);
  49    if (b==NULL) return(a);
  50
  51    aLast = a->small;
  52    bLast = b->small;
  53
  54    join(aLast, b);
  55    join(bLast, a);
  56
  57    return(a);
  58}
  59/*
  60 --Recursion--
  61 Given an ordered binary tree, recursively change it into
  62 a circular doubly linked list which is returned.
  63*/
  64Node B_tree_class::treeToList(Node node)
  65{
  66    Node aList, bList;
  67
  68    if (node==NULL)
  69    return(NULL);
  70
  71    /* recursively solve subtrees -- leap of faith! */
  72    aList = treeToList(node->small);
  73    bList = treeToList(node->large);
  74
  75    /* Make a length-1 list ouf of the root */
  76    node->small = node;
  77    node->large = node;
  78
  79    /* Append everything together in sorted order */
  80    aList = append(aList, node);
  81    aList = append(aList, bList);
  82
  83  head = aList;
  84
  85    return(aList);
  86}
  87/* Create a new node */
  88Node B_tree_class::newNode(int data)
  89{
  90    Node node = (Node) malloc(sizeof(struct node));
  91    node->set_data(data);
  92    node->small = NULL;
  93    node->large = NULL;
  94    return(node);
  95}
  96/* Add a new node into a tree */
  97void B_tree_class::treeInsertHead(Node* rootRef,int data)
  98{
  99  root = *rootRef;
 100
 101    if (root == NULL)
 102    *rootRef = newNode(data);
 103    else
 104    {
 105        if (data <= root->return_data())
 106      treeInsertHead(&(root->small),data);
 107        else
 108      treeInsertHead(&(root->large),data);
 109    }
 110}
 111void B_tree_class::printList(Node current)
 112{
 113    while(current != NULL)
 114    {
 115        printf("%d ", current->return_data());
 116        current = current->large;
 117        if (current == head)
 118      break;
 119    }
 120    printf("\n");
 121}
 122#endif

node.h

#SelectExpand
  1#ifndef NODE_H
  2#define NODE_H
  3
  4class node
  5{
  6  public:
  7
  8    int data;
  9
 10    public:
 11
 12    node* small;
 13    node* large;
 14
 15    node(){}
 16    ~node(){}
 17    int return_data();
 18    void set_data(int value);
 19};
 20int node::return_data()
 21{
 22  return data;
 23}
 24void node::set_data(int value)
 25{
 26  data = value;
 27}
 28#endif

AMCerasoli

Yhea I could use vectors too, but I don't need random access to my objects, I'm taking OOP to the top, I'm already thinking in how to implement an engine, you know send packages to the engine and retrieve them, and a list is perfect.

cplusplus.com said:

Lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

I think this is perfect for any video game which is using extensively OOP, where objects draw themselves and send packages of data to an engine and vice verse.

Obvisuly I don't need this to my trivia game ::) , I just can't avoid thinking in all this already... I'm even sending the events directly to the objects and they will produce a package of info about their position etc, to perform collision detection and things like that. I think sending event to objects isn't a bad idea. And objects which make use of the keyboard (a character) can use it, another object which needs to only know when to draw and do the logic, is going to do just that.

{"name":"604126","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/7\/679791794e4beadfea7ec752c3c6f12d.jpg","w":470,"h":338,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/7\/679791794e4beadfea7ec752c3c6f12d"}

That way I don't need to call a lot of functions from outside the objects. I want to only call one function ((*)->logic(DATA)) which is going to return a DATA package which is going to be used by the engine and at the same time is going to send the DATA package modified to the object with the info already processed by the engine... I don't know something like that. Probably I will need to call two functions instead of one...

So I send the DATA to the object with the previous state, the object do its logic which involves drawing input etc... and send its current state to the engine again.

Anyway, thank you guys to open my mind, I have learned a lot of thing in these 3 days about C++ I was just learning Allegro Allegro and more Allegro... Actually I already knew them I have study them, but it's like you don't know what to do whit them. It's like yhea I have all this knowledge but then what I do with all this? hahaha it's weird...

I have see the examples but I don't like the way they're done, they use C, and even when C++ is not so different in its syntax, it's very different at the moment of creating a game or a program. Well, at least that I think...

I have see the haiku example it's incredible how in that game al_draw_tinted_scaled_rotated_bitmap() is just called once... in ALL the game, and that is the only drawing call. There are structs inside structs, incredible... but I prefer C++. hohhho

Thread #607301. Printed from Allegro.cc