20 replies to this topic

[lordimmortal2]

I have been trying to make a top-down shooter just for my own experience and want to finish something. Nothing special.

But, as always, something is barring me from progressing any farther and that would be: entity spawning and dynamic memory. I have never worked with dynamic memory beyond that which is required by multiple file projects so I don't have much experience. I'm looking to replace all the static arrays I had that contained information about projectiles, mobs, and the player into a dynamic linked list. The way I have functions set up is that one function is called for entity spawning, a different one for entity moving, another one for collision and so forth. I do not know how to have one global linked list but have it be accessible in different files and in different functions.

The problem I have ran into, obviously, is the problem of how to actually implement such a list. If someone could post a tutorial or something similar on how to do these I would greatly appreciate it. I have read several on linked lists but they're not too good at explaining exactly how you do it, what each piece does, why it works, and how to implement it yourself.

As always, any reply at all is welcome =).

[SiCrane]

Mentioning which programming language you're using would probably be helpful. Most programming languages have linked lists either built in to the language or as part of the standard library. Ex: std::list in C++.

[typedef struct]

// your game entity

class Entity {

};



// a Node contains an Entity and a pointer to the next Node

struct Node {

	Entity entity;

	Node *next;

};



// a list is just a pointer to the first node;

Node *list = NULL;



// add a node to the front of the list

void AddNode(Node *n) {

	if (list) {

 		n->next = list;

	}

	list = n;

}



// remove a node from the list

void RemoveNode(Node *n) {

	// first we have to find the node in front of it

	for (Node *i = list; i; i = i->next) {

 		if (i->next == n) {

          	// i->next points to n

          	i->next = n->next;

          	// now i->next points to the node after n. n isn't in the list any more

          	break;

 		}

	}

}



// add some nodes to our list

for (int i = 0; i < 5; ++i) {

	Node *n = new Node();

	AddNode(n);

}



// loop through the nodes

for (Node *n = list; n; n = n->next) {

	n->entity.Draw();

	// this will not work. try to figure out why

	if (n->entity.IsDead()) {

	 	RemoveNode(n);

	 	delete n;

	}

}

[ApochPiQ]

Your loop is broken. As soon as I delete a node, the next iteration will attempt to access n->next, which dereferences a pointer to freed memory, which is undefined behaviour. If you're exceedingly lucky, it'll crash. Otherwise, worse will happen.

This is why you shouldn't try to write your own linked lists etc. without a very deep understanding of everything you're doing. Rely instead on existing, debugged implementations like std::list in C++.

[typedef struct]

Completely disagree. A linked list is the most fundamental data structure there is, and you should be able to write one blindfolded.

You can't remove from STL data structures while in a loop either, I was just trying to show an example of looping through the list.

[SiCrane]

The waste of time reinventing the wheel every time you need a linked list aside, that's something you're only allowed to say if you can write one correctly. Not only did you have to write four times the amount of code that using std::list would have taken, your code contains at least one major bug, requires more effort to use than std::list, and only allows one linked list in the entire program.

Edit: reponse to added text:

You can't remove from STL data structures while in a loop either

Bullshit. And the problem isn't removing in a loop, the problem is that your node removal code is broken.

[typedef struct]

As I said, you'd have the same problem with STL list.

for (MyList::iterator i = list.begin(); i != list.end(); ++i) {
	if ((*i)->IsDead()) {
		delete *i;
		list.erase(i);
	}
}

would not work either.

Second, he's not reinventing the wheel here. He's writing his first linked list! Are you proposing 1st year CS courses switch to teaching STL list?

If my hastily-written example A* implementation had an error in it, I would not be catching shit, even though there's a perfectly fine implementation in Detour.

GameDev.net, where teaching programming is frowned upon lol

EDIT: There are reasons to use STL. Not knowing how to write a linked list is not among them.

[SiCrane]

A) Just because you don't know how to do something correctly doesn't mean it can't be done.

for (MyList::iterator i = list.begin(); i != list.end();) {
  if ((*i)->IsDead()) {
    delete *i;
    i = list.erase(i);
  } else {
    ++i;
  }
}

B) The problem isn't that removing something in a list in a loop can't be done, the problem is your node removal code is broken. You don't know how to remove a node from a linked list. I'm not suggesting that CS programs shouldn't teach how to write a linked list, I'm saying that YOU have no business suggesting people write their own linked list. You can't even write your own correctly.

If my hastily-written example A* implementation had an error in it, I would not be catching shit

Yeah, and no one claims that you can write an A* implementation "blindfolded". You claimed that everyone should be able to do so with a linked list and then demonstrated that doing so is beyond your capabilities.

[typedef struct]

No, the error is NOT in the RemoveNode function, it was in deleting the node while in a loop.

And of course you CAN remove while in a loop (though I would teach using std::list::remove_if, not that mess of code you posted).

OP, sorry your thread got shat on here. GDev has a lot of inappropriate dogma that gets brought out every time someone asks about C++ functionality provided by STL or Boost. Hopefully my example code was able to teach you something about how linked lists work.

[SiCrane]

No, the error is NOT in the RemoveNode function, it was in deleting the node while in a loop.

Sorry, I got mislead by the fact that you edited your original post so that the discussion would now be about something other than what people could actually see. Funny how that can happen when you remove information in a discussion thread.

You can't remove from STL data structures while in a loop either

As I said, you'd have the same problem with STL list.

And of course you CAN remove while in a loop

Make up your mind. This "inappropriate dogma" pops up when people like you can't even get basic facts and details right about what you call something you can do blindfolded. Is it one of the hardest topics in computer science? No, but it's still more difficult than you make it out to be.

[typedef struct]

Ok, I added the error back in, with a comment so readers won't get confused. I'm not in the habit of leaving bugs in example code. But yes, the error is in the technique of using the linked list, not implementing it, so you would have the same bug when using most implementations, including STL. Oddly enough, C macro based linked lists are the ones most likely to not have this issue!

Number of helpful posts in this thread: 1
Number of reputation points gained: -3

That's what I mean by inappropriate dogma.

[yewbie]

I like to just use a vector to store information, generally for entities when you don't really care about the order, vectors are very nice.
And when one is to be removed I mark it for delete with a bool, then before my loop for iterating through my vector I just remove that entity.

To go into more detail I use a class to make my entity struct, then I create a vector with that class as the vector type.
Then I make another function to make a new instance of that class, fill in the data members, then push_back to the vector.

edit: I also put all of the adding / removing of npcs in another big class that is my entity management class that handles adding, removing, loading, saving, etc.

class NPC
{
	public:
   	int IDNum;				//this is the ID number (this should be unique)
   	int LocX;				//X location
   	int LocY;				//Y location
   	string Name;			//Name of NPC
   	bool MarkForDelete;   	//If we need to delete it before next loop (or skip it during the current loop)
}

vector <NPC> NpcList;

Also looping through a vector and getting a pointer is pretty easy

int NumNpcs = NpcList.size();
for(int npc=0;npc < NumNpcs; npc++) //loop through all npcs
{
	NPC * ThisNpc = &NpcList.at(npc); //get a pointer to this npc so its more friendly to use
	ThisNpc->LocX = 0;
}

edit: to all the above information, I think teaching people is great if they are willing to learn, but if he just wants to use something like std::list that has a lot of built in protections without knowing the in's and out's of everything its doing behind the scenes I don't really see a problem with that.

[rip-off]

Ok, I added the error back in, with a comment so readers won't get confused. I'm not in the habit of leaving bugs in example code. But yes, the error is in the technique of using the linked list, not implementing it, so you would have the same bug when using most implementations, including STL. Oddly enough, C macro based linked lists are the ones most likely to not have this issue!

Essentially, the std::list leaks the underlying linked list behaviour, which is that deleting while iterating is tricky. If you can't do it correctly using the interface std::list provides, you almost certainly won't be doing it right if you do it by yourself. All you are doing is potentially adding additional bugs elsewhere.

Incidentally, your RemoveNode() doesn't appear to work for the head node.

@OP What they really want is a container. The first line of their post is:

I have been trying to make a top-down shooter just for my own experience and want to finish something.

Hand rolling a linked list does not add significantly to that end goal, and in fact will become a hindrance to it.

If you are serious about becoming a computer scientist, I believe you should be able to understand and write a linked list. For finishing your game, it is less of a priority.

[typedef struct]

If you are serious about becoming a computer scientist, I believe you should be able to understand and write a linked list. For finishing your game, it is less of a priority.

I guess I just cannot imagine a situation in which "I am using C++" and "I don't know how to implement a linked list" should both be true.

If you want to use C++, you have to know how to use pointers. If you want to know how to use pointers, you have to know how to write a linked list. I'm pretty sure it's physically impossible to understand pointers without understanding the linked list implementation.

[yewbie]

I'm pretty sure it's physically impossible to understand pointers without understanding the linked list implementation.

For years when I first started as a hobbyist game developer I was using a linked list class that someone else had written and it worked great.
I was using a linked list implementation and pointers without really understanding either.

[rip-off]

If you want to use C++, you have to know how to use pointers.

I wrote a lovely little C++ program in this thread. I'm afraid I didn't use any pointers though.

I agree with the principle, a competent C++ programmer should understand pointers. I also agree that a good litmus test of understanding pointers is implementing a linked list. But we're in For Beginners here, so we're not dealing with experienced C++ programmers. If the OP hadn't emphasised the goal as "getting their game done", I would agree with you. I think people should be capable of writing their own basic data structures before they start using a pre-written one.

[lordimmortal2]

First off, sorry about this being super late. Hope you guys don't mind the giant wall of replies.

Mentioning which programming language you're using would probably be helpful. Most programming languages have linked lists either built in to the language or as part of the standard library. Ex: std::list in C++.

Sorry, I really need to put something in my signature or something that says I'm using C++ 'cause I always forget to mention that =/.

Second, he's not reinventing the wheel here. He's writing his first linked list! Are you proposing 1st year CS courses switch to teaching STL list?

If you are assuming that I'm in a CS course, then I'm not =P. I will be in a couple years but for now my only source of teaching will be the internet and myself. I guess it makes threads like these all the more important =P. ( I just wanted to specify that I'm not doing this for a grade but for my own knowledge).

OP, sorry your thread got shat on here. GDev has a lot of inappropriate dogma that gets brought out every time someone asks about C++ functionality provided by STL or Boost. Hopefully my example code was able to teach you something about how linked lists work.

To the former: won't really affect myself any but if something was wrong with something I'm glad it was pointed out if it means I won't have to spend 2 hours later wondering what's going on. To the latter: It will most definitely help, thanks a lot for your help =D.

edit: to all the above information, I think teaching people is great if they are willing to learn, but if he just wants to use something like std::list that has a lot of built in protections without knowing the in's and out's of everything its doing behind the scenes I don't really see a problem with that.

I don't really know what I want to use but I'll side with whatever I think is most efficient and I can get working in a test program. Thanks for your extra input, it's always welcome to see another take on a subject.

Hand rolling a linked list does not add significantly to that end goal, and in fact will become a hindrance to it.

If you are serious about becoming a computer scientist, I believe you should be able to understand and write a linked list. For finishing your game, it is less of a priority.

Those two things (experience and finishing something) should go hand-in-hand ideally. I want to work on something and finish it to figure out and implement everything I need to start a game and finish it. I would like to know exactly how everything is working, why everything is working, and what things need to be there in order for it to work. In this way, I would like to implement the linked list in my own way first (not copy pasting someone else's code but I would like to use some sorta template to understand what's going on faster). If std::list works I'll probably mess around with that as well as implementing it myself in different ways to see what's better for me.

I guess I just cannot imagine a situation in which "I am using C++" and "I don't know how to implement a linked list" should both be true.

If you want to use C++, you have to know how to use pointers. If you want to know how to use pointers, you have to know how to write a linked list. I'm pretty sure it's physically impossible to understand pointers without understanding the linked list implementation.

Someone else already commented on this but I think I should add my own two cents to the table. I know how pointers work (perhaps not completely, but I know all the basics about them) but there are some logistical issues that crop up for (at least) myself sometimes when I try to view tutorials. I think that any, really experienced programmer should be able to look at some code and work out some of the basic workings at least but since I have never really implemented anything that requires pointers like this and with new things like dynamic memory that I hadn't really dealt with before.

I wrote a lovely little C++ program in this thread. I'm afraid I didn't use any pointers though.

I agree with the principle, a competent C++ programmer should understand pointers. I also agree that a good litmus test of understanding pointers is implementing a linked list. But we're in For Beginners here, so we're not dealing with experienced C++ programmers. If the OP hadn't emphasised the goal as "getting their game done", I would agree with you. I think people should be capable of writing their own basic data structures before they start using a pre-written one.

I agree, this is why I asked for some tutorials and templates.

[lordimmortal2]

Okay so I have pseudo-successfully implemented a linked list to handle all the entities within my game (as in it compiles correctly and executes without a crash at the start, the player spawns and can move around) but I seem to have run into a problem with junk values being placed into the next entity in the list's address even after I set it to 0.

Initialization:

void InitGame()
{
	srand(GetTickCount());

	// Create a root for the player list
	playerRoot = new sEntity;
	playerRoot->ID = ROOT_DEFAULT_ID;
	playerRoot->next = 0;
	

	// Spawn a player struct inside the root list
	playerRoot->SpawnEntity(PLAYER, gwx->Width / 2, gwx->Height + 32, 100, 100, 32, 32);

	// Point the list to player
	player = playerRoot->next;

	player->invulnerable = false;

	// Initialize mob's list root
	entityListMobRoot = new sEntity;
	entityListMobRoot->ID = ROOT_DEFAULT_ID;
	entityListMobRoot->next = 0;

	// Initialize projectile's list root
	entityListProjRoot = new sEntity;
	entityListProjRoot->ID = ROOT_DEFAULT_ID;
	entityListProjRoot->next = 0;
}

The value immediately after it's supposed to be set to 0:


I dunno why it's doing this since the ID is set to 0 and not a junk value correctly. I read that 0xcdcdcdcd is a value specified for released addresses but it hasn't been released yet by my program as it hasn't even been initialized.

As always, any reply and all help is greatly appreciated.

[rip-off]

0xcdcdcdcd is for uninitialised memory. The value -842150451 is also 0xcdcdcdcd, and I'd bet the various float/double values are also 0xcdcdcdcd. Something fishy is going on, from the looks of your code it should be impossible for this situation to occur. Have you tried a clean rebuild?

Your Entity constructor should initialise "next" to 0 however, you shouldn't have to set this yourself. The ID, if required, should be a constructor parameter.

[ongamex]

void DestroyObject(long idx)

{

delete Buffer[idx];

Buffer.erase(Buffer.begin() + idx);return ;

}














This is in my game engine. I use std::vectors for Enitity buffer.But you can get the idea.