Sign in to follow this  
lordimmortal2

Linked List/Entity Spawning

Recommended Posts

lordimmortal2    130
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 =).

Share this post


Link to post
Share on other sites
SiCrane    11839
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++.

Share this post


Link to post
Share on other sites
CadetUmfer    234
[code] // 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;
}
}[/code]

Share this post


Link to post
Share on other sites
ApochPiQ    23003
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 [i]very[/i] deep understanding of everything you're doing. Rely instead on existing, debugged implementations like std::list in C++.

Share this post


Link to post
Share on other sites
CadetUmfer    234
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.

Share this post


Link to post
Share on other sites
SiCrane    11839
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 [i]correctly[/i]. 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:
[quote name='typedef struct' timestamp='1308834629' post='4826759']
You can't remove from STL data structures while in a loop either
[/quote]
Bullshit. And the problem isn't removing in a loop, the problem is that your [i]node removal code is broken[/i].

Share this post


Link to post
Share on other sites
CadetUmfer    234
As I said, you'd have the same problem with STL list.
[code]for (MyList::iterator i = list.begin(); i != list.end(); ++i) {
if ((*i)->IsDead()) {
delete *i;
list.erase(i);
}
}[/code]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.

Share this post


Link to post
Share on other sites
SiCrane    11839
A) Just because [b]you [/b]don't know how to do something correctly doesn't mean it can't be done.
[code]
for (MyList::iterator i = list.begin(); i != list.end();) {
if ((*i)->IsDead()) {
delete *i;
i = list.erase(i);
} else {
++i;
}
}
[/code]
B) The problem isn't that removing something in a list in a loop can't be done, the problem is [b]your node removal code is broken[/b]. 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.
[quote]
If my hastily-written example A* implementation had an error in it, I would not be catching shit
[/quote]
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.

Share this post


Link to post
Share on other sites
CadetUmfer    234
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.

Share this post


Link to post
Share on other sites
SiCrane    11839
[quote name='typedef struct' timestamp='1308837005' post='4826778']
No, the error is NOT in the RemoveNode function, it was in deleting the node while in a loop.
[/quote]
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.
[quote name='typedef struct' timestamp='1308834629' post='4826759']
You can't remove from STL data structures while in a loop either
[/quote]
[quote name='typedef struct' timestamp='1308835714' post='4826771']
As I said, you'd have the same problem with STL list.
[/quote]
[quote name='typedef struct' timestamp='1308837005' post='4826778']
And of course you CAN remove while in a loop[/quote]
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.

Share this post


Link to post
Share on other sites
CadetUmfer    234
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 [i]using[/i] the linked list, not [i]implementing[/i] 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.

Share this post


Link to post
Share on other sites
yewbie    677
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.

[code]
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;

[/code]

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

[code]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;
}[/code]

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.

Share this post


Link to post
Share on other sites
rip-off    10976
[quote]
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!
[/quote]
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:
[quote]
I have been trying to make a top-down shooter just for my own experience and want to finish something.
[/quote]
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.

Share this post


Link to post
Share on other sites
CadetUmfer    234
[quote name='rip-off' timestamp='1308839777' post='4826807']
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.
[/quote]

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.

Share this post


Link to post
Share on other sites
yewbie    677
[quote name='typedef struct' timestamp='1308841103' post='4826821']
I'm pretty sure it's physically impossible to understand pointers without understanding the linked list implementation.
[/quote]

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.

Share this post


Link to post
Share on other sites
rip-off    10976
[quote]
If you want to use C++, you have to know how to use pointers.
[/quote]
I wrote a lovely little C++ program in [url="http://www.gamedev.net/topic/604552-two-random-cards-random-but-there-the-same/page__view__findpost__p__4826783"]this thread[/url]. 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.

Share this post


Link to post
Share on other sites
lordimmortal2    130
First off, sorry about this being super late. Hope you guys don't mind the giant wall of replies.

[quote]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++.[/quote]

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 =/.

[quote]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?[/quote]

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).

[quote]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.[/quote]

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.

[quote]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. [/quote]

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.

[quote]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.[/quote]

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.

[quote]
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.[/quote]

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.

[quote]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.[/quote]

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

Share this post


Link to post
Share on other sites
lordimmortal2    130
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:
[code]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;
}[/code]

The value immediately after it's supposed to be set to 0:
[img]http://i53.tinypic.com/v43ozs.jpg[/img]

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.

Share this post


Link to post
Share on other sites
rip-off    10976
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.

Share this post


Link to post
Share on other sites
ongamex    102
[font="Consolas"][size="2"][font="Consolas"][size="2"][/size][/font]

[/size][/font][size="2"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"]void[/color][/font][/color][/font][/color][/font][font="Consolas"][font="Consolas"] DestroyObject([/font][/font][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"]long[/color][/font][/color][/font][/color][/font][font="Consolas"][font="Consolas"] idx)[/font][/font][/size]

[font="Consolas"][size="2"][font="Consolas"][size="2"] {[/size][/font][/size][/font]

[size="2"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"]delete[/color][/font][/color][/font][/color][/font][font="Consolas"][font="Consolas"] Buffer[idx];[/font][/font][/size]

[font="Consolas"][size="2"][font="Consolas"][size="2"] Buffer.erase(Buffer.begin() + idx);[/size][/font][/size][/font][size="2"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"]return[/color][/font][/color][/font][/color][/font][font="Consolas"][font="Consolas"] ;[/font][/font][/size]

[font="Consolas"][size="2"][font="Consolas"][size="2"] }

[/size][/font][/size][/font]












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

[size="2"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"][font="Consolas"] [/font][/color][/font][/color][/font][/size]

[size="2"][font="Consolas"][color="#0000ff"][font="Consolas"][color="#0000ff"][font="Consolas"] [/font][/color][/font][/color][/font][/size]

Share this post


Link to post
Share on other sites
yewbie    677
[quote name='ongamex' timestamp='1309188627' post='4828281']
[font="Consolas"] [/font]This is in my game engine. I use std::vectors for Enitity buffer.But you can get the idea.
[/quote]

I do the same exact thing =p

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