Subject: A method for sprite animation (long)

From: [email-masked] (Richard Theodore Caners)
Date: 13 Sep 1994 23:01:51 GMT

Hi, what follows is a text file I wrote describing a method of
sprite animation I am using in a game.  I hope people find it
informative.

A SIMPLE METHOD FOR SPRITE ANIMATION

By Darren Gyles
* [Shameless Plug] 
  Author of HOOP 
  ( Avaliable at  ftp.funet.fi /pub/msdos/games/cards/hoop11.zip )

Note : The following implementation of sprite animation uses linked lists
fairly extensively.  If you are not familiar with this concept, get any
first year computer science textbook and look into it.

I have recently been programming a simple Galaxian type shoot-em-up and
needed a method for sprite animation.  This is the solution that I came up
with.  I was fairly pleased with the results.  I'm sure that this method is 
not unique, but I haven't seen anybody mention it before so I will take
a stab at it.

I am assuming that you already have your sprite graphics routines written.
I will not cover machine specific graphics routines, just algorithms for 
implementing sprites. 

This document describes a simple sprite system and then expands this
system to include animation.  Be forewarned that even though there is
quite a bit of code given, you will never get it to work unless you
understand the methods completely.  It is really not very hard, the 
most confusing thing are the linked lists.  Good luck.

THE BASIC IDEA BEHIND SPRITE ANIMATION

The basic idea behind sprite animation (or any animation, for that matter) 
is:

     Show frame 1 -> wait delay period -> Show frame 2 -> delay -> etc..

Pretty simple, but how do you implement this?

                          - IMPLEMENTATION -

GENERAL SPRITE STUFF

For this discussion I will assume you have a linked list of sprites, and
each node in the list represents a sprite and contains all the information
relevant to that sprite (of course you could use an array for this as well
with some simple modifications).  I am using C type pseudo code - I hope
that everybody can understand it.

Each node may look like:

struct sprite {

   int      xpos, ypos;     // X and Y coordinates for sprite
   int      xspeed, yspeed; // X and Y speed of sprite
   int      type;           // Type of sprite (ie 1 = ship, 2 = bullet etc..)
                            // These types will be defined by you
   char     background[256];
                    // Stores the piece of the background 
                    // that this sprite covers
   .
   .    // Various other parameters describing the sprite that you may 
   .    // require.
   .    // (ie does the sprite collide with other sprites?,
   .    //     does the sprite bounce around or just disappear at edge of
   .    //     the screen?  etc.. )
   .
   struct sprite  *next;  // Pointer to next sprite (NULL means end of list)

};

And you will have a pointer to the top of this list:

    struct sprite *sprite_list;

So you will have a list that looks like this:

sprite_list --> Sprite Data    /----> Sprite Data     /-->NULL
                Next ---------/       Next  ---------/

NOTE: For simplicity, I am assuming that all sprites are the same size.
Which is a dumb assumption, but it should be pretty easy to alter
these functions to work with variable sized elements.

You should have an add_sprite() function and a delete_sprite() function 
(which are not given here, but are pretty simple) which add and delete
elements to and from the linked list.  And you will have a function that 
looks like this:

// This function goes through the sprite list and updates all sprites
void do_sprites(void) {

   struct sprite *current;

   current = sprite_list;

   while (current != NULL) {

      // This function restores the background, by placing the 
      // data pointed to by current->background at current->xpos,
      // current->ypos.  You write this one.
      RESTORE_BACKGROUND(current->background, current->xpos, current->ypos);
      
      // Update x and y coordinates
      current->xpos = current->xpos + current->xspeed;
      current->ypos = current->ypos + current->yspeed;

      // Do whatever bounds checking or whatever you want here

      // This function will make a copy of the background that will be 
      // covered by the sprite in the array pointed to by 
      // current->background. You have to write this one too.
      CUT_BACKGROUND(current->background, current->xpos, current->ypos);

      // Draw sprite - This function draws the sprite at xpos, ypos
      // the current->type would indicate what data to use when drawing.
      // You'll have to write this one also.
      // Uses the sprite_data[] array which contains the bitmaps for the
      // sprites, see below for more details.
      DRAWSPRITE(sprite_data[current->type], current->xpos, current->ypos);

      current = current->next;
   }
}

You would call this function every time you want to move the sprites (ie
every time you go through your main loop).  Note that this is very simple
and you don't have to do it this way, I am only providing this example
to make the discussion of the animation more understandable.

To draw the sprite, you send the drawing function the address where the 
sprite data starts. This data would be stored in an array that looks 
something like:

unsigned char sprite_data[MAX_NO_OF_SPRITES][MAX_SIZE_OF_SPRITES];

So the data for sprite type 10 starts at sprite_data[10][0]. Remember that
I am assuming all sprites are the same size. 

So, when do we animate?  Right now.

ANIMATION

For animation I use linked lists.  You could use arrays instead, but 
I like linked lists because they can be referenced faster and more neatly.
The downside is that they are a little messy to set up and to deallocate when
finished.

Each particular sprite animation has its own linked list and each node
in that list represents a frame.  Each node has a structure that looks like:

struct frame{
  unsigned char *data;  // Pointer to the bitmap data for this frame.
                        // If you are using compiled bitmaps, you could put
                        // a pointer to the compiled bitmap function here.
  
  int           delay;  // This value indicates how long to wait before
                        // going to the next frame.

   struct frame *next;  // Pointer to the next frame
}

So a sprite that just does the same thing over and over again.  Say an
enemy ship that has blinking lights would have a linked list that looks
like :

/-->   FRAME 1      ---->  FRAME2         -----\
|      (Lights on)         (Lights off)        |
|                                              |
|                                              |
 \---------------------------------------------/

Note that this animation only has two frames, but you could have as many as
you like.  Also note that each frame has its own delay time so you can 
make some frames appear for longer than others.

Now this is where linked lists get a little messy, to create a linked
list that had the above format it would look like:

   struct frame *current, *last;

   ...
   
   current        = allocate( sizeof(struct frame) );
   // We store the pointer to the start of the animation in the array
   // ANIMATIONS, see below for more details.
   animations[0]  = current;                      
   current->data  = POINTER_TO_FRAME1_DATA;
   current->delay = 20;
   last           = current;

   current        = allocate( sizeof(struct frame) );
   current->data  = POINTER_TO_FRAME2_DATA;
   current->delay = 20;
   current->next  = last;
   last->next     = current;

   ...

Now assuming that we have several animation lists set up, how
do we keep track of them?  Simply use an array.  We can use our TYPE
field to index this array.  For example:

struct frame *animations[MAX_ANIMATIONS];

So say that element 0 in the animations[] array is a ship and element
1 is a bullet, then the array would look like:

    animations[0] --> Animation linked list for ship.
    animations[1] --> Animation linked list for bullet.

So suppose we are creating a sprite that has type 4.  We know that the 
animation starts at animations[4].

Now we must add a couple of fields to the sprite struct that was defined 
a little earlier in this document to help with our animation.  
These fields are:

struct sprite {
   ...
   struct frame *a_frame;   // The animation frame that we are currently on
   int          a_count;    // A counter that keeps track of the delay
   ...
};

So for each sprite we have these extra two fields.  Now when we are adding
a sprite to the sprite_list, in addition to initializing xpos, ypos, xspeed,
yspeed etc..  we have the following two lines:
 
   new_sprite->a_frame = animations[new_sprite->type];
   new_sprite->a_count = new_sprite->a_frame->delay;

So for each sprite, we now will know what animation frame we are currently 
on and how long we have left on this frame.

Each time we update the sprite, we subtract one from the a_count value.
When a_count == 0, we move to the next frame.  

Here is a new version of do_sprites() using animation:

void do_sprites(void) {

   struct sprite *current;

   current = sprite_list;

   while (current != NULL) {

      RESTORE_BACKGROUND(current->background, current->xpos, current->ypos);

      // NEW PART STARTS HERE
      current->a_count--;
      if (current->a_count ==0) {
         // If we have reached end of animation, move to next frame and
         // reset a_count.
         current->a_frame = current->a_frame->next;
         current->a_count = current->a_frame->delay;
      }
      // NEW PART ENDS HERE

      current->xpos = current->xpos + current->xspeed;
      current->ypos = current->ypos + current->yspeed;

      // Do whatever bounds checking or whatever you want here

      CUT_BACKGROUND(current->background, current->xpos, current->ypos);
      DRAWSPRITE(sprite_data[current->type], current->xpos, current->ypos);

      current = current->next;
   }
}

Once you have set up the animation linked list and added the sprite to 
the sprite linked list, every time you call do_sprites the animation is done
automatically.

FINITE ANIMATIONS

Finite animations are animations that don't have a loop, that is, they end.
Say for example an explosion, may have three frames: A small explosion,
a bigger explosion and the final biggest explosion.  Once this animation 
has ended we want to delete the explosion from sprite_list.  This is easy
to do.

The animation linked list for the described explosion would look like:

  EXPLOSION  ----->  EXPLOSION  -----> EXPLOSION -----> NULL
  FRAME # 1          FRAME # 2         FRAME # 3

The NEXT field of the last frame will be a NULL pointer.  So when you are
advancing an animation, simply check to see if the next frame if NULL, if
it is, then delete the sprite.

This alteration would look like:      

void do_sprites(void) 
{
   ...
      
      current->a_count--;
      if (current->a_count ==0) {
         // If we have reached end of animation, move to next frame and
         // reset a_count.
         if (current-a_frame->next == NULL)
            // This function deletes the sprite from sprite_list
            delete_sprite(current);
         else {
            current->a_frame = current->a_frame->next;
            current->a_count = current->a_frame->delay;
         }
      }

   ...
}

Two things I must mention:
   1. I didn't bother to show it in the above code fragment, but if you
      delete the sprite, make sure that you jump over the following lines
      that update the x and y positions and draw the sprite.  Since the node
      no longer exists, these operations are no longer valid.

   2. This has nothing to do with sprites, but it is important to
      realize that on MS-DOS machines comparing two pointers will
      not always work because of the segmented architecture. 

      This is important when deleting a node.  For example suppose
      CURRENT is the node to be deleted, and LAST is the node directly
      before CURRENT in the list.  To delete CURRENT we would do the 
      following:

          last->next = current->next;
          free(current);

      So we need to know which node precedes the node to be deleted.
      Since the nodes don't keep track of the previous node (only the next) 
      we must traverse the list and find the node that precedes the node 
      to be deleted.  But since we cannot compare pointers, we cannot simply 
      do the following: (current is a pointer to node to be deleted)

         last = sprite_list;
         while (last->next != current)
            last = last->next

      What I did was to give each node a unique nodeid, so to delete
      a node, do the following:

         last = sprite_list;
         while (last->next->nodeid != current->nodeid)
            last = last->next

      This version would work.  Remember that each node must have a UNIQUE 
      nodeid value.  I hope this makes sense,  if you are familiar with
      linked lists it should.  Although this isn't directly related to 
      sprite animation you must understand this problem if you wish to
      implement the system as described in this document.

CLEANING UP THE ANIMATIONS

When the program is done executing, we must deallocate all the memory
that is used up by the animation linked lists.  As I mentioned earlier, 
this is a little messy, but not too bad. (Also remember to deallocate all 
the nodes in the sprite_list linked list.  This is very easy to do.)

Remember that all the animations are pointed to by the array called
(not surprisingly) animations[].  For each element in this array, we 
delete the animation that is pointed to.

This is pretty simple, except that some of the animations have loops in them
so we cannot simply do the following.

   struct frame *current, *next;
   
   current = animations[0];
   while (current!=NULL) {
      next = current->next;
      free(current);
      current=next;
    }

What we must do is first check to see if the list is finite.  So what I do 
is follow the list for 10 frames and see if a NULL pointer is found, if we
find one, the list does not loop and we can use the above method.  If we 
don't find an end, (and we are assuming that no animations have 10 or
more frames) then we "break" the loop, turning the animation int a non-
looped list and delete the animation as above. This "breaking" looks
like:
    
   struct frame *current, *next;
   
   // Break the loop
   next = animations[0];
   current = next->current
   next->next = NULL;

   // Deallocate list
   while (current!=NULL) {
      next = current->next;
      free(current);
      current=next;
    }

It is good practice to always deallocate all dynamic memory before 
terminating your program, so always try to do it, even if it is a pain.

CONCLUSION

Well, that's pretty much it.  The basic idea is pretty simple, but I 
complicated it with all the implementation details.  I hope this makes 
sense to people.  

If you have any questions/comments/criticisims please feel free to E-mail 
me at [email-masked]

Also feel free to send me any programs you write that uses this technique,
I would like to see if anybody can actually decipher this mess and 
get something working.