能力值:
( LV8,RANK:140 )
2 楼
不理想就继续写、伸手没啥意思。
曾经室友花了一个通宵看算法并搞定了。
能力值:
( 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
能力值:
( 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);
}
}
}
能力值:
( 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();
}
能力值:
( LV3,RANK:20 )
6 楼
能力值:
( LV2,RANK:10 )
7 楼
你看下吧 我觉得挺好的
主要先看下pdf理解它的逻辑
希望能帮助到你
上传的附件:
能力值:
( LV2,RANK:10 )
8 楼
谢谢各位