ant.c

这是一个C语言写的一个解决TSP问题的蚁群算法程序

/*ant.c*/

#define SPACE 0×20
#define ESC 0×1b
#define ANT_CHAR_EMPTY ‘+’
#define ANT_CHAR_FOOD 153
#define HOME_CHAR ‘H’
#define FOOD_CHAR ‘F’
#define FOOD_CHAR2 ‘f’
#define FOOD_HOME_COLOR 12
#define BLOCK_CHAR 177

#define MAX_ANT 50
#define INI_SPEED 3
#define MAXX 80
#define MAXY 23
#define MAX_FOOD 10000
#define TARGET_FOOD 200
#define MAX_SMELL 5000
#define SMELL_DROP_RATE 0.05
#define ANT_ERROR_RATE 0.02
#define ANT_EYESHOT 3
#define SMELL_GONE_SPEED 50
#define SMELL_GONE_RATE 0.05
#define TRACE_REMEMBER 50
#define MAX_BLOCK 100

#define NULL 0
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4
#define SMELL_TYPE_FOOD 0
#define SMELL_TYPE_HOME 1

#include “stdio.h”
#include “conio.h”
#include “dos.h”
#include “stdlib.h”
#include “dos.h”
#include “process.h”
#include “ctype.h”
#include “math.h”

void WorldInitial(void);
void BlockInitial(void);
void CreatBlock(void);
void SaveBlock(void);
void LoadBlock(void);
void HomeFoodInitial(void);
void AntInitial(void);
void WorldChange(void);
void AntMove(void);
void AntOneStep(void);
void DealKey(char key);
void ClearSmellDisp(void);
void DispSmell(int type);
int AntNextDir(int xxx,int yyy,int ddir);
int GetMaxSmell(int type,int xxx,int yyy,int ddir);
int IsTrace(int xxx,int yyy);
int MaxLocation(int num1,int num2,int num3);
int CanGo(int xxx,int yyy,int ddir);
int JudgeCanGo(int xxx,int yyy);
int TurnLeft(int ddir);
int TurnRight(int ddir);
int TurnBack(int ddir);

int MainTimer(void);
char WaitForKey(int secnum);
void DispPlayTime(void);
int TimeUse(void);
void HideCur(void);
void ResetCur(void);

/* —————  */
struct HomeStruct
{
  int xxx,yyy;
  int amount;
  int TargetFood;
}home;

struct FoodStruct
{
  int xxx,yyy;
  int amount;
}food;

struct AntStruct
{
  int xxx,yyy;
  int dir;
  int speed;
  int SpeedTimer;
  int food;
  int SmellAmount[2];
  int tracex[TRACE_REMEMBER];
  int tracey[TRACE_REMEMBER];
  int TracePtr;
  int IQ;
}ant[MAX_ANT];
int AntNow;
int timer10ms;
struct time starttime,endtime;
int Smell[2][MAXX+1][MAXY+1];
int block[MAXX+1][MAXY+1];
int SmellGoneTimer;
int SmellDispFlag;
int CanFindFood;
int HardtoFindPath;

/* —– Main ——– */
void main(void)
{
  char KeyPress;
  int tu;

  clrscr();
  HideCur();
  WorldInitial();
  do
  {
    timer10ms = MainTimer();
    if(timer10ms) AntMove();
    if(timer10ms) WorldChange();
    tu = TimeUse();
    if(tu>=60&&!CanFindFood)
    {
      gotoxy(1,MAXY+1);
      printf(“Can not find food, maybe a block world.”);
      WaitForKey(10);
      WorldInitial();
    }
    if(tu>=180&&home.amount<100&&!HardtoFindPath)
    {
      gotoxy(1,MAXY+1);
      printf(“God! it is so difficult to find a path.”);
      if(WaitForKey(10)==0×0d) WorldInitial();
      else
     {
        HardtoFindPath = 1;
        gotoxy(1,MAXY+1);
        printf(”                     “);
     }
    }
    if(home.amount>=home.TargetFood)
    {
      gettime(&endtime);
      KeyPress = WaitForKey(60);
      DispPlayTime();
      WaitForKey(10);
      WorldInitial();
    }
    else if(kbhit())
    {
      KeyPress = getch();
      DealKey(KeyPress);
    }
    else KeyPress = NULL;
  }
  while(KeyPress!=ESC);
  gettime(&endtime);
  DispPlayTime();
  WaitForKey(10);
  clrscr();
  ResetCur();
}

/* —— general sub process ———– */
int MainTimer(void)
/* output: how much 10ms have pass from last time call this process */
{
  static int oldhund,oldsec;
  struct  time t;
  int timeuse;

  gettime(&t);
  timeuse = 0;
  if(t.ti_hund!=oldhund)
  {
    if(t.ti_sec!=oldsec)
    {
      timeuse+=100;
      oldsec = t.ti_sec;
    }
    timeuse+=t.ti_hund-oldhund;
    oldhund = t.ti_hund;
  }
  else timeuse = 0;
  return (timeuse);
}

char WaitForKey(int secnum)
/* funtion: if have key in, exit immediately, else wait ’secnum’ senconds then exit
   input: secnum — wait this senconds, must < 3600 (1 hour)
   output: key char, if no key in(exit when timeout), return NULL */
{
  int secin,secnow;
  int minin,minnow;
  int hourin,hournow;
  int secuse;
  struct  time t;

  gettime(&t);
  secin = t.ti_sec;
  minin = t.ti_min;
  hourin = t.ti_hour;

  do
  {
    if(kbhit()) return(getch());
    gettime(&t);
    secnow = t.ti_sec;
    minnow = t.ti_min;
    hournow = t.ti_hour;

    if(hournow!=hourin) minnow+=60;
    if(minnow>minin) secuse = (minnow-1-minin) + (secnow+60-secin);
    else secuse = secnow - secin;

    /* counting error check */
    if(secuse<0)
    {
      gotoxy(1,MAXY+1);
      printf(“Time conuting error, any keyto exit…”);
      getch();
      exit(3);
    }
  }
  while(secuse<=secnum);
  return (NULL);
}

void DispPlayTime(void)
{
  int ph,pm,ps;

  ph = endtime.ti_hour - starttime.ti_hour;
  pm = endtime.ti_min - starttime.ti_min;
  ps = endtime.ti_sec - starttime.ti_sec;

  if(ph<0) ph+=24;
  if(pm<0) { ph–; pm+=60; }
  if(ps<0) { pm–; ps+=60; }

  gotoxy(1,MAXY+1);
  printf(“Time use: %d hour- %d min- %d sec “,ph,pm,ps);
}

int TimeUse(void)
{
  int ph,pm,ps;

  gettime(&endtime);
  ph = endtime.ti_hour - starttime.ti_hour;
  pm = endtime.ti_min - starttime.ti_min;
  ps = endtime.ti_sec - starttime.ti_sec;

  if(ph<0) ph+=24;
  if(pm<0) { ph–; pm+=60; }
  if(ps<0) { pm–; ps+=60; }

  return(ps+(60*(pm+60*ph)));
}

void HideCur(void)
{
  union REGS regs0;
  regs0.h.ah=1;
  regs0.h.ch=0×30;
  regs0.h.cl=0×31;
  int86(0×10,&regs0,&regs0);
}

void ResetCur(void)
{
  union REGS regs0;
  regs0.h.ah=1;
  regs0.h.ch=0×06;
  regs0.h.cl=0×07;
  int86(0×10,&regs0,&regs0);
}

/* ———— main ANT programe ————- */
void WorldInitial(void)
{
  int k,i,j;
  randomize();
  clrscr();
  HomeFoodInitial();
  for(AntNow=0;AntNow<MAX_ANT;AntNow++)
  {
    AntInitial();
  } /* of for AntNow */;

  BlockInitial();
  for(k=0;k<=1;k++)
  /* SMELL TYPE FOOD and HOME */
    for(i=0;i<=MAXX;i++)
      for(j=0;j<=MAXY;j++)
        Smell[k][i][j] = 0;
  SmellGoneTimer = 0;
  gettime(&starttime);
  SmellDispFlag = 0;
  CanFindFood = 0;
  HardtoFindPath = 0;
}

void BlockInitial(void)
{
  int i,j;
  int bn;

  for(i=0;i<=MAXX;i++)
    for(j=0;j<=MAXY;j++)
      block[i][j] = 0;

  bn = 1+ MAX_BLOCK/2 + random(MAX_BLOCK/2);
  for(i=0;i<=bn;i++) CreatBlock();
}

void CreatBlock(void)
{
  int x1,y1,x2,y2;
  int dx,dy;
  int i,j;

  x1 = random(MAXX)+1;
  y1 = random(MAXY)+1;

  dx = random(MAXX/10)+1;
  dy = random(MAXY/10)+1;

  x2 = x1+dx;
  y2 = y1+dy;

  if(x2>MAXX) x2 = MAXX;
  if(y2>MAXY) y2 = MAXY;

  if(food.xxx>=x1&&food.xxx<=x2&&food.yyy>=y1&&food.yyy<=y2) return;
  if(home.xxx>=x1&&home.xxx<=x2&&home.yyy>=y1&&home.yyy<=y2) return;

  for(i=x1;i<=x2;i++)
    for(j=y1;j<=y2;j++)
    {
      block[i][j] = 1;
      gotoxy(i,j);
      putch(BLOCK_CHAR);
    }
}

void SaveBlock(void)
{
 FILE *fp_block;
 char FileNameBlock[20];
 int i,j;

 gotoxy(1,MAXY+1);
  printf(”                     “);
 gotoxy(1,MAXY+1);
 printf(“Save to file…”,FileNameBlock);
 gets(FileNameBlock);
 if(FileNameBlock[0]==0) strcpy(FileNameBlock,“Ant.ant”);
 else strcat(FileNameBlock,“.ant”);

 if ((fp_block = fopen(FileNameBlock, “wb”)) == NULL)
 { gotoxy(1,MAXY+1);
    printf(“Creat file %s fail…”,FileNameBlock);
  getch();
  exit(2);
 }
 gotoxy(1,MAXY+1);
  printf(”                           “);

 fputc(home.xxx,fp_block);
 fputc(home.yyy,fp_block);
 fputc(food.xxx,fp_block);
 fputc(food.yyy,fp_block);

 for(i=0;i<=MAXX;i++)
    for(j=0;j<=MAXY;j++)
      fputc(block[i][j],fp_block);

  fclose(fp_block);
}

void LoadBlock(void)
{
 FILE *fp_block;
 char FileNameBlock[20];
 int i,j,k;

 gotoxy(1,MAXY+1);
  printf(”                     “);
 gotoxy(1,MAXY+1);
 printf(“Load file…”,FileNameBlock);
 gets(FileNameBlock);
 if(FileNameBlock[0]==0) strcpy(FileNameBlock,“Ant.ant”);
 else strcat(FileNameBlock,“.ant”);

 if ((fp_block = fopen(FileNameBlock, “rb”)) == NULL)
 { gotoxy(1,MAXY+1);
    printf(“Open file %s fail…”,FileNameBlock);
  getch();
  exit(2);
 }

 clrscr();
 home.xxx = fgetc(fp_block);
 home.yyy = fgetc(fp_block);
 food.xxx = fgetc(fp_block);
 food.yyy = fgetc(fp_block);
 gotoxy(home.xxx,home.yyy); putch(HOME_CHAR);
  gotoxy(food.xxx,food.yyy); putch(FOOD_CHAR);
  food.amount = random(MAX_FOOD/3)+2*MAX_FOOD/3+1;
  /* food.amount = MAX_FOOD; */
  home.amount = 0;
  home.TargetFood =
    (food.amount<TARGET_FOOD)?food.amount:TARGET_FOOD;

 for(AntNow=0;AntNow<MAX_ANT;AntNow++)
  {
    AntInitial();
  } /* of for AntNow */;

 for(i=0;i<=MAXX;i++)
    for(j=0;j<=MAXY;j++)
    {
      block[i][j] = fgetc(fp_block);
      if(block[i][j])
      {
       gotoxy(i,j);
       putch(BLOCK_CHAR);
     }
    }

  for(k=0;k<=1;k++)
  /* SMELL TYPE FOOD and HOME */
    for(i=0;i<=MAXX;i++)
      for(j=0;j<=MAXY;j++)
        Smell[k][i][j] = 0;
  SmellGoneTimer = 0;
  gettime(&starttime);
  SmellDispFlag = 0;
  CanFindFood = 0;
  HardtoFindPath = 0;

  fclose(fp_block);
}

void HomeFoodInitial(void)
{
  int randnum;
  int homeplace;
  /* 1 — home at left-up, food at right-down
     2 — home at left-down, food at right-up
     3 — home at right-up, food at left-down
     4 — home at right-down, food at left-up */

  randnum = random(100);
  if(randnum<25) homeplace = 1;
  else if (randnum>=25&&randnum<50) homeplace = 2;
  else if (randnum>=50&&randnum<75) homeplace = 3;
  else homeplace = 4;

  switch(homeplace)
  {
    case 1: home.xxx = random(MAXX/3)+1;
        home.yyy = random(MAXY/3)+1;
        food.xxx = random(MAXX/3)+2*MAXX/3+1;
        food.yyy = random(MAXY/3)+2*MAXY/3+1;
        break;
    case 2: home.xxx = random(MAXX/3)+1;
        home.yyy = random(MAXY/3)+2*MAXY/3+1;
        food.xxx = random(MAXX/3)+2*MAXX/3+1;
        food.yyy = random(MAXY/3)+1;
        break;
    case 3: home.xxx = random(MAXX/3)+2*MAXX/3+1;
        home.yyy = random(MAXY/3)+1;
        food.xxx = random(MAXX/3)+1;
        food.yyy = random(MAXY/3)+2*MAXY/3+1;
        break;
    case 4: home.xxx = random(MAXX/3)+2*MAXX/3+1;
        home.yyy = random(MAXY/3)+2*MAXY/3+1;
        food.xxx = random(MAXX/3)+1;
        food.yyy = random(MAXY/3)+1;
        break;
  }

  food.amount = random(MAX_FOOD/3)+2*MAX_FOOD/3+1;
  /* food.amount = MAX_FOOD; */
  home.amount = 0;
  home.TargetFood = (food.amount<TARGET_FOOD)?food.amount:TARGET_FOOD;

  /* data correctness check */
  if(home.xxx<=0||home.xxx>MAXX||home.yyy<=0||home.yyy>MAXY||
     food.xxx<=0||food.xxx>MAXX||food.yyy<=0||food.yyy>MAXY||
     food.amount<=0)
  {
    gotoxy(1,MAXY+1);
    printf(“World initial fail, any key to exit…”);
    getch();
    exit(2);
  }

  gotoxy(home.xxx,home.yyy); putch(HOME_CHAR);
  gotoxy(food.xxx,food.yyy); putch(FOOD_CHAR);
}
void AntInitial(void)
/* initial ant[AntNow] */
{
  int randnum;
  int i;

  ant[AntNow].xxx = home.xxx;
  ant[AntNow].yyy = home.yyy;

  randnum = random(100);
  if(randnum<25) ant[AntNow].dir = UP;
  else if (randnum>=25&&randnum<50) ant[AntNow].dir = DOWN;
  else if (randnum>=50&&randnum<75) ant[AntNow].dir = LEFT;
  else ant[AntNow].dir = RIGHT;

  ant[AntNow].speed = 2*(random(INI_SPEED/2)+1);
  ant[AntNow].SpeedTimer = 0;
  ant[AntNow].food = 0;
  ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = 0;
  ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = MAX_SMELL;
  ant[AntNow].IQ = 1;

  for(i=0;i<TRACE_REMEMBER;i++)
  {
    ant[AntNow].tracex[i] = 0;
    ant[AntNow].tracey[i] = 0;
  }
  ant[AntNow].TracePtr = 0;

  /* a sepecail ant */
  if(AntNow==0) ant[AntNow].speed = INI_SPEED;
}

void WorldChange(void)
{
  int k,i,j;
  int smelldisp;

  SmellGoneTimer+=timer10ms;
  if(SmellGoneTimer>=SMELL_GONE_SPEED)
  {
    SmellGoneTimer = 0;
    for(k=0;k<=1;k++)
    /* SMELL TYPE FOOD and HOME */
      for(i=1;i<=MAXX;i++)
        for(j=1;j<=MAXY;j++)
        {
            if(Smell[k][i][j])
          {
              smelldisp = 1+((10*Smell[k][i][j])/(MAX_SMELL*SMELL_DROP_RATE));
              if(smelldisp>=30000||smelldisp<0) smelldisp = 30000;
              if(SmellDispFlag)
           {
                gotoxy(i,j);
                if((i==food.xxx&&j==food.yyy)||(i==home.xxx&&j==home.yyy))
                  /* don’t over write Food and Home */;
              else
             {
                  if(smelldisp>9) putch(‘#’);
                  else putch(smelldisp+‘0′);
             }
           }
              Smell[k][i][j]-= 1+(Smell[k][i][j]*SMELL_GONE_RATE);
              if(Smell[k][i][j]<0) Smell[k][i][j] = 0;
              if(SmellDispFlag)