//总结：
//本方法只适合于开放的路径，即：不能存在死胡同
//比如上面列出来的，因为算法的原因，它必须选取一个路径行走，当选择的这个路径是死胡同的话
//A就会失败
网上搜到的是：需要改变搜索算法，但是即使改变搜索算法，还是只取一条路径，怎么能保证选取的一定是正确的呢？
我的想法是，对有两个或多个路径点可选时，分别对其使用A算法求出完整的路径，如果可以达到的话，让其返回1，否则返回0，作为进行多路径选择的一个依据
#include “stdafx.h”
#include
#include
#include <math.h>
using namespace std;
int Map =
{
{0,1,1,1,1,1},
{0,0,0,0,0,0},
{1,1,0,1,1,0},
{1,1,0,1,0,0},
{1,0,1,1,1,0},
{1,0,1,0,0,0} //（0，0）为起点 (3,5)为终点
};
typedef struct Point
{
int x;
int y;
int wight;
Point(int a, int b, int c=10){ x = a, y = b; wight = c; }
int getH(struct Point &other)
{
int H = abs(other.x - x) + abs(other.y - y);
return H*10;
}
bool operator==(struct Point& p)
{
if (x == p.x && y == p.y)
return true;
else
return false;
}
}M_Point;
typedef struct Node
{
Node(struct Node _parent, Point&_currentPoint, int Weight = 10, Point&_endPoint = Point(3, 5)) :currentPoint(_currentPoint), pairent(_parent)
{
if (_parent != NULL)
G = _parent->G + Weight;//每行动一格，权值为10
else
G = 0;
H = _currentPoint.getH(_endPoint);
F = G + H;
}
int G;
int H;
int F;
Point currentPoint;
struct Node * pairent;
}M_Node;
list<M_Node> openList;
list<M_Node*> closeList;
void BeginStart(M_Node&begin);
int searchIsThrough(Point& point);
int _tmain(int argc, _TCHAR* argv])
{
M_Node* Begin = new M_Node(NULL,Point(0,0));
openList.push_back(Begin); //将开始节点添加进open列表中
BeginStart(Begin);
return 0;
}
void BeginStart(M_Node&begin)
{
//----------------------获取其周围可以通行的路径添加到openList列表中----------------------
Point top(begin.currentPoint.x - 1, begin.currentPoint.y);//向上
Point bottom(begin.currentPoint.x + 1, begin.currentPoint.y);//向下
Point right(begin.currentPoint.x , begin.currentPoint.y +1);//向右
Point left(begin.currentPoint.x , begin.currentPoint.y-1);//向左
Point left_top(begin.currentPoint.x - 1, begin.currentPoint.y-1,14);//左上
Point left_bottm(begin.currentPoint.x + 1, begin.currentPoint.y - 1, 14);//左下
Point right_top(begin.currentPoint.x - 1, begin.currentPoint.y + 1, 14);//右上
Point right_bottm(begin.currentPoint.x + 1, begin.currentPoint.y + 1, 14);//右下
Point p = {top,bottom,right,left,left_top,left_bottm,right_top,right_bottm};
for (int i = 0; i < 8; i++)
{
if (searchIsThrough(p) == 0&&p*.x>=0&&p*.x<6&&p*.y>=0&&p*.y<6)
{
bool isInClose = false;
//遍历close列表
for (auto tmp : closeList)
{
if (p* == tmp->currentPoint)
isInClose = true;
}
if (!isInClose)
{
M_Node * newNode = new M_Node(&begin, p*);
openList.push_back(newNode);
}
}
}
//------------------------------添加完毕----------------------------------------
//------人物行走之前，先将当前的路径点从openList中除去，同时将其添加到closeList中----
openList.remove(&begin);
closeList.push_back(&begin);
//--------------判断除去之后，openList是否为空，如果为空，说明无路可走了,那么直接return----
if (openList.empty())
{
cout << “openList is empty” << endl;
return;
}
auto iter = openList.begin();
M_Node * Next = *iter;
for (auto tmp : openList) //如果只有一个路径，那么就走这个了
{
if (tmp->F < Next->F) //比较F值，F值小的话就选这个路径
Next = tmp;
}
if (Next->H != 0)
{
cout << "( " << begin.currentPoint.x << "," << begin.currentPoint.y << " )" << endl;
openList.clear();//每次重新行走都需要将openList进行清空
BeginStart(*Next);//递归，开始第二次行走
}
else
{
cout << "( " << begin.currentPoint.x << "," << begin.currentPoint.y << " )" << endl;
return; //递归结束条件
}
}
int searchIsThrough(Point& point) //判断该点是否可以通行
{
return Map;
}*******
