蟻群算法程序

#defineSPACE0x20

#defineESC0x1b

#defineANT_CHAR_EMPTY'+'#defineANT_CHAR_FOOD153#defineHOME_CHAR'H'#defineFOOD_CHAR'F'#defineFOOD_CHAR2'f'

#defineFOOD_HOME_COLOR12

#defineBLOCK_CHAR177#defineMAX_ANT50

#defineINI_SPEED3

#defineMAXX80

#defineMAXY23

#defineMAX_FOOD10000#defineTARGET_FOOD200#defineMAX_SMELL5000#defineSMELL_DROP_RATE0.05#defineANT_ERROR_RATE0.02#defineANT_EYESHOT3

#defineSMELL_GONE_SPEED50#defineSMELL_GONE_RATE0.05#defineTRACE_REMEMBER50#defineMAX_BLOCK100

#defineNULL0

#defineUP1

#defineDOWN2

#defineLEFT3

#defineRIGHT4

#defineSMELL_TYPE_FOOD0#defineSMELL_TYPE_HOME1#include"stdio.h"

#include"conio.h"

#include"dos.h"

#include"stdlib.h"

#include"dos.h"

#include"process.h"

#include"ctype.h"

#include"math.h"

voidWorldInitial(void);voidBlockInitial(void);voidCreatBlock(void);

voidHomeFoodInitial(void);

voidAntInitial(void);

voidWorldChange(void);

voidAntMove(void);

voidAntOneStep(void);voidDealKey(charkey);

voidClearSmellDisp(void);

voidDispSmell(inttype);

intAntNextDir(intxxx,intyyy,intddir);

intGetMaxSmell(inttype,intxxx,intyyy,intddir);intIsTrace(intxxx,intyyy);

intMaxLocation(intnum1,intnum2,intnum3);

intCanGo(intxxx,intyyy,intddir);

intJudgeCanGo(intxxx,intyyy);

intTurnLeft(intddir);

intTurnRight(intddir);

intTurnBack(intddir);

intMainTimer(void);

charWaitForKey(intsecnum);voidDispPlayTime(void);

intTimeUse(void);voidHideCur(void);voidResetCur(void);

structHomeStruct

{

intxxx,yyy;

intamount;

intTargetFood;

}home;

structFoodStruct

{

intxxx,yyy;

intamount;

}food;

structAntStruct

{

intxxx,yyy;

intdir;

intspeed;

intSpeedTimer;

intfood;

intSmellAmount[2];

inttracex[TRACE_REMEMBER];

inttracey[TRACE_REMEMBER];intTracePtr;

intIQ;

}ant[MAX_ANT];

intAntNow;inttimer10ms;structtimestarttime,endtime;

intSmell[2][MAXX+1][MAXY+1];

intblock[MAXX+1][MAXY+1];

intSmellGoneTimer;

intSmellDispFlag;intCanFindFood;

intHardtoFindPath;

voidmain(void)

{

charKeyPress;inttu;

clrscr();HideCur();

WorldInitial();

do{

timer10ms=MainTimer();if(timer10ms)AntMove();if(timer10ms)WorldChange();

tu=TimeUse();if(tu>=60&&!CanFindFood)

{gotoxy(1,MAXY+1);printf("Cannotfindfood,maybeablockworld.");WaitForKey(10);

WorldInitial();

}if(tu>=180&&home.amount<100&&!HardtoFindPath)

{gotoxy(1,MAXY+1);printf("God!itissodifficulttofindapath.");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();

}elseif(kbhit())

{KeyPress=getch();DealKey(KeyPress);

}elseKeyPress=NULL;

}while(KeyPress!=ESC);gettime(&endtime);DispPlayTime();WaitForKey(10);clrscr();

ResetCur();

}

intMainTimer(void)

{

staticintoldhund,oldsec;structtimet;

inttimeuse;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;

}elsetimeuse=0;return(timeuse);

charWaitForKey(intsecnum)

{

intsecin,secnow;

intminin,minnow;

inthourin,hournow;

intsecuse;

structtimet;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);elsesecuse=secnow-secin;

if(secuse<0)

{gotoxy(1,MAXY+1);printf("Timeconutingerror,anykeytoexit...");getch();

exit(3);

}

}while(secuse<=secnum);return(NULL);

}

voidDispPlayTime(void)

{

intph,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("Timeuse:%dhour-%dmin-%dsec",ph,pm,ps);

intTimeUse(void)

{

intph,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)));

}

voidHideCur(void)

{

unionREGSregs0;regs0.h.ah=1;regs0.h.ch=0x30;regs0.h.cl=0x31;int86(0x10,®s0,®s0);

}

voidResetCur(void)

{

unionREGSregs0;

regs0.h.ah=1;regs0.h.ch=0x06;

regs0.h.cl=0x07;int86(0x10,®s0,®s0);

}

voidWorldInitial(void)

{

intk,i,j;

randomize();

clrscr();

HomeFoodInitial();for(AntNow=0;AntNow<MAX_ANT;AntNow++){

AntInitial();

};

BlockInitial();

for(k=0;k<=1;k++)

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;

}

voidBlockInitial(void)

{

inti,j;

intbn;

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();

}

voidCreatBlock(void)

{

intx1,y1,x2,y2;

intdx,dy;

inti,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);

}

voidHomeFoodInitial(void)

{

intrandnum;

inthomeplace;

randnum=random(100);

if(randnum<25)homeplace=1;

elseif(randnum>=25&&randnum<50)homeplace=2;

elseif(randnum>=50&&randnum<75)homeplace=3;

elsehomeplace=4;

switch(homeplace)

{

case1: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;

case2: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;

case3: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;

case4: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;

home.amount=0;

home.TargetFood=(food.amount<TARGET_FOOD)?food.amount:TARGET_FOOD;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("Worldinitialfail,anykeytoexit...");

getch();

exit(2);

gotoxy(home.xxx,home.yyy);putch(HOME_CHAR);gotoxy(food.xxx,food.yyy);putch(FOOD_CHAR);

}

voidAntInitial(void)

{

intrandnum;

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

randnum=random(100);if(randnum<25)ant[AntNow].dir=UP;

elseif(randnum>=25&&randnum<50)ant[AntNow].dir=DOWN;

elseif(randnum>=50&&randnum<75)ant[AntNow].dir=LEFT;elseant[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;

}

voidWorldChange(void)

{

intk,i,j;

intsmelldisp;

SmellGoneTimer+=timer10ms;if(SmellGoneTimer>=SMELL_GONE_SPEED){

SmellGoneTimer=0;for(k=0;k<=1;k++)

for(i=1;i<=MAXX;i++)for(j=1;j<=MAXY;j++)

{

if(Smell[k][i][j])

{

smelldisp1+((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));

else

{if(smelldisp>9)putch('#');elseputch(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);

}

}

}

}

}

}

voidAntMove(void)

{

intantx,anty;

intsmelltodrop,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);

if(ant[AntNow].food)putch(ANT_CHAR_FOOD);

elseputch(ANT_CHAR_EMPTY);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;antx=ant[AntNow].xxx;

anty=ant[AntNow].yyy;

if(ant[AntNow].food)

{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;ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]-=smelltodrop;if(ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]<0)ant[AntNow].SmellAmount[SMELL_TYPE_FOOD]=0;

}

}

else

{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;ant[AntNow].SmellAmount[SMELL_TYPE_HOME]-=smelltodrop;if(ant[AntNow].SmellAmount[SMELL_TYPE_HOME]<0)ant[AntNow].SmellAmount[SMELL_TYPE_HOME]=0;

}

}

}

}

textcolor(FOOD_HOME_COLOR);

gotoxy(home.xxx,home.yyy);putch(HOME_CHAR);

gotoxy(food.xxx,food.yyy);

if(food.amount>0)putch(FOOD_CHAR);

elseputch(FOOD_CHAR2);

textcolor(7);

gotoxy(1,MAXY+1);

printf("Food%d,Home%d",food.amount,home.amount);

voidAntOneStep(void)

{

intddir,tttx,ttty;

inti;

ddir=ant[AntNow].dir;

tttx=ant[AntNow].xxx;

ttty=ant[AntNow].yyy;

ddir=AntNextDir(tttx,ttty,ddir);switch(ddir)

{

caseUP: ttty--;

break;

caseDOWN:ttty++;

break;

caseLEFT:tttx--;

break;

caseRIGHT:tttx++;

break;

default:break;

}

ant[AntNow].dir=ddir;

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

if(ant[AntNow].food)

{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;

}

else

{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;

if(tttx==home.xxx&&ttty==home.yyy)ant[AntNow].SmellAmount[SMELL_TYPE_HOME]=MAX_SMELL;

}

}

voidDealKey(charkey)

{

inti;

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();

}

elseSmellDispFlag=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;

default:gotoxy(1,MAXY+1);for(i=1;i<=MAXX-1;i++)putch(SPACE);

}

}

voidClearSmellDisp(void)

{

intk,i,j;

for(k=0;k<=1;k++)for(i=1;i<=MAXX;i++)

for(j=1;j<=MAXY;j++){

if(Smell[k][i][j])

{gotoxy(i,j);putch(SPACE);

}}

}

voidDispSmell(inttype)

{

intk,i,j;

intfromk,tok;

intsmelldisp;switch(type)

{

case0:fromk=0;tok=0;break;

case1:fromk=1;tok=1;break;

case2:fromk=0;tok=1;break;

default:fromk=0;tok=1;break;

}SmellGoneTimer=0;

for(k=fromk;k<=tok;k++)

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));

else{

if(smelldisp>9)putch('#');

elseputch(smelldisp+'0');

}

}

}

}

}

intAntNextDir(intxxx,intyyy,intddir)

{

intrandnum;

inttestdir;

intCanGoState;

intcangof,cangol,cangor;

intmsf,msl,msr,maxms;

inttype;

CanGoState=CanGo(xxx,yyy,ddir);if(CanGoState==0||CanGoState==2||CanGoState==3||CanGoState==6)cangof=1;elsecangof=0;

if(CanGoState==0||CanGoState==1||CanGoState==3||CanGoState==5)cangol=1;elsecangol=0;

if(CanGoState==0||CanGoState==1||CanGoState==2||CanGoState==4)cangor=1;elsecangor=0;

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

elsetype=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);

testdir=NULL;switch(maxms)

case0:break;

case1:if(cangof)

testdir=ddir;

else

if(msl>msr)if(cangol)testdir=TurnLeft(ddir);elseif(cangor)testdir=TurnRight(ddir);break;

case2:if(cangol)

testdir=TurnLeft(ddir);

else

if(msf>msr)if(cangof)testdir=ddir;elseif(cangor)testdir=TurnRight(ddir);

break;

case3:if(cangor)

testdir=TurnRight(ddir);

else

if(msf>msl)if(cangof)testdir=ddir;elseif(cangol)testdir=TurnLeft(ddir);

break;default:break;

}

randnum=random(1000);

if(randnum<SMELL_DROP_RATE*1000||testdir==NULL)

{

randnum=random(100);switch(CanGoState){

case0:if(randnum<90)testdir=ddir;

elseif(randnum>=90&&randnum<95)testdir=TurnLeft(ddir);elsetestdir=TurnRight(ddir);

break;

case1:if(randnum<50)testdir=TurnLeft(ddir);

elsetestdir=TurnRight(ddir);break;

case2:if(randnum<90)testdir=ddir;elsetestdir=TurnRight(ddir);break;

case3:if(randnum<90)testdir=ddir;

elsetestdir=TurnLeft(ddir);break;

case4:testdir=TurnRight(ddir);

break;

case5:testdir=TurnLeft(ddir);

break;

case6:testdir=ddir;

break;

case7:testdir=TurnBack(ddir);

break;default:testdir=TurnBack(ddir);

}

}return(testdir);

}

intGetMaxSmell(inttype,intxxx,intyyy,intddir)

{

inti,j;

intms;

ms=0;

switch(ddir)

{

caseUP: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;

caseDOWN: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;

caseLEFT: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;

caseRIGHT: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);

}

intIsTrace(intxxx,intyyy)

{

inti;for(i=0;i<TRACE_REMEMBER;i++)

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

}

intMaxLocation(intnum1,intnum2,intnum3){

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