首页
社区
课程
招聘
[求助]求大神给a星寻路的代码,我自己写的总是不理想
发表于: 2016-3-7 04:05 4112

[求助]求大神给a星寻路的代码,我自己写的总是不理想

2016-3-7 04:05
4112
我自己写的寻路常常在某个点就卡死在那了
求大神给个能用的代码..............
感激不尽

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (7)
雪    币: 393
活跃值: (224)
能力值: ( LV8,RANK:140 )
在线值:
发帖
回帖
粉丝
2
不理想就继续写、伸手没啥意思。
曾经室友花了一个通宵看算法并搞定了。
2016-3-7 11:05
0
雪    币: 257
活跃值: (44)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
3
#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
2016-3-7 11:57
0
雪    币: 257
活跃值: (44)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
4
#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);
                }
        }
}
2016-3-7 11:58
0
雪    币: 257
活跃值: (44)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
5
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();
}
2016-3-7 12:01
0
雪    币: 257
活跃值: (44)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
6
多年前写的。。哎我的青春啊。。
上传的附件:
2016-3-7 12:03
0
雪    币: 105
活跃值: (549)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
你看下吧 我觉得挺好的

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

希望能帮助到你
上传的附件:
2016-3-7 12:22
0
雪    币: 35
活跃值: (25)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
谢谢各位
2016-3-7 13:13
0
游客
登录 | 注册 方可回帖
返回
//