不理想就继续写、伸手没啥意思。
曾经室友花了一个通宵看算法并搞定了。

#ifndef _A_ASTERISK_H_
#define _A_ASTERISK_H_

#include <list>

using namespace std;

typedef pair<int, int> POS;
typedef list<POS> LIST_POS;

#define MAX_X 20
#define MAX_Y 20

enum PointType
{
        PointType_Normal,
        PointType_Block,
        PointType_Start,
        PointType_End,
        PointType_Other
};

struct Point
{
        POS pos;
        POS parentPos;
        // F = G + H
        int F;
        int G;
        int H;
        PointType pointType;
};

class A_asterisk
{
public:
        void Init(POS, POS, POS *, int);
        void Calc();
        void Show();
        LIST_POS GetCheckList(POS);
        bool IsAccess(POS, POS);
        void SetG(POS referPos, LIST_POS list);
        void GetAllH();
        POS GetMinPOSByF();
        void SetFinalList();
private:
        Point m_pointMatrix[MAX_Y][MAX_X];
        LIST_POS m_openList;
        LIST_POS m_closedList;
        POS m_startPos;
        POS m_endPos;
};

#endif

#include <iostream>
#include "A_asterisk.h"
#include "Utils.h"

using namespace std;

void A_asterisk::Init(POS startPos, POS endPos, POS *pBlockPoses, int blockLength)
{
        for (int i = 0; i < MAX_X; i++)
        {
                for (int j = 0; j < MAX_Y; j++)
                {
                        m_pointMatrix[i][j].pos.first = i;
                        m_pointMatrix[i][j].pos.second = j;
                        m_pointMatrix[i][j].parentPos.first = -1;
                        m_pointMatrix[i][j].parentPos.second = -1;
                        m_pointMatrix[i][j].F = -1;
                        m_pointMatrix[i][j].G = -1;
                        m_pointMatrix[i][j].H = 10 * (
                                abs(endPos.first - m_pointMatrix[i][j].pos.first) +
                                abs(endPos.second - m_pointMatrix[i][j].pos.second));
                        m_pointMatrix[i][j].pointType = PointType_Normal;
                }
        }
        m_pointMatrix[startPos.first][startPos.second].pointType = PointType_Start;
        m_pointMatrix[endPos.first][endPos.second].pointType = PointType_End;
        for (int k = 0; k < blockLength; k++)
        {
                m_pointMatrix[pBlockPoses[k].first][pBlockPoses[k].second].pointType = PointType_Block;
        }
        m_startPos = startPos;
        m_pointMatrix[startPos.first][startPos.second].G = 0;
        m_endPos = endPos;
}

void A_asterisk::Show()
{
        for (int i = 0; i < MAX_Y; i++)
        {
                for (int j = 0; j < MAX_X; j++)
                {
                        if (m_pointMatrix[j][i].pointType == PointType_Block)
                                cout<<'#'<<' ';
                        else if (m_pointMatrix[j][i].pointType == PointType_Start)
                                cout<<'s'<<' ';
                        else if (m_pointMatrix[j][i].pointType == PointType_End)
                                cout<<'e'<<' ';
                        else if (m_pointMatrix[j][i].pointType == PointType_Normal)
                                cout<<'-'<<' ';
                        else if (m_pointMatrix[j][i].pointType == PointType_Other)
                                cout<<'x'<<' ';
                }
                cout<<endl;
        }
        cout<<endl;
}

LIST_POS A_asterisk::GetCheckList(POS referPos)
{
        LIST_POS checkList;
        for (int i = -1; i <= 1; i++)
        {
                for (int j = -1; j <= 1; j++)
                {
                        POS pos;
                        pos.first = referPos.first + i;
                        pos.second = referPos.second + j;

                        // get check list
                        // 1 -> except referPos
                        if (pos == referPos)
                                continue;
                        // 2 -> not in closed list
                        if (Utils::Contains(m_closedList, pos))
                                continue;
                        // 3 -> not a block point
                        if (m_pointMatrix[pos.first][pos.second].pointType == PointType_Block)
                                continue;
                        // 4 -> not a unaccessible path
                        if (!IsAccess(referPos, pos))
                                continue;
                        // 5 -> not a negative pos
                        if (pos.first < 0 || pos.second < 0)
                                continue;
                        checkList.push_back(pos);

                        // add to open list
                        if (!Utils::Contains(m_openList, pos))
                                m_openList.push_back(pos);
                }
        }
        return checkList;
}

bool A_asterisk::IsAccess(POS referPos, POS pos)
{
        if (pos.first == referPos.first - 1 && pos.second == referPos.second - 1)
        {
                if (m_pointMatrix[pos.first + 1][pos.second].pointType == PointType_Block ||
                        m_pointMatrix[pos.first][pos.second + 1].pointType == PointType_Block)
                        return false;
                else
                        return true;
        }
        else if (pos.first == referPos.first - 1 && pos.second == referPos.second + 1)
        {
                if (m_pointMatrix[pos.first + 1][pos.second].pointType == PointType_Block ||
                        m_pointMatrix[pos.first][pos.second - 1].pointType == PointType_Block)
                        return false;
                else
                        return true;
        }
        else if (pos.first == referPos.first + 1 && pos.second == referPos.second - 1)
        {
                if (m_pointMatrix[pos.first - 1][pos.second].pointType == PointType_Block ||
                        m_pointMatrix[pos.first][pos.second + 1].pointType == PointType_Block)
                        return false;
                else
                        return true;
        }
        else if (pos.first == referPos.first + 1 && pos.second == referPos.second + 1)
        {
                if (m_pointMatrix[pos.first - 1][pos.second].pointType == PointType_Block ||
                        m_pointMatrix[pos.first][pos.second - 1].pointType == PointType_Block)
                        return false;
                else
                        return true;
        }
        else
        {
                // beeline
                return true;
        }
}

void A_asterisk::SetG(POS referPos, LIST_POS list)
{
        for (LIST_POS::iterator it = list.begin(); it != list.end(); it++)
        {
                POS pos = *it;
                if (pos.first != referPos.first &&
                        pos.second != referPos.second)
                {
                        // diagonal
                        int l = m_pointMatrix[referPos.first][referPos.second].G + 14;
                        if (l < m_pointMatrix[pos.first][pos.second].G ||
                                m_pointMatrix[pos.first][pos.second].G == -1)
                        {
                                m_pointMatrix[pos.first][pos.second].G = l;
                                m_pointMatrix[pos.first][pos.second].F = m_pointMatrix[pos.first][pos.second].H + l;
                                m_pointMatrix[pos.first][pos.second].parentPos = referPos;
                        }
                }
                else
                {
                        // beeline
                        int l = m_pointMatrix[referPos.first][referPos.second].G + 10;
                        if (l < m_pointMatrix[pos.first][pos.second].G ||
                                m_pointMatrix[pos.first][pos.second].G == -1)
                        {
                                m_pointMatrix[pos.first][pos.second].G = l;
                                m_pointMatrix[pos.first][pos.second].F = m_pointMatrix[pos.first][pos.second].H + l;
                                m_pointMatrix[pos.first][pos.second].parentPos = referPos;
                        }
                }
        }
        // add to closed list
        // remove from open list
        m_closedList.push_back(referPos);
        m_openList.remove(referPos);
}

POS A_asterisk::GetMinPOSByF()
{
        POS minPos;
        for (LIST_POS::iterator it = m_openList.begin(); it != m_openList.end(); it++)
        {
                POS pos = *it;
                if (it == m_openList.begin())
                        minPos = pos;
                else if (m_pointMatrix[minPos.first][minPos.second].F >= m_pointMatrix[pos.first][pos.second].F)
                        minPos = pos;
        }
        return minPos;
}

void A_asterisk::SetFinalList()
{
        LIST_POS list;
        for (POS pos = m_pointMatrix[m_endPos.first][m_endPos.second].parentPos;
                pos != m_pointMatrix[m_startPos.first][m_startPos.second].pos;
                pos = m_pointMatrix[pos.first][pos.second].parentPos)
        {
                m_pointMatrix[pos.first][pos.second].pointType = PointType_Other;
                list.push_back(pos);
        }
}

void A_asterisk::Calc()
{
        while (true)
        {
                if (Utils::Contains(m_closedList, m_endPos))
                {
                        // get final path
                        SetFinalList();
                        break;
                }

                if (!Utils::Contains(m_closedList, m_startPos))
                {
                        // first calc
                        LIST_POS list = GetCheckList(m_startPos);
                        SetG(m_startPos, list);
                }
                else
                {
                        POS referPos = GetMinPOSByF();
                        LIST_POS list = GetCheckList(referPos);
                        SetG(referPos, list);
                }
        }
}

void Test_A_asterisk()
{
        POS blockPoses[] = {
                POS(3, 0), POS(3, 1), POS(3, 2), POS(3, 3),  POS(3, 4), POS(3, 5), POS(6, 3), POS(6, 4), POS(6, 5),
                POS(7, 5), POS(8, 5)
        };
        POS startPos(1, 3);
        POS endPos(7, 4);
        A_asterisk foo;
        foo.Init(startPos, endPos, blockPoses, sizeof(blockPoses) / sizeof(blockPoses[0]));
        foo.Calc();
        foo.Show();
}

多年前写的。。哎我的青春啊。。

上传的附件：

• 无标题.png （9.57kb，1次下载）

你看下吧 我觉得挺好的

主要先看下pdf理解它的逻辑

希望能帮助到你

上传的附件：

• A星算法自寻路.zip （305.68kb，68次下载）
• A星算法.pdf （428.82kb，89次下载）

谢谢各位