Back to General and Gameplay Programming

Linked Lists

General and Gameplay Programming Programming

Started by JSCFaith May 12, 2001 06:37 PM

29 comments, last by JSCFaith 23 years, 9 months ago

jwalker

122

May 13, 2001 07:10 AM

oh yeah .. forgot about the double. . thanks

Anonymous

May 13, 2001 08:00 AM

Actually, a more accurate way would be to check wheter it''s the last node, first node, or in the middle...
Since it can also be in the middle, you need to first find it by its index...

Here''s my code:

t Remove (int index) {    int i;    CNode* pNode;      if(index < 0) {         //negative index starts from the end        // (eg. an index of -1 means the last node)        pNode = pLast;        for(i = 0; i < -(index+1); i++)             pNode = pNode->pPrev;     }            else {        pNode = pFirst;        for(i = 0; i < index; i++)             pNode = pNode->pNext;    }        t Value = pNode->Value;    CNode* pNextNode = pNode->pNext;    CNode* pPrevNode = pNode->pPrev;    if(pPrevNode)        pPrevNode->pNext = pNextNode;      if(pNextNode)        pNextNode->pPrev = pPrevNode;    if(pFirst == pNode) { //Check if it''s the only node        pFirst = NULL;        pLast = NULL;            }    delete pNode;    return Value;}

Ofcourse, It could be written better, But that''s about it for this example...

Stoffel

250

May 13, 2001 02:54 PM

Not to flame, but that's a horrible example. You never, ever, ever want to have to traverse a linked list on an insert or delete operation. That's the whole reason you use linked lists instead of arrays.

Since it's Sunday and I'm avoiding my research project, I decided to make this class work. Here ya go, with some minor changes, including fixing the linked lists:

  #include <stdio.h>#include <stdlib.h>#include <cassert>class Bullet{public:    static void CreateBullet (float x, float y, int Direction);    static void RemoveDeadBullets ();    static bool AreBulletsLeft () { return s_pBulletFirst != NULL; }private:    Bullet (float x, float y, int Direction);    ~Bullet ();    float m_x, m_y;    int m_direction;    Bullet *m_pBulletPrev, *m_pBulletNext; // per-bullet pointers    static Bullet *s_pBulletFirst, *s_pBulletLast; // per-list pointers};// define & initialize static class membersBullet *Bullet::s_pBulletFirst = NULL;Bullet *Bullet::s_pBulletLast = NULL;void Bullet::CreateBullet(float x, float y, int Direction) {	    Bullet *NewBullet;	    NewBullet = new Bullet (x, y, Direction);}// The class Bullet's constructor adds bullet to linked listBullet::Bullet(float x, float y, int Direction) :m_x (x), m_y (y), m_direction (Direction){	    // Add to linked List    if( s_pBulletFirst == NULL )    {        // this is the first node        s_pBulletFirst = s_pBulletLast = this;        m_pBulletPrev = m_pBulletNext = NULL;    }    else    {        Bullet *pOldLast = s_pBulletLast; // old last bullet        assert (pOldLast->m_pBulletNext == NULL); // sanity check        // link old last bullet with this bullet        pOldLast->m_pBulletNext = this;        m_pBulletPrev = pOldLast; // this-> is implicit        // link this bullet with static last stub        m_pBulletNext = NULL; // it's the end--nothing next        s_pBulletLast = this;    }	}Bullet::~Bullet (){    if (s_pBulletLast == this)        s_pBulletLast = m_pBulletPrev; // last is now bullet before this    if (s_pBulletFirst == this)        s_pBulletFirst = m_pBulletNext; // first is now bullet after    // note--if this was last bullet in list, and both last and first    // were set to this bullet, last & first should now be NULL    // if there's a next entry, set its prev to the prev of this bullet    if (m_pBulletNext)        m_pBulletNext->m_pBulletPrev = m_pBulletPrev;    // if there's a prev entry, set its next to next of this bullet    if (m_pBulletPrev)        m_pBulletPrev->m_pBulletNext = m_pBulletNext;}void Bullet::RemoveDeadBullets (){    // in real code, you would remove bullets that have "hit" or gone off    // the screen.  For the purpose of experiment, just remove a random    // bullet    Bullet *pBullet = s_pBulletFirst;    while (pBullet)    {        if (rand () % 2) // 50/50 odds to delete each        {            Bullet *pNextBullet = pBullet->m_pBulletNext; // save next bullet            delete pBullet; // hasta            pBullet = pNextBullet;        }        else            pBullet = pBullet->m_pBulletNext; // advance to next bullet    }}int main (){    srand (0);    for (int i=0; i<20; ++i)        Bullet::CreateBullet (i + 1.0f, 20.0f-i, rand () % 4);    i = 0; // use i to check how many times it takes to delete    while (Bullet::AreBulletsLeft ())    {        Bullet::RemoveDeadBullets ();        ++i;    }    return i;}

On my machine, it takes 5 loops through RemoveDeadBullets to get them all with a seed of 0 (should work that way with everyone who has the same MSVC rand function). You can go through manually and ensure there are no leaks, or use a static counter to convince yourself, but this program works.

I didn't find any errors in your constructor from the code given, though some things that I put as static you may not have. You'll notice that I preface member variables with "m_" and static members with "s_" to keep them straight; this is (IMHO) a good style habit.

Also IMHO, this is bad object-oriented design. A bullet shouldn't know that it's part of a list; it shouldn't care if it's in a list or vector or hash table. All it should know is that it's a bullet. There should be no list information in the bullet class. Furthermore, you'll have to regenerate this linked list code for every class that's part of a list if you use this style.

A solution using the STL would be to make a bullet manager tat coordinates the list, and remove all list code from the bullet ctor and dtor:

    class BulletManager{private:  static list<Bullet*> s_list;public:  static void CreateBullet (Args args)  {    s_list.push_back (new Bullet (args));  }  static void RemoveDeadBullets ()  {    list<Bullet*>::iterator it = s_list.begin ();    while (it != s_list.end ())    {      if (it->IsDead ())      {        delete *it; // delete Bullet *        it = s_list.erase (it); // remove record from list      }      else        ++it; // go to next bullet    }  }};

You could, of course, substitute your own class for std::list, but that would be the "correct" OOP way to solve this problem.

Edited by - Stoffel on May 13, 2001 3:56:20 PM

JSCFaith

Author

122

May 13, 2001 05:30 PM

Hey,

Well this is my first time using classes, linked lists, and the 'new' & 'delete' in a full featured program all together. I am a rather new programmer and I want to clerify a few things. First, what is the 'std::list' thing you are referncing too in your post. Also, you say the 'Bullet' should not know its in a list. How do you mean? What is in my code that makes the bullet know its in a list? I am still trying to grasp this OOP stuff. Being only fourteen I have plenty of time to figure it out. Well if you could clerfy those things it would be appreciated.

Oh, one more thing. I went on MSDN and looked up which you include at the top. I didn't find much information on it. Is that where the 'std' class is? Well thanks a lot for the help. I will continue studying your code help me better my own code and fix the problem.

Thanks..

Edited by - JSCFaith on May 13, 2001 6:50:41 PM

ldespot

122

May 13, 2001 05:59 PM

std::list refers to the STL (Standard Template Library) version of a list class. Just do a seach on list in the help and pick the ones pertaining to the C/C++ language. I would highly suggets picking up a good C++ book that explains STL and templates in detail.

JSCFaith

Author

122

May 13, 2001 06:06 PM

Thanks, I will look into that.

Later..

DeVore

122

May 13, 2001 06:07 PM

the std::list is a standard library implementation of a linked list using c++ templates. Basically, what it means is that you don''t need to go to all of the trouble of writing your own linked list - it''s an often used data structure and that''s why it''s in the std lib. However, it''s a good idea to write one yourself at least once so that you understand how they work.

oop: I think what Stoffel meant by saying that your bullet shouldnt know it''s in a linked list is this: To properly abstract your bullet, you should just have your bullet class containing bullety things - like where it is and how it''s position is updated and what sort of thing it does when it hits something. In your bullet class you have also included the information about other bullets. ie, Your bullet knows about linked lists. So, to clean your design up, you could have your bullet knowing only about things pertinent to itself and a controller class whose job it is to manage the storeage (creation and deletion) of bullet objects. This could mean that when later you learn about a more appropriate way to store your bullets(maybe) you just change your manager class and the bullet class stays the same.
Of course, this is subjective (as design stuff always is) but i think Stoffel has a reasonable point in this instance.

my 2p
DeVore

JSCFaith

Author

122

May 13, 2001 06:37 PM

Hey

Well thanks for your help guys. DeVore you said that the bullet shouldn't know it is in a list and that I should have a bullet manger class or something. So you mean this:

    // Simplified Bullet Classclass Bullet : GameObject {Bullet() {// add to linked list}~Bullet() {// remove from list}// Bullet stuffprotected:int damage;int range;}// Manager Classclass BulletManager {public:BulletManager() {// basic initialization}~BulletManager() {// basic deinitialization}DrawBullets(); // Goes through the linked list and draws all the bullets that are ALIVECreateBullet(); // duhDestroyBullet(); // Destroys any Bullets that are DEADCheckBulletCollisions();// duhprotected:}

So, something like that? Where all the bullet object has is the information about the bullet. And then you create one BulletManager object that takes care of Drawing the each bullet, destroying, creating, checking collisions and stuff? Is that what you mean? This has been a question I have had for a while. Should I have the bullet class handle managing each bullet or another class? I could never quite figure out what I should do. Well thanks for the clerification guys.

Hasta Luego..

Edited by - JSCFaith on May 13, 2001 7:44:47 PM

JSCFaith

Author

122

May 13, 2001 08:35 PM

Hey,

Well I am trying to get the program to work. The program works fine if I do this...

Bullet Bullets[40];

...but when I try this...

Bullet *NewBullet;

NewBullet = new Bullet;

... it crashes. Here if my two complete classes that make up the bullets:

  class Bullet : public GameObject {public:	Bullet(int BulletDamage, int BulletRange) {		Type = BULLET;		Damage = BulletDamage;		Range = BulletRange;		DistanceFlown = 0;		// Add to linked List		if( pBulletFirst == NULL )		{			// this is the first node			pBulletFirst = this;			pBulletFirst->pBulletPrev = NULL;		}		else		{			pBulletLast->pBulletNext = this;			this->pBulletPrev = pBulletLast;		}		pBulletLast = this;		this->pBulletNext = NULL;		}	~Bullet() {		if (pBulletPrev == NULL) 			pBulletFirst = pBulletNext;		else			pBulletPrev->pBulletNext = pBulletNext;		if (pBulletNext == NULL)			pBulletLast = pBulletPrev;		else			pBulletNext->pBulletPrev = pBulletPrev;	}	int Draw(LPDIRECTDRAWSURFACE7 PrimarySurface);	//. Sets the damage	void SetDamage(int NewDamage) {		Damage = NewDamage;	}	// Set Velocity	void SetBulletVelocity(int Direction);	// Gets the Damage	int GetDamage() {		return Damage;	}	Bullet *GetNextBullet() {		return(pBulletNext);	}	Bullet *GetPrevBullet() {		return(pBulletPrev);	}	static Bullet *GetFirstBullet() {		return(pBulletFirst);	}	static Bullet *GetLastBullet() {		return(pBulletLast);	}	int GetDistanceFlown() {		return DistanceFlown;	}	void AddOneDistanceFlown() {		DistanceFlown++;	}	int GetRange() {		return Range;	}			protected:	// Linked list stuff	static Bullet *pBulletFirst;	static Bullet *pBulletLast;	Bullet *pBulletNext;	Bullet *pBulletPrev;	// Bullet Damgae	int Damage;	int Range;	int DistanceFlown;};class BulletManager {public:	BulletManager() {	}	~BulletManager() {	}	void CreateBullet(float x, float y, int Range, int Damage, int Direction);	void CheckBulletCollisions();	void DrawBullets(LPDIRECTDRAWSURFACE7 PrimarySurface);	void RemoveDeadBullets();	void MoveBullets();	void ManageBullets(LPDIRECTDRAWSURFACE7 PrimarySurface);protected:};// Now here is the code I call that failsvoid BulletManager::CreateBullet(float x, float y, int Range, int Damage, int Direction) {	Bullet *NewBullet;	NewBullet = new Bullet(Damage, Range); // This Right here. 	NewBullet->SetPosition(x,y);	NewBullet->SetObjectState(ALIVE);	NewBullet->SetBulletVelocity(Direction);	NewBullet->SetSize(4, 4);	NewBullet->SetAnimationProperties(8, 8, 1, 1, DDSCAPS_VIDEOMEMORY, "Data\\Art\\Weapons\\bullet");	NewBullet->SetFrame(1);}

I commented out everything and it worked, but the very second I uncommented that line of code I showed you, it would crash evertime it was run. I tried doing this with other classes like my Asteroid Class and the exact same thing happens. I am using VC++ 6.0.

Well I hope someone can help. Thanks.

DeVore

122

May 14, 2001 06:22 AM

I''m just wondering if you are initialising your static pointers to the head and tail of the list to NULL. They don''t necessarily get created pointing to NULL.

use something like:
#define NULL 0

Bullet::pBulletFirst = NULL;
Bullet::pBulletLast = NULL;

(I think it''s something like that)

I think you missed the point of seperating the bullet and list code. The manager class should do the list stuff. The bullet class should have no list stuff in it at all.

class manager {
private:
// list pointers
public:
void createBullet(...) {
// add new bullet to linked list
}

...
}

hope it helps...
DeVore

ps: A debugging idea - create a test project for this class and run it in a console using cout to print debug statements. Don''t use the drawing functions, just check that things get created and deleted properly. look at the pointers etc...
Test it bit by bit. first try to create one bullet and then delete it using your list functions. Then create a couple etc... delete the first one, delete one from the middle and end of the list. Try out all of the cases your code can encounter.

Linked Lists

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Linked Lists

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines