|
|
前年开发一个RPG的游戏的时候，我放弃了A Star的算法，本来写好了，后来没有用到，对于3D游戏发现有点画蛇添足的味道（寻路是2D的），今年项目中有一个四国，工兵寻路觉得有点意思，但代码不好意思放上来，现在有个连连看的东西，跟上面的几种有区别但也有点相似。跟大家探讨。
常见的路径搜索算法，其实是一种穷举法，我们通常用的地图是连续存储的，比如用一个2维的数组来表示。
{ 1， 1， 1， 1，
1， 1， 0， 1，
1， 1， 1， 1，
1， 0， 1， 1 }
但也有非单一数组表示的，比如像四国军旗，每一个节点的下一步走法都不尽相同，有的可以8个方向走，有的只能2个方向，有的可以4个方向走，有的可以5个方向走。这个都没关系，只要把下一步能走的节点都存储起来即可。
struct NodeDir
{
int NextPos[MAX_DIR];
}
通常我们会有一个数组来存放每个节点的权重，初始化时将能走动的节点权重设置为一个大数，而将不能走动的节点设置为0。
同时我们定义一个双向链表树来存储已经走过路径
typedef struct tagCheckNode
{
int pos;
tagCheckNode * child[4];
tagCheckNode * father;
tagCheckNode( tagCheckNode * _father, int _pos );
~tagCheckNode( );
tagCheckNode * add_child( int _pos );
void del_child( tagCheckNode * _child );
}
CHK_NODE, *LP_CHK_NODE;
有了节点方向，权重数组，和路径树就可以开始了，常见的2D Tile地图不需要这个，默认就是4向或者8向。
所谓穷举法就是一个节点（格子）一个节点的试，找到一条适合我们需要的路径，那么连连看的连线路径比较特殊，最多只能拐2个弯，这是一个绝对Judge，当然我们常见的绝对Judge还有曼哈顿距离等等，当然我们会有其他的Judge，最常见的就是每次走过的路径不能比上一次的长，这就是权重的意义，由于初始化的时候，能走的地方权重都是大数，所以都可以走，不能走的地方都是0，那么都不能走，没有什么路径比0长。
现在开始从起点开始走（以四向连连看为例）
有4个方向（但不包括上次来的节点），如果在地图边上就只有3个方向走，地图角上是2个方向，每走一步把走过的节点存放到双向链表树中，同时该步路经的权重+1，并修改走过的节点的权重。
如果发现下面情况，则从双向链表树中删除当前节点，并退回到上一步
1、当前节点的权重比当前小，证明有一条更好的路已经来过了
2、当前节点不是目标点并四个方向都是死路
3、当前节点的路径比已经走过的一条正确的路径的长
4、当前节点拐了3个弯
5、其他觉得是死路的理由
如果当前节点是目标点，则 [ 不 ] 从双向链表树中删除当前节点，并退回到上一步
直到退回到双向链表树根节点，证明所有的节点都已经试过了，这时候我们可以认为最后一条路径就是最适合我们的路径，其实有可能最后2条，3条都符合，但我们只需取最后一条就OK了。
class GGamePath
{
private:
int * m_PathWeight; // 权重
int m_nCountX;
int m_nCountY;
int m_nCount;
CHK_NODE * m_pHeadPath;
CHK_NODE * m_pTailPath;
private:
// nFatherDir 上一次方向, 1右, 2左, 3上, 4下
// nChangeCount 拐弯次数
bool FindPath( CHK_NODE * pFarherNode, int nCheckPos, int nObjPos, int nFatherWeight, int nFatherDir, int nChangeCount )
{
char sDInfo[DEBUG_LEN];
if ( nFatherWeight != 0 )
{
if ( pFarherNode == null )
{
return false; // 错误
}
if ( nFatherWeight + 1 > m_PathWeight[nCheckPos] )
{
return false; // 不是最佳路径
}
if ( nCheckPos == nObjPos )
{
m_PathWeight[nCheckPos] = nFatherWeight + 1; // 标记路径权重
m_pTailPath = pFarherNode->add_child( nCheckPos );
return true; // 到达目标
}
if ( m_PathWeight[nCheckPos] == 0 )
{
return false; // 不通
}
}
m_PathWeight[nCheckPos] = nFatherWeight + 1; // 标记路径权重
bool bRet = CheckNextPath( pFarherNode, nCheckPos, nObjPos, nFatherWeight, nFatherDir, nChangeCount );
// bRet == false 死路
return bRet;
}
// 检查下一个方向
inline bool CheckNextPath( CHK_NODE * pFarherNode, int nCheckPos, int nObjPos, int nFatherWeight, int nFatherDir, int nChangeCount )
{
bool bRet = false;
int nNewPos;
int nNewChangeCount;
int x = nCheckPos % m_nCountX;
int y = nCheckPos / m_nCountX;
CHK_NODE * pNewNode = pFarherNode->add_child( nCheckPos );
nNewChangeCount = nChangeCount;
if ( x > 0 && nFatherDir != 1 )
{
if ( nFatherDir != 2 && nFatherDir != 0 ) nNewChangeCount = nChangeCount + 1;
if ( nNewChangeCount < 3 )
{
nNewPos = x - 1 + y * m_nCountX;
bRet |= FindPath( pNewNode, nNewPos, nObjPos, m_PathWeight[nCheckPos], 2, nNewChangeCount ); // 左
}
}
nNewChangeCount = nChangeCount;
if ( x < m_nCountX-1 && nFatherDir != 2 )
{
if ( nFatherDir != 1 && nFatherDir != 0 ) nNewChangeCount = nChangeCount + 1;
if ( nNewChangeCount < 3 )
{
nNewPos = x + 1 + y * m_nCountX;
bRet |= FindPath( pNewNode, nNewPos, nObjPos, m_PathWeight[nCheckPos], 1, nNewChangeCount ); // 右
}
}
nNewChangeCount = nChangeCount;
if ( y > 0 && nFatherDir != 4 )
{
if ( nFatherDir != 3 && nFatherDir != 0 ) nNewChangeCount = nChangeCount + 1;
if ( nNewChangeCount < 3 )
{
nNewPos = x + (y-1) * m_nCountX;
bRet |= FindPath( pNewNode, nNewPos, nObjPos, m_PathWeight[nCheckPos], 3, nNewChangeCount ); // 上
}
}
nNewChangeCount = nChangeCount;
if ( y < m_nCountY-1 && nFatherDir != 3 )
{
if ( nFatherDir != 4 && nFatherDir != 0 ) nNewChangeCount = nChangeCount + 1;
if ( nNewChangeCount < 3 )
{
nNewPos = x + (y+1) * m_nCountX;
bRet |= FindPath( pNewNode, nNewPos, nObjPos, m_PathWeight[nCheckPos], 4, nNewChangeCount ); // 下
}
}
if ( bRet == false ) // 死路
{
//m_PathWeight[nCheckPos] = 0;
if ( pNewNode )
{
delete pNewNode;
pNewNode = null;
}
}
return bRet;
}
void Destory( )
{
if ( m_PathWeight )
{
delete m_PathWeight;
m_PathWeight = null;
}
if ( m_pHeadPath )
{
delete m_pHeadPath;
m_pHeadPath = null;
m_pTailPath = null;
}
}
public:
GGamePath( )
{
m_PathWeight = null;
m_pHeadPath = null;
m_pTailPath = null;
}
~GGamePath( )
{
Destory( );
}
// nCountX和nCountY包括最外一层没有棋子的区域
bool SetCheckPath( int pArryPath[], int nCountX, int nCountY, int nStartPos, int nObjPos )
{
int i;
m_nCountX = nCountX;
m_nCountY = nCountY;
m_nCount = m_nCountX * m_nCountY;
m_PathWeight = new int[m_nCount];
m_pHeadPath = new CHK_NODE( null, nStartPos );
m_pTailPath = null;
for ( i=0; i {
if ( pArryPath > 0 )
m_PathWeight = 0;
else
m_PathWeight = m_nCount + 1;
}
m_PathWeight[nStartPos] = 0;
m_PathWeight[nObjPos] = m_nCount + 1;
return FindPath( m_pHeadPath, nStartPos, nObjPos, 0, 0, 0 );
}
CHK_NODE * GetPath( ) { return m_pTailPath; }
};
|
|
发表于 2005-12-19 13:26:00
楼主
