a star algorithm/A* algorithm
Posted on | 六月 5, 2010 | No Comments
A star算法在静态路网中的应用
#include <string.h>
#include<stdio.h >
#define MAPW 21
#define MAPH 21
//a star path finding take 2
//create a list struct for the path
struct list_s
{
int x;
int y;
int f;
} path[10000];
struct NODE
{
int walkable;
int onopen;
int onclosed;
int g;
int h;
int f;
int parentx;
int parenty;
} node[MAPW][MAPH];
void initnodes()
{
int x,y;
for(x=0;x<MAPW;x++)
{
for(y=0;y<MAPH;y++)
{
node[x][y].walkable = getpixel(map,x,y);
node[x][y].onopen = FALSE;
node[x][y].onclosed = FALSE;
node[x][y].g = 0;
node[x][y].h = 0;
node[x][y].f = 0;
node[x][y].parentx = NULL;
node[x][y].parenty = NULL;
}
}
}
int *findpath(int startx, int starty, int endx, int endy)
{
int x=0,y=0; // for running through the nodes
int dx,dy; // for the 8 squares adjacent to each node
int currentx=startx, currenty=starty;
int lowestf=10000; // start with the lowest being the highest
// add starting node to open list
node[startx][starty].onopen = TRUE;
while (!node[currentx][currenty].onclosed) //stop when the current node is on the closed list
{
//look for lowest F cost node on open list – this becomes the current node
for(x=0;x<MAPW;x++)
{
for(y=0;y<MAPY;y++)
{
node[x][y].f = node[x][y].g + node[x][y].h;
if(node[x][y].onopen)
if(node[x][y].f<lowestf) { currentx = x; currenty = y; lowestf = node[x][y].f;}
}
}
// we found it, so now put that node on the closed list
node[currentx][currenty].onopen = FALSE;
node[currentx][currenty].onclosed = TRUE;
// for each of the 8 adjacent node
for(dx=-1;dx<=1;dx++)
{
for(dy=-1;dy<=1;dy++)
{
// if its walkable and not on the closed list
if(node[currentx+dx][currenty+dy].walkable || !node[currentx+dx][currenty+dy].onclosed)
{
//if its not on open list
if(!node[currentx+dx][currenty+dy].onopen)
{
//add it to open list
node[currentx+dx][currenty+dy].onopen = TRUE; node[currentx+dx][currenty+dy].onclosed = FALSE;
//make the current node its parent
node[currentx+dx][currenty+dy].parentx = currentx;
node[currentx+dx][currenty+dy].parenty = currenty;
//work out G
if(dx!=0 && dy!=0) node[currentx+dx][currenty+dy].g = 14; // diagonals cost 14
else node[currentx+dx][currenty+dy].g = 10; // straights cost 10
//work out H
//MANHATTAN METHOD
node[currentx+dx][currenty+dy].h = abs(endx-currentx+dy + endy-currenty+dy) * 10;
}
//otherwise it is on the open list
else
{
if(dx==0 || dy==0) // if its not a diagonal
if(node[currentx+dx][currenty+dy].g!=10) //and it was previously
{
node[currentx+dx][currenty+dy].g = 10; // straight score 10
//change its parent because its a shorter distance
node[currentx+dx][currenty+dy].parentx = currentx;
node[currentx+dx][currenty+dy].parenty = currenty;
//recalc H
node[currentx+dx][currenty+dy].h = abs(endx-currentx+dy + endy-currenty+dy) * 10;
//recalc F
node[currentx+dx][currenty+dy].f = node[currentx+dx][currenty+dy].g + node[currentx+dx][currenty+dy].h;
}
}//end else
}// end if walkable and not on closed list
}
}//end for each 8 adjacent node
}//end while
//put the parent nodes into a list ordered from highest to lowest f value
//first count how many there are
int count=0;
for(x=0;x<MAPW;x++)
{
for(y=0;y<MAPY;y++)
{
if(node[x][y].onclosed) { path[count].x = x; path[count].y = y; path[count].f = node[x][y].f; count++; }
}
}
//sort them
qsort (path, count, sizeof(struct list_s), compare);
return &path; //we’re done, return a pointer to the final path;
}//end function
//sorting stuff
int compare (const struct list_s * a, const struct list_s * b)
{
return ( a->f – b->f );
}
主要搜索过程： 创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值-> While(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) break; else { if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值 if( X的估价值小于OPEN表的估价值 ) 更新OPEN表中的估价值; //取最小路径的估价值 if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值 if( X的估价值小于CLOSE表的估价值 ) 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值 if(X not in both) 求X的估价值; 并将X插入OPEN表中; //还没有排序 } 将n节点插入CLOSE表中; 按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
相关文章:
评论|Comments
留言|Leave a Reply
Archives
- 2012年五月 (1)
- 2012年四月 (1)
- 2012年三月 (3)
- 2012年一月 (1)
- 2011年十二月 (1)
- 2011年十一月 (4)
- 2011年十月 (3)
- 2011年九月 (2)
- 2011年八月 (1)
- 2011年七月 (1)
- 2011年五月 (1)
- 2011年三月 (3)
- 2011年二月 (2)
- 2011年一月 (6)
- 2010年十一月 (2)
- 2010年十月 (10)
- 2010年九月 (7)
- 2010年八月 (4)
- 2010年七月 (11)
- 2010年六月 (14)
- 2010年五月 (14)
- 2010年四月 (20)
- 2010年三月 (61)
- 2010年二月 (71)
- 2010年一月 (59)
- 2009年十二月 (78)
- 2009年十一月 (61)
链接表
SUNSHINE
About
