游戲類庫-搜索算法

//搜索算法.cpp



#include "stdafx.h"

#include "搜索算法.h"

/////////////////////////////////////////////////////////////////////////////

findpt::findpt(){} //構(gòu)造函數(shù)

findpt::~findpt(){} //析構(gòu)函數(shù)

/////////////////////////////////////////////////////////////////////////////

// 初始化隊列

void findpt::init_queue()

{ queue=(LINK)malloc(sizeof(*queue));

queue->node=NULL;

queue->f=-1;

queue->next=(LINK)malloc(sizeof(*queue));

queue->next->f=MAXINT;

queue->next->node=NULL;

queue->next->next=NULL;

}

// 待處理節(jié)點(diǎn)入隊列, 依*對目的地估價距離插入排序

void findpt::enter_queue(TREE node,int f)

{ LINK p=queue,father,q;

while(f>p->f)

{ father=p; p=p->next;}

q=(LINK)malloc(sizeof(*q));

q->f=f,q->node=node,q->next=p;

father->next=q;

}

// 將離目的地估計最近的方案出隊列

TREE findpt::get_from_queue()

{ TREE bestchoice=queue->next->node;

LINK next=queue->next->next;

free(queue->next);

queue->next=next;

stack[stacktop++]=bestchoice;

return bestchoice;

}

// 釋放申請過的所有節(jié)點(diǎn)

void findpt::freetree()

{ int i;

LINK p;

for (i=0;i<stacktop;i++) free(stack[i]);

while (queue)

{ p=queue;

free(p->node);

queue=queue->next;

free(p);

}

free(queue);

}

// 估價函數(shù),估價 x,y 到目的地的距離,估計值必須保證比實(shí)際值小

int findpt::judge(int x,int y)

{ int distance;

distance=abs(end_x-x)+abs(end_y-y);

return distance;

}

// 嘗試下一步移動到 x,y 可行否

int findpt::trytile(int x,int y,TREE father)

{ TREE p=father;

int h;

if (map[y][x]!=’0’) return 1; //如果(x,y)處是障礙,失敗

h=father->h+1;

if (h>=dis_map[y][x]) return 1; // 如果曾經(jīng)有更好的方案移動到 (x,y) 失敗

dis_map[y][x]=h; // 記錄這次到 (x,y) 的距離為歷史最佳距離

// 將這步方案記入待處理隊列

p=(TREE)malloc(sizeof(*p));

p->father=father;

p->h=father->h+1;

p->tile=tile_num(x,y);

enter_queue(p,p->h+judge(x,y));

return 0;

}



// 路徑尋找主函數(shù)

int findpt::findpath()

{ TREE root;

int i,j;

stacktop=0;

for (i=0;i<map_h;i++)

for (j=0;j<map_w;j++)

dis_map[i][j]=MAXINT;

init_queue();

root=(TREE)malloc(sizeof(*root));

root->tile=tile_num(start_x,start_y);

root->h=0;

root->father=NULL;

enter_queue(root,judge(start_x,start_y));

for (;;)

{ int x,y,child;

root=get_from_queue();

if (root==NULL)

{*path=-1; 

free(root); freetree();//釋放

return -1;

}

x=tile_x(root->tile);

y=tile_y(root->tile);

if (x==end_x && y==end_y) break;//達(dá)到目的地成功返回

child =trytile(x, y-1,root); //嘗試向北 移動

child&=trytile(x+1,y-1,root); //嘗試向東北移動

child&=trytile(x+1,y, root); //嘗試向東 移動

child&=trytile(x+1,y+1,root); //嘗試向東南移動

child&=trytile(x, y+1,root); //嘗試向南 移動

child&=trytile(x-1,y+1,root); //嘗試向西南移動

child&=trytile(x-1,y, root); //嘗試向西 移動

child&=trytile(x-1,y-1,root); //嘗試向西北移動

if (child!=0) free(stack[--stacktop]);

//如果8個方向均不能移動,釋放這個死節(jié)點(diǎn)(釋放棧頂節(jié)點(diǎn))

}

// 回溯樹，將求出的最佳路徑保存在 path[] 中

for (i=0;root;i++)

{ path[i]=root->tile; root=root->father;}

path[i]=-1;

free(root); freetree();//釋放

return 0;

}



=========================================================================================



//搜索算法.h



#include "常數(shù)定義.h"



#define MAXINT 8192 //定義一個最大整數(shù), 地圖上任意兩點(diǎn)距離不會超過它8192 

#define STACKSIZE 40000 //保存搜索節(jié)點(diǎn)的堆棧大小65536

#define tile_num(x,y) ((y)*map_w+(x)) //將 x,y 坐標(biāo)轉(zhuǎn)換為地圖上塊的編號

#define tile_x(n) ((n)%map_w) //由塊編號得出 x,y 坐標(biāo)

#define tile_y(n) ((n)/map_w)

//定義結(jié)構(gòu)----------------------------------------------------------------------

typedef struct node *TREE;// 樹結(jié)構(gòu)

struct node

{int h; int tile; TREE father;};

typedef struct node2 *LINK;// 樹結(jié)構(gòu)

struct node2

{ TREE node; int f; LINK next;};

//---------------------------------------------

class findpt

{public: findpt(); //構(gòu)造函數(shù)

virtual~findpt(); //析構(gòu)函數(shù)

public://公有,外部可調(diào)用

int path[MAXINT];

char map[WIDTH*SCRP/GX+2][HEIGHT*SCRP/GY+2]; //地圖障礙格數(shù)據(jù)

short int dis_map[WIDTH*SCRP/GX+2][HEIGHT*SCRP/GY+2];//保存搜索路徑時,中間目標(biāo)地最優(yōu)解

int map_w,map_h; //地圖障礙格寬和高

int start_x,start_y,end_x,end_y; //起點(diǎn)坐標(biāo),終點(diǎn)坐標(biāo)



int findpath(); //路徑尋找主函數(shù)

private://私有,類內(nèi)部使用

LINK queue; //保存沒有處理的行走方法的節(jié)點(diǎn)

TREE stack[STACKSIZE]; //保存已經(jīng)處理過的節(jié)點(diǎn)(搜索完后釋放)

int stacktop;



void init_queue(); // 初始化隊列

void enter_queue(TREE node,int f); //待處理節(jié)點(diǎn)入隊列,依*對目的地估價距離插入排序

TREE get_from_queue(); //將離目的地估計最近的方案出隊列

void freetree(); //釋放申請過的所有節(jié)點(diǎn)

int judge(int x,int y); //估價函數(shù),估價x,y到目的地的距離,估計值必須保證比實(shí)際值小

int trytile(int x,int y,TREE father);//嘗試下一步移動到x,y可行否

}; 

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1595082