/* Programme d'animation par recouvrement de rectangles, en partie optimisé.

Testé avec Borland C++ 4.02 en modèle small par Jim Mischel 12/16/94.
*/
#include <stdlib.h>
#include <conio.h>
#include <alloc.h>
#include <memory.h>
#include <dos.h>

/* A mettre en commentaire pour désactiver la suppression du recouvrement dans 
   la liste des rectangles de recouvrement. */
#define CHECK_OVERLAP 1
#define SCREEN_WIDTH  320
#define SCREEN_HEIGHT 200
#define SCREEN_SEGMENT 0xA000

/* Décrit un rectangle de recouvrement */
typedef struct {
   void *Next;    /* pointeur sur le prochain nœud dans la liste chaînée des rectangles de recouvrement*/
   int Top;
   int Left;
   int Right;
   int Bottom;
} DirtyRectangle;
/* Décrit un objet animé */
typedef struct {
   int X;            /* coin supérieur gauche dans la bitmap virtuelle */
   int Y;
   int XDirection;   /* direction et distance du mouvement */
   int YDirection;
   int InternalAnimateCount; /* piste l'état de l'animation interne */
   int InternalAnimateMax;   /* état maximal de l'animation interne */
} Entity;
/* Stockage utilisé pour les rectangles de recouvrement */
#define MAX_DIRTY_RECTANGLES  100
int NumDirtyRectangles;
DirtyRectangle DirtyRectangles[MAX_DIRTY_RECTANGLES];
/* Tête et queue de la liste des rectangles de recouvrement */
DirtyRectangle DirtyHead;
/* Si à 1, ignore la liste des rectangles de recouvrement et copie tout  
   l'écran. */

  DrawWholeScreen = 0;
/* Pixels et masques pour les deux versions d'animation interne de l'image
   que nous animerons */
#define IMAGE_WIDTH  13
#define IMAGE_HEIGHT 11
char ImagePixels0[] = {
   0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0,
   0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0,
   0, 9, 9, 0, 0,14,14,14, 9, 9, 0, 0, 0,
   9, 9, 0, 0, 0, 0,14,14,14, 9, 9, 0, 0,
   9, 9, 0, 0, 0, 0,14,14,14, 9, 9, 0, 0,
   9, 9,14, 0, 0,14,14,14,14, 9, 9, 0, 0,
   9, 9,14,14,14,14,14,14,14, 9, 9, 0, 0,
   9, 9,14,14,14,14,14,14,14, 9, 9, 0, 0,
   0, 9, 9,14,14,14,14,14, 9, 9, 0, 0, 0,
   0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0,
   0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0,
};
char ImageMask0[] = {
   0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,
   0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
   0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0,
   1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0,
   1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0,
   1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0,
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
   0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
   0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
   0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,
};
char ImagePixels1[] = {
   0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 9,
   0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9,
   0, 9, 9, 0, 0,14,14,14, 9, 9, 9, 9, 0,
   9, 9, 0, 0, 0, 0,14,14,14, 0, 0, 0, 0,
   9, 9, 0, 0, 0, 0,14,14, 0, 0, 0, 0, 0,
   9, 9,14, 0, 0,14,14,14, 0, 0, 0, 0, 0,
   9, 9,14,14,14,14,14,14, 0, 0, 0, 0, 0,
   9, 9,14,14,14,14,14,14,14, 0, 0, 0, 0,
   0, 9, 9,14,14,14,14,14, 9, 9, 9, 9, 0,
   0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 9,
   0, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 9, 9,
};
char ImageMask1[] = {
   0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,
   0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,
   0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0,
   1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
   1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,
   1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0,
   1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,
   1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
   0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
   0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,
   0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1,
};
/* Pointeurs sur les données du pixel et du masque pour les différentes versions
   d'animation de notre image animée. */
char * ImagePixelArray[] = {ImagePixels0, ImagePixels1};
char * ImageMaskArray[] = {ImageMask0, ImageMask1};
/* Animated entities */
#define NUM_ENTITIES 15
Entity Entities[NUM_ENTITIES];
/* Pointeur sur le tampon système dans lequel nous afficherons */
char far *SystemBufferPtr;
/* Pointeur sur l'écran*/
char far *ScreenPtr;
void EraseEntities(void);
void CopyDirtyRectanglesToScreen(void);
void DrawEntities(void);
void AddDirtyRect(Entity *, int, int);
void DrawMasked(char far *, char *, char *, int, int, int);
void FillRect(char far *, int, int, int, int);
void CopyRect(char far *, char far *, int, int, int, int);
void main()
{
   int i, XTemp, YTemp;
   unsigned int TempCount;
   char far *TempPtr;
   union REGS regs;
   /* Alloue de la mémoire au tampon système dans lequel nous afficherons */
   if (!(SystemBufferPtr = farmalloc((unsigned int)SCREEN_WIDTH*
         SCREEN_HEIGHT))) {
      printf("Couldn't get memory\n");
      exit(1);
   }
   /* Vide le tampon système */
   TempPtr = SystemBufferPtr;
   for (TempCount = ((unsigned)SCREEN_WIDTH*SCREEN_HEIGHT); TempCount--; ) {
      *TempPtr++ = 0;
   }
   /* Pointe sur l'écran */
   ScreenPtr = MK_FP(SCREEN_SEGMENT, 0);
   /* Configure les entités que nous animerons, à des emplacements aléatoires */
   randomize();
   for (i = 0; i < NUM_ENTITIES; i++) {
      Entities[i].X = random(SCREEN_WIDTH - IMAGE_WIDTH);
      Entities[i].Y = random(SCREEN_HEIGHT - IMAGE_HEIGHT);
      Entities[i].XDirection = 1;
      Entities[i].YDirection = -1;
      Entities[i].InternalAnimateCount = i & 1;
      Entities[i].InternalAnimateMax = 2;
   }
   /* Paramètre la liste de rectangles par recouvrement pour vider, et configure  
      le nœud tête/queue comme une sentinelle */
   NumDirtyRectangles = 0;
   DirtyHead.Next = &DirtyHead;
   DirtyHead.Top = 0x7FFF;
   DirtyHead.Left= 0x7FFF;
   DirtyHead.Bottom = 0x7FFF;
   DirtyHead.Right = 0x7FFF;
   /* Paramètre le mode graphique 320x200 en 256 couleurs  */
   regs.x.ax = 0x0013;
   int86(0x10, &regs, &regs);
   /* Effectue une boucle et affiche jusqu'à ce qu'une touche clavier soit    
      pressée */
   do {
      /* Affiche les entités dans le tampon système à leur emplacement courant,
         en mettant à jour la liste de rectangles de recouvrement */
      DrawEntities();
      /* Affiche les rectangles de recouvrement, ou tout le tampon système si
         nécessaire */
      CopyDirtyRectanglesToScreen();
      /* Réinitialise l liste des rectangles de recouvrement pour vider */
      NumDirtyRectangles = 0;
      DirtyHead.Next = &DirtyHead;
      /* Supprime les entités dans le tampon système à leur ancien emplacement,
         en mettant à jour la liste des rectangles de recouvrement */
      EraseEntities();
      /* Déplace les entités, en rebondissant sur les cotés de l'écran */
      for (i = 0; i < NUM_ENTITIES; i++) {
         XTemp = Entities[i].X + Entities[i].XDirection;
         YTemp = Entities[i].Y + Entities[i].YDirection;
         if ((XTemp < 0) || ((XTemp + IMAGE_WIDTH) > SCREEN_WIDTH)) {
            Entities[i].XDirection = -Entities[i].XDirection;
            XTemp = Entities[i].X + Entities[i].XDirection;
         }
         if ((YTemp < 0) || ((YTemp + IMAGE_HEIGHT) > SCREEN_HEIGHT)) {
            Entities[i].YDirection = -Entities[i].YDirection;
            YTemp = Entities[i].Y + Entities[i].YDirection;
         }
         Entities[i].X = XTemp;
         Entities[i].Y = YTemp;
      }
   } while (!kbhit());
   getch();    /* clear the keypress */

   /* Revient en mode texte */
   regs.x.ax = 0x0003;
   int86(0x10, &regs, &regs);
}
/* Affiche les entités à leur emplacement courant, en mettant à jour la liste  
   des rectangles de recouvrement. */
void DrawEntities()
{
   int i;
   char far *RowPtrBuffer;
   char *TempPtrImage;
   char *TempPtrMask;
    Entity *EntityPtr;

   for (i = 0, EntityPtr = Entities; i < NUM_ENTITIES; i++, EntityPtr++) {
      /* Mémorise l'info du rectangle par recouvrement pour cette entité */
      AddDirtyRect(EntityPtr, IMAGE_HEIGHT, IMAGE_WIDTH);
      /* Pointe sur la destination dans le tampon système */
      RowPtrBuffer = SystemBufferPtr + (EntityPtr->Y * SCREEN_WIDTH) +
            EntityPtr->X;
      /* Avance le pointeur de l'animation de l'image */
      if (++EntityPtr->InternalAnimateCount >=
            EntityPtr->InternalAnimateMax) {
         EntityPtr->InternalAnimateCount = 0;
      }
      /* Pointe sur l'image et le masque à afficher */
      TempPtrImage = ImagePixelArray[EntityPtr->InternalAnimateCount];
      TempPtrMask = ImageMaskArray[EntityPtr->InternalAnimateCount];
      DrawMasked(RowPtrBuffer, TempPtrImage, TempPtrMask, IMAGE_HEIGHT,
               IMAGE_WIDTH, SCREEN_WIDTH);
   }
}
/* Copie les rectangles de recouvrement, ou tout le tampon système si 
   nécessaire, à l'écran. */
void CopyDirtyRectanglesToScreen()
{
   int i, RectWidth, RectHeight;
   unsigned int Offset;
   DirtyRectangle * DirtyPtr;
   if (DrawWholeScreen) {
      /* Copie seulement tout le tampon système à l'écran*/
      DrawWholeScreen = 0;
      CopyRect(ScreenPtr, SystemBufferPtr, SCREEN_HEIGHT, SCREEN_WIDTH,
               SCREEN_WIDTH, SCREEN_WIDTH);
   } else {
      /* Copie seulement les rectangles par recouvrement, dans l'ordre de tri YX dans lequel ils sont chaînés */
      DirtyPtr = DirtyHead.Next;
      for (i = 0; i < NumDirtyRectangles; i++) {
         /* Offset dans à la fois le tampon système et l'écran de l'image */
         Offset = (unsigned int) (DirtyPtr->Top * SCREEN_WIDTH) +
               DirtyPtr->Left;
         /* Dimensions du rectangle par recouvrement */
         RectWidth = DirtyPtr->Right - DirtyPtr->Left;
         RectHeight = DirtyPtr->Bottom - DirtyPtr->Top;
         /* Copie un rectangle par recouvrement */
         CopyRect(ScreenPtr + Offset, SystemBufferPtr + Offset,
               RectHeight, RectWidth, SCREEN_WIDTH, SCREEN_WIDTH);
         /* Pointe sur le prochain rectangle par recouvrement */
         DirtyPtr = DirtyPtr->Next;
      }
   }
}
/* Supprime les entités dans le tampon système à leur emplacement courant,
en mettant à jour la liste de rectangles par recouvrement. */
void EraseEntities()
{
   int i;
   char far *RowPtr;
   for (i = 0; i < NUM_ENTITIES; i++) {
      /* Mémorise l'info du rectangle par recouvrement pour cette entité */
      AddDirtyRect(&Entities[i], IMAGE_HEIGHT, IMAGE_WIDTH);
      /* Pointe sur la destination dans le tampon système */
      RowPtr = SystemBufferPtr + (Entities[i].Y * SCREEN_WIDTH) +
            Entities[i].X;
      /* Efface le rectangle */
      FillRect(RowPtr, IMAGE_HEIGHT, IMAGE_WIDTH, SCREEN_WIDTH, 0);
   }
}
/*Ajoute un rectangle de recouvrement dans la liste. */
void AddDirtyRect(Entity * pEntity, int ImageHeight, int ImageWidth)
{
   DirtyRectangle * DirtyPtr;
   DirtyRectangle * TempPtr;
   Entity TempEntity;
   int i;
   if (NumDirtyRectangles >= MAX_DIRTY_RECTANGLES) {
      /* Il y a trop de rectangles fr recouvrement; réaffichons simplement
        l'écran */
      DrawWholeScreen = 1;
      return;
   }
   /* Mémorise ce rectangle par recouvrement. Divisons-le si nécessaire pour
      éviter les chevauchements avec les rectangles déjà présents dans la liste   
   */
#ifdef CHECK_OVERLAP
   /* Cherche les chevauchements avec les rectangles existants */
   TempPtr = DirtyHead.Next;
   for (i = 0; i < NumDirtyRectangles; i++, TempPtr = TempPtr->Next) {
      if ((TempPtr->Left < (pEntity->X + ImageWidth)) &&
          (TempPtr->Right > pEntity->X) &&
          (TempPtr->Top < (pEntity->Y + ImageHeight)) &&
          (TempPtr->Bottom > pEntity->Y)) {

         /* Nous avons trouvé un rectangle chevauchant. Compte les
            rectangles, s'il en reste après la soustraction des zones
            chevauchante, puis ajoutons-les dans la liste des recouvrement */
         /* Cherche une partie gauche non chevauchante */
         if (TempPtr->Left > pEntity->X) {
            
            TempEntity.X = pEntity->X;
            TempEntity.Y = max(pEntity->Y, TempPtr->Top);
            AddDirtyRect(&TempEntity,
                  min(pEntity->Y + ImageHeight, TempPtr->Bottom) -
                  TempEntity.Y,
                        TempPtr->Left - pEntity->X);
         }
         /* Cherche une partie droite non chevauchante */
         if (TempPtr->Right < (pEntity->X + ImageWidth)) {

            TempEntity.X = TempPtr->Right;
            TempEntity.Y = max(pEntity->Y, TempPtr->Top);
            AddDirtyRect(&TempEntity,
                  min(pEntity->Y + ImageHeight, TempPtr->Bottom) -
                  TempEntity.Y,
                  (pEntity->X + ImageWidth) - TempPtr->Right);
         }
         /* Cherche une partie non chevauchante en haut*/
         if (TempPtr->Top > pEntity->Y) {
            /* Il y aune partie en haut qui n'est pas chevauchante */
            TempEntity.X = pEntity->X;
            TempEntity.Y = pEntity->Y;
            AddDirtyRect(&TempEntity, TempPtr->Top - pEntity->Y, ImageWidth);
         }
         /* Cherche une partie non chevauchante en bas */
         if (TempPtr->Bottom < (pEntity->Y + ImageHeight)) {
         /* Il y aune partie en bas qui n'est pas chevauchante */                     
            TempEntity.X = pEntity->X;
            TempEntity.Y = TempPtr->Bottom;
            AddDirtyRect(&TempEntity,
                  (pEntity->Y + ImageHeight) - TempPtr->Bottom, ImageWidth);
         }
         /* Nous avons ajouté toutes les parties non-overlapped dans la liste des rectangles par recouvrement*/
         return;
      }
   }
#endif 

   /* Il n'y a aucun chevauchement avec tout rectangle existant, aussi nous  
      pouvons ajouter ce rectangle tel quel */
   /* Trouve le point d'insertion de tri YX. Les recherches se terminent  
      toujours, car le rectangle tête/queue est à des valeurs  
      maximales */

   TempPtr = &DirtyHead;
   while (((DirtyRectangle *)TempPtr->Next)->Top < pEntity->Y) {
      TempPtr = TempPtr->Next;
   }
   while ((((DirtyRectangle *)TempPtr->Next)->Top == pEntity->Y) &&
           (((DirtyRectangle *)TempPtr->Next)->Left < pEntity->X)) {
      TempPtr = TempPtr->Next;
   }
   /* Paramètre le rectangle et l'ajoure dans la liste des recouvrements */
   DirtyPtr = &DirtyRectangles[NumDirtyRectangles++];
   DirtyPtr->Left = pEntity->X;
   DirtyPtr->Top = pEntity->Y;
   DirtyPtr->Right = pEntity->X + ImageWidth;
   DirtyPtr->Bottom = pEntity->Y + ImageHeight;
   DirtyPtr->Next = TempPtr->Next;
   TempPtr->Next = DirtyPtr;
}