蟻群算法(C/C++實現)
作者：      來源：zz     發表時間：2007-07-02     瀏覽次數： 3198      字號：大  中  小

源代碼如下：

/*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,&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);