Ant colony ACO (ant colony optimization) principles and the achievement of the source code

Basically, before the algorithm that are more boring (nonsense, the algorithm is very boring ... ...), this time to introduce the ant colony algorithm (Ant Colony Algorithm) is a kind of algorithm derived from natural phenomena, but also a meta heuristic , that has little to do with the specific problems of the optimization algorithm, that is, it is used to find the optimal path in the graph the probability of technologies. Marco Dorigo in 1992, his doctoral thesis in the introduction, its inspiration from the ants found in the course of the path in search of food behavior.

Little ants are always able to find food, what kind of intelligence they have it? Vision, if we are to design an artificial intelligence program ant, then the procedure to how complicated? First, you let the ants can avoid obstacles, terrain must be based on appropriate commands to it into a cleverly so that they can avoid obstacles and, secondly, let the ants find food, they need all the space they traverse point; again, if you want the ants to find the shortest path, then the need to calculate all possible paths and compare their size, but more importantly, you have to careful programming, because the program's error may let you come to naught. What an incredible program! Too complicated, I am afraid that no one could accomplish this tedious redundancy procedures.

Why make such a simple procedure to do such complicated things ants? The answer is: the emergence of simple rules. In fact, each ant is not as we imagine the whole world needs to know the information, they are actually only interested in immediate information within a limited scope, and local information using these few simple rules to make decisions, so that the ant This group, the complexity of behavior will be exposed. This is artificial life, complexity science to explain the law!

The following is the realization of such a complex, seven simple rules:

1, range:
Ants observed range is a square in the world, ants have a parameter for the speed of the radius (usually 3), then it is observed in the range 3 * 3 grid in the world, and can also move away from this range inside.
2, Environment:
Ant where the environment is a virtual world in which there are obstacles, there are other ants, as well as pheromone information known two types of ants to find food, the food shed pheromone, a nest is found shed in the nest of ants pheromone. Each ant is only able to perceive it within the scope of environmental information. Environment to a certain rate so that pheromone disappears.
3, feeding rules:
Each ant can sense in the context of looking for whether there is food, if directly in the past. Otherwise, see if there are pheromones, and more at what point the perception of the pheromone within the maximum, so that it more towards the place to go pheromone and the ants will be more than a small probability of mistakes, which is not to Move up to the point of pheromone. Ant nest to find the rules and as above, but its nest pheromone response, but did not respond to food pheromone.
4, mobile rules:
Each ant is the direction towards the pheromone of the most moving, and when around the time the guidelines have not pheromones, ants will be in accordance with their original direction of movement of inertia of the movement continues, and, in the direction of movement has a small random perturbation. To prevent ants in situ circular motion, it will remember what has just gone through a point, if we find the next point to go have recently gone through, it will try to avoid.
5, obstacle avoidance rules:
If you want to move in the direction of the ant obstacles block, it will randomly select another direction, and there are pheromone guidelines, then it will follow the rules of foraging behavior.
7, sow pheromone rules:
Ants nest in just the time to find food or pheromone spreading hair up, and gone the distance with it, spreads less and less pheromone.

The following program starts running, the ants began flew from the nest to find food; they will follow the screen covered with the screen, until you find the food and then return to nest.

One, 'F' point that food, 'H' that hole, white block that obstacle, '+' is the ants.

Parameters:
Maximum factors: ants at the beginning of the total pheromone owned, the greater that procedures exist in the longer period of time to pheromone. Pheromone reduction of speed: over time, already exists in the world will reduce the pheromone, the greater this value, then the reduction of the faster.
Error probability that the ants do not go to the largest regional walking pheromone probability that the ant is larger the more innovative.
Speed radius that ants can go a maximum length, but also the perception that the scope of this ant.
Memory that can remember the number of ants just passed the coordinates of points, the value to avoid the ants in the local spinning, standing still. And this value is greater then the speed will slow the whole system, the smaller ants are more easily spot a circular motion.

 Source code is as follows  ( Different compiler may need to be modified  ):
#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,&regs0,&regs0);
}

void ResetCur(void)
{
  union REGS regs0;
  regs0.h.ah=1;
  regs0.h.ch=0x06;
  regs0.h.cl=0x07;
  int86(0x10,&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)
           {
                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;AntNow<MAX_ANT;AntNow++)
  {
    ant[AntNow].SpeedTimer+=timer10ms;
    if(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<TRACE_REMEMBER;i++)
       {
          ant[AntNow].tracex[i] = 0;
          ant[AntNow].tracey[i] = 0;
       }
        ant[AntNow].TracePtr = 0;
        CanFindFood = 1;
      } /* 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<SMELL_DROP_RATE*1000||testdir==NULL)
  /* 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;j<yyy;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 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;i<xxx;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;
    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;i<TRACE_REMEMBER;i++)
    if(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 */
}

  
分类:Tech 时间:2010-03-18 人气:381
分享到:
blog comments powered by Disqus

相关文章

  • The shortest path - Dijkstra Algorithm 2010-05-04

    Dijkstra algorithm is used to solve a directed graph (can also be an undirected graph, undirected graph is a special case of a directed graph) of a point (called the origin) to the remaining points (called neighboring points) of the shortest path pro

  • The single source shortest path - Bellman-Ford algorithm optimization 2011-01-08

    Bellman-Ford single source shortest path to solve the problem, compared to Dijkastra, it is less restrictive: Edge weights can be negative. At the same time, can also detect a negative ring (positive loop). However, the Bellman-Ford ordinary time com

  • Single-source shortest path of SPFA - Shortest Path Faster Algorithm 2011-01-09

    Is very good SPFA the shortest path algorithm, we should grasp. SPFA on the Bellman-Ford algorithm to optimize the key is to realize that: Only those who changed the relaxation of the former over the distance of the point estimates, it may cause the

  • [Transfer] A * algorithm using the heuristic function (1) 2010-10-05

    Links: http://godorz.info/2009/11/heuristics-1/ A * algorithm uses a heuristic function h (n) to get from any node to destination node n went to the estimated minimum cost, so choose a good heuristic function is very important. A * algorithm using th

  • [Transfer] A * algorithm is a heuristic function to use (1) 2010-10-05

    Links: http://godorz.info/2009/11/heuristics-1/ A * algorithm uses a heuristic function h (n) to get from any node to destination node n went to the estimated minimum cost, so choose a good heuristic function is very important. A * algorithm using th

  • [Turn] game programming pathfinding algorithm 2011-02-17

    http://blog.csdn.net/ityuany/archive/2010/04/21/5509750.aspx In recent years, the game industry's rapid development led to game artificial intelligence (Artificial Intelligence, referred to as AI) development, more and more of the game using artifici

  • As3 A * pathfinding algorithm tutorial 2010-11-11

    Although the A * (pronounced A star) algorithm is more esoteric beginners, but once you find the opportunities, and it will become very simple. There are many online articles explain the A * algorithm, but most is for those who have some basic viewed

  • visualrules business rules platform features custom value 2010-11-12

    VisualRules rules engine is developed on the basis of a product, adhering to the rules engine can change the business logic programs can be independent of the characteristics of outside, combined with the characteristics of the domestic software proj

  • A little more information about the network analysis! (Rpm) 2010-12-01

    Some time before the network analysis to user training, and accumulated a little scattered information. We want to be helpful Network type (1) Transportation Network: a Undirected Network. Edge Network, with the direction that the user can freely def

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

Copyright (C) codeweblog.com, All Rights Reserved.

CodeWeblog.com 版权所有 黔ICP备15002463号-1

processed in 0.405 (s). 13 q(s)