A星算法(游戏寻路算法)的C++实现_mfc astar

作者：煮酒与君饮 | 2024-07-19 01:59:15

踩

mfc astar

A星算法的实现原理看这里：http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html

实现部分：

头文件：

[cpp] view plain copy

/*
A star 算法的基础处理
*/
#ifndef _A_STAR_BASE_H_
#define _A_STAR_BASE_H_
#include "windows.h"
typedef struct _APoint{
int x; // x 坐标
int y; // y 坐标
int type; // 类型
int f; // f = g + h
int g;
int h;
} APoint,*PAPoint;
enum APointType{
APT_UNKNOWN, // 未知状态
APT_OPENED, // 开放列表中
APT_CLOSED, // 关闭列表中
APT_STARTPOINT, // 起始点
APT_ENDPOINT // 结束点
};
class CAStarBase{
public:
CAStarBase();
~CAStarBase();
private:
PAPoint m_pAPointArr;
int m_nAPointArrWidth;
int m_nAPointArrHeight;
PAPoint m_pStartPoint,m_pEndPoint,m_pCurPoint;
char* m_pOldArr;
public:
BOOL Create(char* pDateArr,int nWidth,int nHeight);
void SetStartPoint(int x,int y);
void SetEndPoint(int x,int y);
void SetOpened(int x,int y);
void SetClosed(int x,int y);
void SetCurrent( int x,int y );
void PrintCharArr();
PAPoint CalcNextPoint(PAPoint ptCalc); // 应用迭代的办法进行查询
};
#endif

实现cpp文件：

[cpp] view plain copy

#include "stdafx.h"
#include "AStarBase.h"
CAStarBase::CAStarBase()
{
m_pAPointArr = NULL;
m_nAPointArrWidth = 0;
m_nAPointArrHeight = 0;
m_pStartPoint = NULL;
m_pEndPoint = NULL;
m_pCurPoint = NULL;
}
CAStarBase::~CAStarBase()
{
}
BOOL CAStarBase::Create( char* pDateArr,int nWidth,int nHeight )
{
if(!pDateArr) return FALSE;
if(nWidth<1 || nHeight<1) return FALSE;
m_pAPointArr = new APoint[nWidth*nHeight];
if(!m_pAPointArr) return FALSE;
m_pOldArr = pDateArr;
m_nAPointArrWidth = nWidth;
m_nAPointArrHeight = nHeight;
// 初始化数组内容
for ( int y = 0;y<m_nAPointArrHeight;y++)
{
for ( int x=0;x<m_nAPointArrWidth;x++)
{
m_pAPointArr[y*m_nAPointArrWidth+x].x = x;
m_pAPointArr[y*m_nAPointArrWidth+x].y = y;
m_pAPointArr[y*m_nAPointArrWidth+x].g = 0;
m_pAPointArr[y*m_nAPointArrWidth+x].f = 0;
m_pAPointArr[y*m_nAPointArrWidth+x].h = 0;
if ( pDateArr[y*m_nAPointArrWidth+x] == '0')
{
m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_OPENED;
}else if ( pDateArr[y*m_nAPointArrWidth+x] == '1')
{
m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_CLOSED;
}else if ( pDateArr[y*m_nAPointArrWidth+x] == 'S')
{
m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_STARTPOINT;
m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
m_pCurPoint = m_pStartPoint;
}else if ( pDateArr[y*m_nAPointArrWidth+x] == 'E')
{
m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_ENDPOINT;
m_pEndPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
}else{
m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_UNKNOWN;
}
}
}
return TRUE;
}
void CAStarBase::SetStartPoint( int x,int y )
{
if ( m_pStartPoint && m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_CLOSED )
{
m_pStartPoint->type = APT_OPENED;
// 设置新的值
m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
m_pStartPoint->type = APT_STARTPOINT;
m_pCurPoint = m_pStartPoint;
}
}
void CAStarBase::SetEndPoint( int x,int y )
{
if ( m_pStartPoint && m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_CLOSED )
{
m_pStartPoint->type = APT_OPENED;
// 设置新的值
m_pStartPoint = m_pAPointArr + y*m_nAPointArrWidth+x;
m_pStartPoint->type = APT_ENDPOINT;
}
}
void CAStarBase::SetCurrent( int x,int y )
{
// if ( m_pAPointArr[y*m_nAPointArrWidth+x].type==APT_OPENED )
{
m_pCurPoint = m_pAPointArr+y*m_nAPointArrWidth+x;
}
}
void CAStarBase::SetOpened( int x,int y )
{
if ( m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_OPENED )
{
m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_OPENED;
}
}
void CAStarBase::SetClosed( int x,int y )
{
if ( m_pAPointArr[y*m_nAPointArrWidth+x].type!=APT_CLOSED )
{
m_pAPointArr[y*m_nAPointArrWidth+x].type = APT_CLOSED;
}
}
void CAStarBase::PrintCharArr()
{
if ( m_pOldArr )
{
for ( int y=0; y<m_nAPointArrHeight;y++)
{
for ( int x=0;x<m_nAPointArrWidth;x++)
{
printf("%c ",m_pOldArr[x+m_nAPointArrWidth*y]);
}
printf("\r\n");
}
printf("\r\n");
}
}
PAPoint CAStarBase::CalcNextPoint( PAPoint ptCalc )
{
if ( ptCalc == NULL )
{
ptCalc = m_pStartPoint;
}
int x = ptCalc->x;
int y = ptCalc->y;
int dx = m_pEndPoint->x;
int dy = m_pEndPoint->y;
int xmin = x,ymin = y,vmin = 0; // 最优步骤的坐标和值
// 判断是否已经到了最终的位置
if ( (x==dx && abs(y-dy)==1) || (y==dy && abs(x-dx)==1) )
{
return m_pEndPoint;
}
// 上
if ( m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].type == APT_OPENED && y>0)
{
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].g = 10;
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].h =
10*(abs(x - dx) + abs(y-1 - dy));
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f =
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].g + m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].h;
if ( vmin==0 )
{
xmin = x;
ymin = y-1;
vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f;
}else{
if ( vmin > m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f )
{
xmin = x;
ymin = y-1;
vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y-1)].f;
}
}
}
// 下
if ( m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].type == APT_OPENED && y<m_nAPointArrHeight)
{
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].g = 10;
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].h =
10*(abs(x - dx) + abs(y+1 - dy));
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f =
m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].g + m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].h;
if ( vmin==0 )
{
xmin = x;
ymin = y+1;
vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f;
}else{
if ( vmin > m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f )
{
xmin = x;
ymin = y+1;
vmin = m_pAPointArr[(x+0)+m_nAPointArrWidth*(y+1)].f;
}
}
}
// 左
if ( m_pAPointArr[(x-1)+m_nAPointArrWidth*y].type == APT_OPENED && x>0)
{
m_pAPointArr[(x-1)+m_nAPointArrWidth*y].g = 10;
m_pAPointArr[(x-1)+m_nAPointArrWidth*y].h =
10*(abs(x-1 - dx) + abs(y - dy));
m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f =
m_pAPointArr[(x-1)+m_nAPointArrWidth*y].g + m_pAPointArr[(x-1)+m_nAPointArrWidth*y].h;
if ( vmin==0 )
{
xmin = x-1;
ymin = y;
vmin = m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f;
}else{
if ( vmin > m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f )
{
xmin = x-1;
ymin = y;
vmin = m_pAPointArr[(x-1)+m_nAPointArrWidth*y].f;
}
}
}
// 右
if ( m_pAPointArr[(x+1)+m_nAPointArrWidth*y].type == APT_OPENED && x<m_nAPointArrWidth)
{
m_pAPointArr[(x+1)+m_nAPointArrWidth*y].g = 10;
m_pAPointArr[(x+1)+m_nAPointArrWidth*y].h =
10*(abs(x+1 - dx) + abs(y - dy));
m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f =
m_pAPointArr[(x+1)+m_nAPointArrWidth*y].g + m_pAPointArr[(x+1)+m_nAPointArrWidth*y].h;
if ( vmin==0 )
{
xmin = x+1;
ymin = y;
vmin = m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f;
}else{
if ( vmin > m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f )
{
xmin = x+1;
ymin = y;
vmin = m_pAPointArr[(x+1)+m_nAPointArrWidth*y].f;
}
}
}
// 如果有最优点则迭代，则否就返回NULL
if ( vmin )
{
SetCurrent(xmin,ymin);
SetClosed(xmin,ymin);
*(m_pOldArr+xmin+m_nAPointArrWidth*ymin) = '-';
PrintCharArr();
PAPoint pApoint = CalcNextPoint(m_pCurPoint);
if ( pApoint == NULL )
{
SetCurrent(x,y);
SetClosed(xmin,ymin);
*(m_pOldArr+xmin+m_nAPointArrWidth*ymin) = '0';
return CalcNextPoint(m_pCurPoint);
}
return pApoint;
}else{
return NULL;
}
}

测试文件：

[cpp] view plain copy

// AStarMath.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "AStarBase.h"
CAStarBase Astarbase;
int _tmain(int argc, _TCHAR* argv[])
{
char pBuff[5][7] = {
'0','0','0','1','0','0','0',
'0','1','1','0','0','1','1',
'0','S','1','0','1','E','0',
'0','1','0','0','0','1','0',
'0','0','0','1','0','0','0'
};
Astarbase.Create(&pBuff[0][0],7,5);
Astarbase.PrintCharArr();
PAPoint pPoint = Astarbase.CalcNextPoint(NULL);
if ( pPoint == NULL )
{
printf("no path can arrive!\r\n");
}else{
printf("success arrived!\r\n");
}
getchar();
return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/848860