[C] Linked lists for manage entities in a game

[Pix3l]

Hello there, I tried to implement a little game engine from scratch, now in particular I was working on a simple system for manage entities in a game.

I declared a simple Entity (node) structure like this, and an head and tail pointers

{l Code}: {l Select All Code}

typedef struct _Entity {
   int id;
   float x, y;
   int w, h;
   struct _Entity *next;
        [...]
} Entity;

Entity *headList, *tailList;

After that, I create every single new entity (node) with this function

{l Code}: {l Select All Code}

void createEntity(int id, int x, int y, int w, int h)
{
   Entity *pnew = (Entity*) malloc(sizeof(Entity));
   
   if(headList == NULL)
   {
      pnew->id = 1;
      headList = pnew;
      tailList = headList;
   }
   else
   {
      pnew->id = tailList->id+1;
      tailList->next = pnew;
      tailList = pnew;
   }

   tailList->next = NULL;
}

After some entities (nodes) are created, I loop over them with a function like this, along with some logical functions:

{l Code}: {l Select All Code}

void doGame()
{
        input();
   movePlayer();
   
   Entity *entity = headList, *temp=NULL, *previous=NULL;
   while(entity!=NULL)
   {
      if(entity->active==1)
      {
         entity->update(entity);
         doEntityGravity(entity);

         if(rectCollision(Player.x, Player.y, Player.w, Player.h,
                       entity->x, entity->y, entity->w, entity->h))
         {
            if(headList==entity)
            {
               headList = entity->next;
            }
            else if(tailList==entity)
            {
               previous->next=NULL;
            }
            else
            {
               
               previous = entity->next;
               free(entity);
               entity = previous->next;
            }
         }
      }      
      previous = entity;
      entity = entity->next;
   }
}

I loop over every entities (nodes) from head to tails, check if they collide with the player and try to destroy them from the list.
I have a problem here in trying to make it all work properly, things work correctly if i destroy the entities in the correct order, from head to tail, but having a segfault if trying to destroy e middle list entity.

Anyone have an idea on how to fix this?
Or is there a best practice for using singly linked lists in games?

[amuzen]

From what I can tell, your node deletion code is not correct:

• When the first node is deleted, it is unlinked but not freed, so it will leak.
• When the last node is deleted, it is leaked similarly. Also, you need to set tailList = previous, or else it wil point to the deleted node.
• When other nodes are deleted, you free the node but do not unlink it from the list. You should do previous->next = entity->next before freeing entity, or else the freed pointer will remain in the list.
• You do not correctly handle the case of there being only one node in the list. You need to set headList = tailList = NULL in this case.

Once you have fixed those, you will have to change the way how you iterate through the list. Otherwise, you will access invalid pointers in some cases:

• After deleting the first node, entity = headList.
• After deleting a node in the middle, entity = previous->next.
• After deleting the last node, break out of the loop.
• When the node was not deleted, previous = entity, entity = entity->next.

No guarantee that I got everything right so you might want to double check with a singly linked list tutorial. There should be quite a few of those around.

[Pix3l]

Thanks for the reply amuzen!

Looking better at my code, I saw some mistakes and missing parts.
I've rearranged the loop to make some more controls on the node to be deleted, helped by some debug output.
Now seems to work! I can delete entities (nodes) in every order without problems, hoping it will be a solution and not just a fluke...

{l Code}: {l Select All Code}

void doGame()
{
        input();
   movePlayer();
   
   Entity *entity = headList, *temp=NULL, *previous=NULL;
   while(entity!=NULL)
   {
      if(entity->active==1)
      {
         entity->update(entity);
         doEntityGravity(entity);

         if(rectCollision(Player.x, Player.y, Player.w, Player.h,
                       entity->x, entity->y, entity->w, entity->h))
         {
            if(previous!=NULL)
               printf("Previous ID %d Current ID %d\n", previous->id, entity->id);
            
            if(entity==headList && entity==tailList)
            {
               printf("Head is equal to Tail! Break!\n");
               free(entity);
               headList=tailList=NULL;
               break;
            }
            
            if(headList==entity)
            {
               printf("head!\n");
               headList = entity->next;
               free(entity);
               entity = headList;
            }
            else if(tailList==entity)
            {
               printf("tail!\n");
               previous->next=NULL;
               tailList=previous;
               free(entity);
               entity = tailList;
            }
            else
            {
               printf("Entity is now ID %d\n", entity->id);
               previous->next = entity->next;
               printf("Previous next will be ID %d\n", entity->next->id);
               entity->active = 0;   //Inattiva (free?)
               free(entity);
               //destroyEntity(entity);
               entity = previous->next;
            }

            printf("id %d\n", entity->id);
         }
      }      
      previous = entity;
      entity = entity->next;
   }
}

I hope this can be good enough and usefull for others game programmers. :]

[Pix3l]

Working on my game project, I noticed some new issues in the linked list handling.

Putting some printf for debugging purpose, I noticed that the nodes in the list are not deleted correctly from the specific function (util.c -> void freeEntities ()) using free ().

{l Code}: {l Select All Code}

$ ./main
New entity HEAD ID 1
New entity TAIL 2
New entity TAIL 3
New entity TAIL 4
New entity TAIL 5
New entity TAIL 6
New entity TAIL 7
New entity TAIL 8
New entity TAIL 9
New entity TAIL 10
New entity TAIL 11
New entity TAIL 12
New entity TAIL 13
New entity TAIL 14
New entity TAIL 15
New entity TAIL 16
New entity TAIL 17
New entity TAIL 18
New entity TAIL 19
---------------------
Destroy entity ID 1 free(0x80e9d28)
Destroy entity ID 2 free(0x8119940)
Destroy entity ID 3 free(0x81199b8)
Destroy entity ID 4 free(0x8119a30)
Destroy entity ID 5 free(0x8119aa8)
Destroy entity ID 6 free(0x8119b20)
Destroy entity ID 7 free(0x8119b98)
Destroy entity ID 8 free(0x8119c10)
Destroy entity ID 9 free(0x8119c88)
Destroy entity ID 10 free(0x8119d00)
Destroy entity ID 11 free(0x8119d78)
Destroy entity ID 12 free(0x8119df0)
Destroy entity ID 13 free(0x8119e68)
Destroy entity ID 14 free(0x8119ee0)
Destroy entity ID 15 free(0x8119f58)
Destroy entity ID 16 free(0x8119fd0)
Destroy entity ID 17 free(0x80ebab8)
Destroy entity ID 18 free(0x811a0b8)
Destroy entity ID 19 free(0x811a130)
List has item with ID 135175752 and address 0x80e9d28
List has item with ID 135175456 and address 0x8119940
List has item with ID 3 and address 0x81199b8
List has item with ID 4 and address 0x8119a30
List has item with ID 5 and address 0x8119aa8
List has item with ID 6 and address 0x8119b20
List has item with ID 7 and address 0x8119b98
List has item with ID 8 and address 0x8119c10
List has item with ID 9 and address 0x8119c88
List has item with ID 10 and address 0x8119d00
List has item with ID 11 and address 0x8119d78
List has item with ID 12 and address 0x8119df0
List has item with ID 13 and address 0x8119e68
List has item with ID 14 and address 0x8119ee0
List has item with ID 15 and address 0x8119f58
List has item with ID 16 and address 0x8119fd0
List has item with ID 17 and address 0x80ebab8
List has item with ID 135179944 and address 0x811a0b8
List has item with ID 19 and address 0x811a130


The allocation is made ​​in the function createEntity () (entity.c) as follows:

{l Code}: {l Select All Code}

void createEntity(int type, int solid, int x, int y, int w, int h,
              int lives, SDL_Surface *sprite, float animation_speed,
              float speed, float gravity, void (*update)())
{
   //calloc alloc and initialize the memory
   //~ Entity *pnew = (Entity*) calloc(1, sizeof(Entity));

   if(headList == NULL)
   {
      headList = (Entity*) calloc(1, sizeof(Entity));
      headList->id = 1;
      tailList = headList;

      //~ pnew->id = 1;
      //~ headList = pnew;
      //~ tailList = headList;
      printf("New entity HEAD ID %d\n", tailList->id);
   }
   else
   {
      tailList->next = (Entity*) calloc(1, sizeof(Entity));
      tailList->next->id = tailList->id+1;
      tailList = tailList->next;
      //~ pnew->id = tailList->id+1;
      //~ tailList->next = pnew;
      //~ tailList = pnew;

      printf("New entity TAIL %d\n", tailList->id);
   }
   
   tailList->next = NULL;
   
   tailList->type = type;
   //~ tailList->solid = solid;
   tailList->x = x;
   tailList->y = y;
   tailList->w = w;
   tailList->h = h;
   tailList->lives = lives;
   tailList->sprite = sprite;
   tailList->animation_speed = animation_speed;
   tailList->speed = speed;
   tailList->gravity = gravity;

   if(update==NULL)
   {
    quit=1;
    printf("Function pointer not initialized!\n");
   }
   
   tailList->update = update;

   //Valori di default
   tailList->active = 1;
   tailList->xstart = x;
   tailList->ystart = y;
   tailList->direction_x = -1;
   tailList->direction_y = 0;
   tailList->visible = 1;
}


I'm not very practical on the dynamic memory management in C, I followed several tutorials about the linked lists and I followed the same steps to create one, but I can not get it to work properly.
I'm running out of ideas ...

If someone wants to and can help me solve the puzzle, you can find the latest version of the test sources here

Thanks in advance :]

[dusted]

You can also use a doubly-linked list, and also to have the list elements contain a "destructor" function which can be set by the using code to automatically free data pointed to by the list.
What will be of main interest to you is the deletion function in my while loop, I set the list iterator to the previous element before removing an element. This requires me to first update my previous and next elements.
Please note, I just wrote this code in the forum editor, it is not a full implementation, just some visible parts to give a general idea

{l Code}: {l Select All Code}

struct listElement
{
  struct listElement* next;
  struct listElement* previous;
  void (*delete)();
  gameEntity* data;
}

//Create a new list
listElement* myList = listNew();
//Create a new game-element
gameEntity* gameObject = createGoblin();
//Add element to list
listAdd( (void*)gameObject, gameObject->delete );

//Iterating and deleting
listElement* iterator = myList;

while( (iterator=iterator->next) )
{
  gameEntity* gameObj = (gameEntity*)(it->data);

  gameObj->think();

  if(gameObj->dead)
  {
    //Because it is a doubly linked list, deletion is as simple as
    // iterator->previous->next=iterator->next; if(iterator->next) { iterator->next->previous=iterator->previous; } if( iterator->delete ) { iterator->delete(); } free(iterator);
    iterator = listDelete( iterator ); //Delete should return a pointer to the previous element (this can always succeed since the first elemnt of the list is a unused "header" simply pointing to the first element containing data).
  }
}

[Pix3l]

Really interesting your approach, perhaps I'll include it in my project RetroGear.
Thanks for the reply anyway

[dusted]

Ooh, retrogear looks interesting