?? astar.cpp
字號:
// AStar.cpp: implementation of the CAStar class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "SearchPath.h"
#include "AStar.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
extern map[Height][Width];
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CAStar::CAStar()
{
for(int i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
{
m_close[i][j]=0;
m_open[i][j]=0;
m_element[i][j] = &node[i][j];
m_element[i][j]->close=0;
m_element[i][j]->open=0;
m_element[i][j]->parent=NULL;
m_element[i][j]->fore=NULL;
m_element[i][j]->next=NULL;
m_element[i][j]->f=-1;
}
}
targetX=0;
targetY=0;
}
CAStar::~CAStar()
{
}
int CAStar::A()
{
while(head!=NULL)
{
as_node *tempHead;
if(head->next==NULL)
{
tempHead=NULL;
}
else
{
tempHead=head->next;//head下一個節點作為新的鏈表頭指針
head->next->fore=NULL;
}
m_element[head->y][head->x]->open=0;
m_element[head->y][head->x]->close=1;//把head放進close表
if(map[head->y][head->x+1]!=-1)//如果臨近的方格不是墻壁
{
if(m_element[head->y][head->x+1]->close)
{}
else if(m_element[head->y][head->x+1]->open)
{
int temp = m_element[head->y][head->x]->g+1+m_element[head->y][head->x+1]->h;
if(m_element[head->y][head->x+1]->f > temp)
{
m_element[head->y][head->x+1]->g = m_element[head->y][head->x]->g+1;
m_element[head->y][head->x+1]->f = temp;
m_element[head->y][head->x+1]->parent = m_element[head->y][head->x];
tempHead=adjustNode(tempHead,m_element[head->y][head->x+1]);
}
}
else
{
if(head->x+1==targetX && head->y==targetY){return 1;}//找到終點！//修改這里
//as_node *node=new as_node;
as_node *node=m_element[head->y][head->x+1];
node->x=head->x+1;//修改這里
node->y=head->y;//修改這里
node->open=1;
node->close=0;
node->parent=m_element[head->y][head->x];
node->g=node->parent->g+1;
node->h=abs(node->x - targetX) + abs(node->y - targetY);
node->f=node->g + node->h;
tempHead=insertNode(tempHead,node);
}
//最后記住把head放進close表
}
if(map[head->y][head->x-1]!=-1)//如果臨近的方格不是墻壁
{
if(m_element[head->y][head->x-1]->close)
{}
else if(m_element[head->y][head->x-1]->open)
{
int temp = m_element[head->y][head->x]->g+1+m_element[head->y][head->x-1]->h;
if(m_element[head->y][head->x-1]->f > temp)
{
m_element[head->y][head->x-1]->g = m_element[head->y][head->x]->g+1;
m_element[head->y][head->x-1]->f = temp;
m_element[head->y][head->x-1]->parent=m_element[head->y][head->x];
tempHead=adjustNode(tempHead,m_element[head->y][head->x-1]);
}
}
else
{
if(head->x-1==targetX && head->y==targetY){return 1;}//找到終點！//修改這里
//as_node *node=new as_node;
as_node *node=m_element[head->y][head->x-1];
node->x=head->x-1;//修改這里
node->y=head->y;//修改這里
node->open=1;
node->close=0;
node->parent=m_element[head->y][head->x];
node->g=node->parent->g+1;
node->h=abs(node->x - targetX) + abs(node->y - targetY);
node->f=node->g + node->h;
tempHead=insertNode(tempHead,node);
}
//最后記住把head放進close表
}
if(map[head->y+1][head->x]!=-1)//如果臨近的方格不是墻壁
{
if(m_element[head->y+1][head->x]->close)
{}
else if(m_element[head->y+1][head->x]->open)
{
int temp = m_element[head->y][head->x]->g+1+m_element[head->y+1][head->x]->h;
if(m_element[head->y+1][head->x]->f > temp)
{
m_element[head->y+1][head->x]->g = m_element[head->y][head->x]->g+1;
m_element[head->y+1][head->x]->f = temp;
m_element[head->y+1][head->x]->parent=m_element[head->y+1][head->x];
tempHead=adjustNode(tempHead,m_element[head->y+1][head->x]);
}
}
else
{
if(head->x==targetX && head->y+1==targetY){return 1;}//找到終點！//修改這里
//as_node *node=new as_node;
as_node *node=m_element[head->y+1][head->x];
node->x=head->x;//修改這里
node->y=head->y+1;//修改這里
node->open=1;
node->close=0;
node->parent=m_element[head->y][head->x];
node->g=node->parent->g+1;
node->h=abs(node->x - targetX) + abs(node->y - targetY);
node->f=node->g + node->h;
tempHead=insertNode(tempHead,node);
}
//最后記住把head放進close表
}
if(map[head->y-1][head->x]!=-1)//如果臨近的方格不是墻壁
{
if(m_element[head->y-1][head->x]->close)
{}
else if(m_element[head->y-1][head->x]->open)
{
int temp = m_element[head->y][head->x]->g+1+m_element[head->y-1][head->x]->h;
if(m_element[head->y-1][head->x]->f > temp)
{
m_element[head->y-1][head->x]->g = m_element[head->y][head->x]->g+1;
m_element[head->y-1][head->x]->f = temp;
m_element[head->y-1][head->x]->parent=m_element[head->y-1][head->x];
tempHead=adjustNode(tempHead,m_element[head->y-1][head->x]);
}
}
else
{
if(head->x==targetX && head->y-1==targetY){return 1;}//找到終點！//修改這里
//as_node *node=new as_node;
as_node *node=m_element[head->y-1][head->x];
node->x=head->x;//修改這里
node->y=head->y-1;//修改這里
node->open=1;
node->close=0;
node->parent=m_element[head->y][head->x];
node->g=node->parent->g+1;
node->h=abs(node->x - targetX) + abs(node->y - targetY);
node->f=node->g + node->h;
tempHead=insertNode(tempHead,node);
}
//最后記住把head放進close表
}
head=tempHead;
}
return 0;//如果head是NULL表示open表已為空，所以找不到路徑
}
as_node *CAStar::adjustNode(as_node *head,as_node *node)
{
if(node->next != NULL && node->fore != NULL)//如果node存在與open鏈表中，而且在中間
{
if(node->f >= node->fore->f && node->f <= node->next->f)
{
return head;
}
else
{
//把node取出鏈表
node->fore->next = node->next;
node->next->fore = node->fore;
return insertNode(head,node);
}
}
else if(node->next!=NULL)//如果node存在于open鏈表中，而且處于頭部
{
if(node->f <= node->next->f)
{
return head;
}
else
{
//把node取出鏈表
node->next->fore=NULL;
return insertNode(head,node);
}
}
else if(node->fore!=NULL)//如果node存在于open鏈表中，而且處于尾部
{
if(node->f >= node->fore->f)
{
return head;
}
else
{
//把node取出鏈表
node->fore->next=NULL;
return insertNode(head,node);
}
}
//前面如果沒有返回值就代表node不適合原來鏈表中的位置
return insertNode(head,node);
}
//向open鏈表插入一個新的節點包括排序工作，但是不負責把原來的節點從open表中取出
as_node *CAStar::insertNode(as_node *head,as_node *node)
{
as_node *realHead=head;
if(head==NULL)//如果open表已經為空
{
node->fore=NULL;
node->next=NULL;
return node;
}
if(node->f <= head->f)//把node插入open表的頭部
{
node->fore=NULL;
node->next=head;
head->fore=node;
return node;
}
while(head->next != NULL)
{
if(node->f >= head->f && node->f <= head->next->f)
{
//把node接入鏈表的中間
head->next->fore=node;
node->next=head->next;
head->next=node;
node->fore=head;
return realHead;
}
head=head->next;
}
//while結構后head不再是原來的頭指針了
//如果經過以上的操作還沒返回，則表示node應該至于open表的末尾
head->next=node;
node->fore=head;
node->next=NULL;
return realHead;
}
int CAStar::searchThePath()
{
for(int i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
{
if(map[i][j]==0)
{
head = m_element[i][j];
head->x=j;
head->y=i;
head->fore=NULL;
head->next=NULL;
head->g=0;
//head->h=
head->close=0;
head->open=1;
//head->f=
head->parent=NULL;
}
else if(map[i][j]==-3)
{
targetX=j;
targetY=i;
}
}
}
return A();
}
void CAStar::showThePath(CDC *pDC , int showMode)
{
as_node *tempHead=head;
CBitmap bm1,bm2,bm3,bm4,bm5,bm6, *pbm;
BITMAP bmMetric1,bmMetric2;
bm1.LoadBitmap(IDB_BITMAP7);
bm2.LoadBitmap(IDB_BITMAP8);
bm3.LoadBitmap(IDB_BITMAP9);
bm4.LoadBitmap(IDB_BITMAP11);
bm5.LoadBitmap(IDB_BITMAP12);//起點
bm6.LoadBitmap(IDB_BITMAP13);//終點
bm1.GetBitmap(&bmMetric1);
bm2.GetBitmap(&bmMetric2);
CDC memDC;
memDC.CreateCompatibleDC(pDC);
pbm = memDC.SelectObject(&bm1);
memDC.SelectObject(&bm2);
//顯示地圖
for(int i = 0; i < Height; i ++)
{
for(int j = 0; j < Width; j ++)
{
if(map[i][j]==-1)
{
memDC.SelectObject(&bm1);
pDC->BitBlt(j*bmMetric2.bmWidth, i*bmMetric2.bmHeight,bmMetric1.bmWidth,bmMetric1.bmHeight,&memDC,0,0,SRCCOPY);
}
else if(map[i][j]==0)
{
memDC.SelectObject(&bm5);
pDC->BitBlt(j*bmMetric2.bmWidth, i*bmMetric2.bmHeight,bmMetric2.bmWidth,bmMetric2.bmHeight,&memDC,0,0,SRCCOPY);
}
else if(map[i][j]==-3)
{
memDC.SelectObject(&bm6);
pDC->BitBlt(j*bmMetric2.bmWidth, i*bmMetric2.bmHeight,bmMetric2.bmWidth,bmMetric2.bmHeight,&memDC,0,0,SRCCOPY);
}
}
}
/*
//顯示搜索過的點的f值
CFont *poldfont,*newfont=new CFont;
TEXTMETRIC tm;
newfont->CreateFont(3,0,0,0,FW_NORMAL,0,0,0,GB2312_CHARSET,OUT_DEFAULT_PRECIS,CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH,"宋體");
poldfont=pDC->SelectObject(newfont);
pDC->GetTextMetrics(&tm);
for(i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
{
if(m_element[i][j]->f!=-1)
{
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -