www.pudn.com > GameEngine_src.rar > CPathSeeker.cpp

// CPathSeeker.cpp: implementation of the CPathSeeker class. 
// 
////////////////////////////////////////////////////////////////////// 
 
#include "CPathSeeker.h" 
#include "normal.h" 
#include "CMap.h" 
#include "BaseUtil.h" 
#include  
 
 
const BYTE SEEK_MASK = 0x80;			//已经检测过的标记 
const BYTE CLEAR_MASK= ~SEEK_MASK;		//清除OPEN,CLOSE 
const int MAX_NUM_SEEK = 8;				//在一次游戏循环中的最大寻路次数,不包括英雄 
 
extern CMap	theMap; 
 
const CELL ROUND_CELL[8] = { CELL(0,1), CELL(1,1), CELL(1,0), CELL(1,-1), CELL(0,-1), CELL(-1,-1), CELL(-1,0), CELL(-1,1) }; 
 
 
////////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////////// 
CPathSeeker::CPathSeeker() 
{ 
} 
 
CPathSeeker::~CPathSeeker() 
{ 
	Free(); 
} 
 
 
////////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////////// 
bool CPathSeeker::Init() 
{ 
	bool b = m_OpenList.Init( 128 ); 
	if ( !b ) return false; 
 
	b = m_PathNodePool.Init( 512 ); 
	if ( !b ) return false; 
	 
	m_NumSeekOfLoop = 0; 
	return m_CloseList.Init( 128 ); 
} 
 
 
////////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////////// 
void CPathSeeker::Free() 
{ 
	m_OpenList.Free(); 
	m_CloseList.Free(); 
	m_PathNodePool.Free(); 
} 
 
 
////////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////////// 
bool CPathSeeker::SeekPath( CStaticStack &path_array,  const CELL &from, const CELL &to, SPRITE_TYPE sprite_type ) 
{ 
	BYTE hold_mask = BUILDING_MASK;// | MONSTER_MASK; 
 
	if ( sprite_type == ST_MONSTER ) 
	{ 
		if ( m_NumSeekOfLoop >= MAX_NUM_SEEK ) 
			return false;							//如果一次循环中的寻路次数已经超过最大则不寻路 
		++m_NumSeekOfLoop; 
		hold_mask |= SAVE_MASK;						//安全地带怪物无法进入 
	} 
 
	BYTE *cell_array = theMap.GetCellArray(); 
	int width = theMap.GetCellPitch(); 
	int height= theMap.GetHeight() * 4; 
 
	//如果目的CELL走不通,就寻找目的CELL周围最近的可走的CELL 
	CELL dest = to; 
 
	if ( theMap.IsCellHold( dest.row, dest.col, hold_mask ) ) 
	{ 
		bool b = false; 
		int dir = CBaseSprite::CalcDirection( dest, from )-1; 
		for ( int i = 0; i < 8; ++i ) 
		{ 
			dest.row += ROUND_CELL[dir].row; 
			dest.col += ROUND_CELL[dir].col; 
 
			if ( theMap.IsCellHold( dest.row, dest.col, hold_mask ) == false ) 
			{ 
				b = true; 
				break; 
			} 
 
			++dir; 
			dir %= 8; 
		} 
 
		if ( !b ) return false;			//如果周围CELL无一可走	 
	} 
 
	if ( from.row == dest.row && from.col == dest.col ) 
		return false; 
	hold_mask |= MONSTER_MASK; 
	bool re = true; 
	PATH_NODE *src = m_PathNodePool.Alloc(); 
	src->cell = from; 
 
	//add src to open list 
	m_OpenList.Push( src );							 
 
	PATH_NODE *pnode; 
 
	while ( m_OpenList.Pop( pnode ) ) 
	{ 
		m_CloseList.Add( pnode ); 
 
		int row = pnode->cell.row; 
		int col = pnode->cell.col; 
 
		cell_array[row * width + col] |= SEEK_MASK;			//记上检测过的标记 
 
		int begin_row = ( row > 1 ? row - 1 : 0 ); 
		int end_row = ( row < height-1 ? row+1 : height-1 ); 
		int begin_col = ( col > 1 ? col-1 : 0 ); 
		int end_col = ( col < width-1 ? col+1 : width-1 ); 
 
		//遍历与pnode相连接的节点 
		for ( int i = begin_row; i <= end_row; ++i ) 
		{ 
			for ( int j = begin_col; j <= end_col; ++j ) 
			{ 
				BYTE data = cell_array[i * width + j]; 
 
				if ( dest.col == j && dest.row == i ) 
				{ 
					re = OnFinish( path_array, dest, pnode ); 
					goto _exit; 
				} 
				else if ( (data & SEEK_MASK) || (data & hold_mask) ) 
				{ 
					continue; 
				} 
				else 
				{ 
					PATH_NODE *new_node = m_PathNodePool.Alloc(); 
					if ( new_node == NULL ) 
					{ 
						re = false; 
						goto _exit; 
					} 
 
					new_node->cell.row = i; 
					new_node->cell.col = j; 
					new_node->known = pnode->known + 1; 
					new_node->estimate = Estimate( new_node->cell, to ); 
					new_node->total = new_node->known + new_node->estimate; 
					new_node->pFather = pnode; 
 
					if ( m_OpenList.Push( new_node ) == false ) 
					{ 
						re = OnFinish( path_array, CELL( row, col ), pnode ); 
						goto _exit; 
					} 
 
					cell_array[i * width + j] |= SEEK_MASK; 
				} 
			} 
		} 
	} 
 
	re = false;//OnFinish( path_array, CELL( row, col ), pnode ); 
 
_exit: 
	for ( m_PathNodePool.Begin(); m_PathNodePool.IsNotNull(); m_PathNodePool.MoveNext() ) 
	{ 
		int row = m_PathNodePool.GetCur()->cell.row; 
		int col = m_PathNodePool.GetCur()->cell.col; 
		cell_array[row * width + col] &= CLEAR_MASK; 
 
		m_PathNodePool.FreeCur(); 
	} 
 
	m_OpenList.Clear(); 
	m_CloseList.Clear(); 
 
	return re; 
} 
 
 
////////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////////// 
inline int CPathSeeker::Estimate( const CELL &from, const CELL &to ) 
{ 
	return abs( from.row - to.row ) + abs( from.col - to.col ); 
} 
 
////////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////////// 
bool CPathSeeker::OnFinish( CStaticStack &path_array, const CELL &dest, PATH_NODE *pnode ) 
{ 
	path_array.Clear(); 
	path_array.Push( dest ); 
	bool re; 
	while ( pnode->pFather != NULL ) 
	{ 
		re = path_array.Push( pnode->cell ); 
		pnode = pnode->pFather; 
	} 
 
	return re; 
}