蚁群算法ACO(ant colony optimization)的原理以及实现源代码

蚁群算法ACO(ant colony optimization)的原理以及实现源代码

By Minidxer | February 1, 2008

 之前说的算法基本上都比较枯燥的（废话，算法都很枯燥……），这次要介绍的蚁群算法(Ant Colony Algorithm)却是一种源于自然现象的算法，也是一种 meta heuristic，即与具体问题关系不大的优化算法，也就是它是一种用来在图中寻找优化路径的机率型技术。Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

小小的蚂蚁总是能够找到食物，他们具有什么样的智能呢？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。

为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！

下面就是实现如此复杂性的七条简单规则：

1、范围：
蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。
2、环境：
蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
3、觅食规则：
在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。
4、移动规则：
每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。
5、避障规则：
如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
7、播撒信息素规则：
每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。

下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。

其中，‘F’点表示食物，‘H’表示窝，白色块表示障碍物，‘+’就是蚂蚁了。

参数说明：
最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。
错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。
速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。
记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。

源代码如下(不同编译器可能需做一定修改)：

/*ant.c*/

#define SPACE 0x20
#define ESC 0x1b
#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)==0x0d) 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=0x30;
  regs0.h.cl=0x31;
  int86(0x10,®s0,®s0);
}

void ResetCur(void)
{
  union REGS regs0;
  regs0.h.ah=1;
  regs0.h.ch=0x06;
  regs0.h.cl=0x07;
  int86(0x10,®s0,®s0);
}

/* ------------ main ANT programe ------------- */
void WorldInitial(void)
{
  int k,i,j;
  randomize();
  clrscr();
  HomeFoodInitial();
  for(AntNow=0;AntNow/* 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.amountfor(AntNow=0;AntNow/* 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/* 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/* 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)
           {
                if(Smell[k][i][j]<=2)
             {
                  gotoxy(i,j);
                  putch(SPACE);
             }
           }
          }
          } /* of one location */
  } /* of time to change the world */
} /* of world change */

void AntMove(void)
{
  int antx,anty;
  int smelltodrop,smellnow;

  for(AntNow=0;AntNowif(ant[AntNow].SpeedTimer>=ant[AntNow].speed)
    {
      ant[AntNow].SpeedTimer = 0;
      gotoxy(ant[AntNow].xxx,ant[AntNow].yyy);
      putch(SPACE);
      AntOneStep();
      gotoxy(ant[AntNow].xxx,ant[AntNow].yyy);
      /* ant0 is a sepecail ant, use different color */
      if(AntNow==0) textcolor(0xd);
      if(ant[AntNow].food) putch(ANT_CHAR_FOOD);
      else putch(ANT_CHAR_EMPTY);
      if(AntNow==0) textcolor(0x7);

      /* remember trace */
      ant[AntNow].tracex[ant[AntNow].TracePtr] = ant[AntNow].xxx;
      ant[AntNow].tracey[ant[AntNow].TracePtr] = ant[AntNow].yyy;
      if(++(ant[AntNow].TracePtr)>=TRACE_REMEMBER) ant[AntNow].TracePtr = 0;

      /* drop smell */
      antx = ant[AntNow].xxx;
      anty = ant[AntNow].yyy;

      if(ant[AntNow].food)
      /* have food, looking for home */
     {
        if(ant[AntNow].SmellAmount[SMELL_TYPE_FOOD])
       {
          smellnow = Smell[SMELL_TYPE_FOOD][antx][anty];
          smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]*SMELL_DROP_RATE;
          if(smelltodrop>smellnow) Smell[SMELL_TYPE_FOOD][antx][anty] = smelltodrop;
          /* else Smell[...] = smellnow */
          ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]-= smelltodrop;
          if(ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]<0) ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = 0;
        } /* of have smell to drop */
      } /* of have food */
      else
      /* no food, looking for food */
     {
        if(ant[AntNow].SmellAmount[SMELL_TYPE_HOME])
       {
          smellnow = Smell[SMELL_TYPE_HOME][antx][anty];
          smelltodrop = ant[AntNow].SmellAmount[SMELL_TYPE_HOME]*SMELL_DROP_RATE;
          if(smelltodrop>smellnow) Smell[SMELL_TYPE_HOME][antx][anty] = smelltodrop;
          /* else Smell[...] = smellnow */
          ant[AntNow].SmellAmount[SMELL_TYPE_HOME]-= smelltodrop;
          if(ant[AntNow].SmellAmount[SMELL_TYPE_HOME]<0) ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = 0;
        } /* of have smell to drop */
     }
    } /* of time to go */
    /* else not go */
  } /* of for AntNow */

  textcolor(FOOD_HOME_COLOR);
  gotoxy(home.xxx,home.yyy); putch(HOME_CHAR);
  gotoxy(food.xxx,food.yyy);
  if(food.amount>0) putch(FOOD_CHAR);
  else putch(FOOD_CHAR2);
  textcolor(7);

  gotoxy(1,MAXY+1);
  printf("Food %d, Home %d   ",food.amount,home.amount);
}

void AntOneStep(void)
{
  int ddir,tttx,ttty;
  int i;

  ddir = ant[AntNow].dir;
  tttx = ant[AntNow].xxx;
  ttty = ant[AntNow].yyy;

  ddir = AntNextDir(tttx,ttty,ddir);

  switch(ddir)
  {
    case UP:  ttty--;
          break;
    case DOWN:  ttty++;
          break;
    case LEFT:  tttx--;
          break;
    case RIGHT: tttx++;
          break;
    default:  break;
  } /* of switch dir */

  ant[AntNow].dir = ddir;
  ant[AntNow].xxx = tttx;
  ant[AntNow].yyy = ttty;

  if(ant[AntNow].food)
  /* this ant carry with food, search for home */
  {
    if(tttx==home.xxx&&ttty==home.yyy)
    {
      home.amount++;
      AntInitial();
    }
    if(tttx==food.xxx&&ttty==food.yyy)
      ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = MAX_SMELL;
  } /* of search for home */
  else
  /* this ant is empty, search for food */
  {
    if(tttx==food.xxx&&ttty==food.yyy)
    {
      if(food.amount>0)
     {
        ant[AntNow].food = 1;
        food.amount--;
        ant[AntNow].SmellAmount[SMELL_TYPE_FOOD] = MAX_SMELL;
        ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = 0;
        ant[AntNow].dir = TurnBack(ant[AntNow].dir);
        for(i=0;i/* of still have food */
    }
    if(tttx==home.xxx&&ttty==home.yyy)
      ant[AntNow].SmellAmount[SMELL_TYPE_HOME] = MAX_SMELL;
  }  /* of search for food */
}

void DealKey(char key)
{
  int i;
  switch(key)
  {
    case 'p':   gettime(&endtime);
          DispPlayTime();
          getch();
          gotoxy(1,MAXY+1);
          for(i=1;i<=MAXX-1;i++) putch(SPACE);
          break;
    case 't':   if(SmellDispFlag)
        {
            SmellDispFlag=0;
            ClearSmellDisp();
        }
          else SmellDispFlag = 1;
          break;
    case '1':   DispSmell(SMELL_TYPE_FOOD);
          getch();
          ClearSmellDisp();
          break;
    case '2':   DispSmell(SMELL_TYPE_HOME);
          getch();
          ClearSmellDisp();
          break;
    case '3':   DispSmell(2);
          getch();
          ClearSmellDisp();
          break;
    case 's':   SaveBlock();
       break;
    case 'l':   LoadBlock();
       break;
    default:  gotoxy(1,MAXY+1);
          for(i=1;i<=MAXX-1;i++) putch(SPACE);
  } /* of switch */
}

void ClearSmellDisp(void)
{
  int k,i,j;

  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])
        {
            gotoxy(i,j);
            putch(SPACE);
        }
        } /* of one location */
}

void DispSmell(int type)
/* input: 0 -- Only display food smell
      1 -- Only display home smell
      2 -- Display both food and home smell
*/
{
  int k,i,j;
  int fromk,tok;
  int smelldisp;

  switch(type)
  {
    case 0: fromk = 0;
        tok = 0;
        break;
    case 1: fromk = 1;
        tok = 1;
        break;
    case 2: fromk = 0;
        tok = 1;
        break;
    default:fromk = 0;
        tok = 1;
        break;
  }
  SmellGoneTimer = 0;
  for(k=fromk;k<=tok;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;
            gotoxy(i,j);
            if(i!=food.xxx||j!=food.yyy)
          {
              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');
           }
          }
        }
        } /* of one location */
}

int AntNextDir(int xxx,int yyy,int ddir)
{
  int randnum;
  int testdir;
  int CanGoState;
  int cangof,cangol,cangor;
  int msf,msl,msr,maxms;
  int type;

  CanGoState = CanGo(xxx,yyy,ddir);
  if(CanGoState==0||CanGoState==2||CanGoState==3||CanGoState==6) cangof = 1;
  else cangof = 0;
  if(CanGoState==0||CanGoState==1||CanGoState==3||CanGoState==5) cangol = 1;
  else cangol = 0;
  if(CanGoState==0||CanGoState==1||CanGoState==2||CanGoState==4) cangor = 1;
  else cangor = 0;

  if(ant[AntNow].food) type = SMELL_TYPE_HOME;
  else type = SMELL_TYPE_FOOD;

  msf = GetMaxSmell(type,xxx,yyy,ddir);
  msl = GetMaxSmell(type,xxx,yyy,TurnLeft(ddir));
  msr= GetMaxSmell(type,xxx,yyy,TurnRight(ddir));
  maxms = MaxLocation(msf,msl,msr);
  /* maxms - 1 - msf is MAX
         2 - msl is MAX
         3 - msr is MAX
         0 - all 3 number is 0 */

  testdir = NULL;
  switch(maxms)
  {
    case 0: /* all is 0, keep testdir = NULL, random select dir */
        break;
    case 1: if(cangof)
          testdir = ddir;
        else
          if(msl>msr) if(cangol) testdir = TurnLeft(ddir);
          else if(cangor) testdir = TurnRight(ddir);
        break;
    case 2: if(cangol)
          testdir = TurnLeft(ddir);
        else
          if(msf>msr) if(cangof) testdir = ddir;
          else if(cangor) testdir = TurnRight(ddir);
        break;
    case 3: if(cangor)
          testdir = TurnRight(ddir);
        else
          if(msf>msl) if(cangof) testdir =ddir;
          else if(cangol) testdir = TurnLeft(ddir);
        break;
    default:break;
  } /* of maxms */

  randnum = random(1000);
  if(randnum/* 1. if testdir = NULL, means can not find the max smell or the dir to max smell can not go
     then random select dir
     2. if ant error, don't follow the smell, random select dir
  */
  {
    randnum = random(100);
    switch(CanGoState)
    {
      case 0: if(randnum<90) testdir = ddir;
          else if (randnum>=90&&randnum<95) testdir = TurnLeft(ddir);
          else testdir = TurnRight(ddir);
          break;
      case 1: if(randnum<50) testdir = TurnLeft(ddir);
          else testdir = TurnRight(ddir);
          break;
      case 2: if(randnum<90) testdir = ddir;
          else testdir = TurnRight(ddir);
          break;
      case 3: if(randnum<90) testdir = ddir;
          else testdir = TurnLeft(ddir);
          break;
      case 4: testdir = TurnRight(ddir);
          break;
      case 5: testdir = TurnLeft(ddir);
          break;
      case 6: testdir = ddir;
          break;
      case 7: testdir = TurnBack(ddir);
          break;
      default:testdir = TurnBack(ddir);
    } /* of can go state */
  }
  return(testdir);
}

int GetMaxSmell(int type,int xxx,int yyy,int ddir)
{
  int i,j;
  int ms; /* MAX smell */

  ms = 0;
  switch(ddir)
  {
    case UP:  for(i=xxx-ANT_EYESHOT;i<=xxx+ANT_EYESHOT;i++)
            for(j=yyy-ANT_EYESHOT;jif(!JudgeCanGo(i,j)) continue;
              if((i==food.xxx&&j==food.yyy&&type==SMELL_TYPE_FOOD)||
                 (i==home.xxx&&j==home.yyy&&type==SMELL_TYPE_HOME))
           {
                ms = MAX_SMELL;
               break;
           }
              if(IsTrace(i,j)) continue;
              if(Smell[type][i][j]>ms) ms = Smell[type][i][j];
          }
          break;
    case DOWN:  for(i=xxx-ANT_EYESHOT;i<=xxx+ANT_EYESHOT;i++)
            for(j=yyy+1;j<=yyy+ANT_EYESHOT;j++)
          {
              if(!JudgeCanGo(i,j)) continue;
              if((i==food.xxx&&j==food.yyy&&type==SMELL_TYPE_FOOD)||
                 (i==home.xxx&&j==home.yyy&&type==SMELL_TYPE_HOME))
           {
                ms = MAX_SMELL;
               break;
           }
              if(IsTrace(i,j)) continue;
              if(Smell[type][i][j]>ms) ms = Smell[type][i][j];
          }
          break;
    case LEFT:  for(i=xxx-ANT_EYESHOT;ifor(j=yyy-ANT_EYESHOT;j<=yyy+ANT_EYESHOT;j++)
          {
              if(!JudgeCanGo(i,j)) continue;
              if((i==food.xxx&&j==food.yyy&&type==SMELL_TYPE_FOOD)||
                 (i==home.xxx&&j==home.yyy&&type==SMELL_TYPE_HOME))
           {
                ms = MAX_SMELL;
               break;
           }
              if(IsTrace(i,j)) continue;
              if(Smell[type][i][j]>ms) ms = Smell[type][i][j];
          }
          break;
    case RIGHT: for(i=xxx+1;i<=xxx+ANT_EYESHOT;i++)
            for(j=yyy-ANT_EYESHOT;j<=yyy+ANT_EYESHOT;j++)
          {
              if(!JudgeCanGo(i,j)) continue;
              if((i==food.xxx&&j==food.yyy&&type==SMELL_TYPE_FOOD)||
                 (i==home.xxx&&j==home.yyy&&type==SMELL_TYPE_HOME))
           {
                ms = MAX_SMELL;
               break;
           }
              if(IsTrace(i,j)) continue;
              if(Smell[type][i][j]>ms) ms = Smell[type][i][j];
          }
          break;
    default:  break;
  }
  return(ms);
}

int IsTrace(int xxx,int yyy)
{
  int i;

  for(i=0;iif(ant[AntNow].tracex[i]==xxx&&ant[AntNow].tracey[i]==yyy) return(1);
  return(0);
}

int MaxLocation(int num1,int num2,int num3)
{
  int maxnum;

  if(num1==0&&num2==0&&num3==0) return(0);

  maxnum = num1;
  if(num2>maxnum) maxnum = num2;
  if(num3>maxnum) maxnum = num3;

  if(maxnum==num1) return(1);
  if(maxnum==num2) return(2);
  if(maxnum==num3) return(3);
}

int CanGo(int xxx,int yyy,int ddir)
/* input: xxx,yyy - location of ant
      ddir - now dir
   output: 0 - forward and left and right can go
       1 - forward can not go
       2 - left can not go
       3 - right can not go
       4 - forward and left can not go
       5 - forward and right can not go
       6 - left and right can not go
       7 - forward and left and right all can not go
*/
{
  int tx,ty,tdir;
  int okf,okl,okr;

  /* forward can go ? */
  tdir = ddir;
  tx = xxx;
  ty = yyy;
  switch(tdir)
  {
    case UP:  ty--;
          break;
    case DOWN:  ty++;
          break;
    case LEFT:  tx--;
          break;
    case RIGHT: tx++;
          break;
    default:  break;
  } /* of switch dir */
  if(JudgeCanGo(tx,ty)) okf = 1;
  else okf = 0;

  /* turn left can go ? */
  tdir = TurnLeft(ddir);
  tx = xxx;
  ty = yyy;
  switch(tdir)
  {
    case UP:  ty--;
          break;
    case DOWN:  ty++;
          break;
    case LEFT:  tx--;
          break;
    case RIGHT: tx++;
          break;
    default:  break;
  } /* of switch dir */
  if(JudgeCanGo(tx,ty)) okl = 1;
  else okl = 0;

  /* turn right can go ? */
  tdir = TurnRight(ddir);
  tx = xxx;
  ty = yyy;
  switch(tdir)
  {
    case UP:  ty--;
          break;
    case DOWN:  ty++;
          break;
    case LEFT:  tx--;
          break;
    case RIGHT: tx++;
          break;
    default:  break;
  } /* of switch dir */
  if(JudgeCanGo(tx,ty)) okr = 1;
  else okr = 0;

  if(okf&&okl&&okr) return(0);
  if(!okf&&okl&&okr) return(1);
  if(okf&&!okl&&okr) return(2);
  if(okf&&okl&&!okr) return(3);
  if(!okf&&!okl&&okr) return(4);
  if(!okf&&okl&&!okr) return(5);
  if(okf&&!okl&&!okr) return(6);
  if(!okf&&!okl&&!okr) return(7);
  return(7);
}

int JudgeCanGo(int xxx,int yyy)
/* input: location to judeg
   output: 0 -- can not go
       1 -- can go
*/
{
  int i,j;

  if(xxx<=0||xxx>MAXX) return(0);
  if(yyy<=0||yyy>MAXY) return(0);
  if(block[xxx][yyy]) return(0);
  return(1);
}

int TurnLeft(int ddir)
{
  switch(ddir)
  {
    case UP:  return(LEFT);
    case DOWN:  return(RIGHT);
    case LEFT:  return(DOWN);
    case RIGHT: return(UP);
    default:  break;
  } /* of switch dir */
}

int TurnRight(int ddir)
{
  switch(ddir)
  {
    case UP:  return(RIGHT);
    case DOWN:  return(LEFT);
    case LEFT:  return(UP);
    case RIGHT: return(DOWN);
    default:  break;
  } /* of switch dir */
}

int TurnBack(int ddir)
{
  switch(ddir)
  {
    case UP:  return(DOWN);
    case DOWN:  return(UP);
    case LEFT:  return(RIGHT);
    case RIGHT: return(LEFT);
    default:  break;
  } /* of switch dir */
}