back.rar cwayai.cpp

www.pudn.com > back.rar > cwayai.cpp
#include  
#include  
 
#include "base.h" 
#include "xblock_table.h" 
#include "skill.h" 
 
#include "../CUserInfo/userinfo.h" 
#include "npc.h" 
#include "xblock.h" 
#include "MAP.H" 
 
#include "Clock.H" 
#include "party.h" 
//#include "skill.h" 
#include "trade.h" 
#include "buy.h" 
#include "sell.h" 
#include "guild.h" 
#include "PrivateShop.h"	//임창원 추가. 
 
#include "server.h" 
#include "Main.H" 
#include "CWayAi.h" 
 
/**************************************************************************/ 
/*                            STACK FUNCTIONS                             */ 
/**************************************************************************/ 
void CWayAi::Push(NODE *Node)	{					// ... 
    AI_STATIC *tmp; 
 
    tmp=( AI_STATIC *)calloc(1,sizeof(AI_STATIC)); 
    tmp->NodePtr=Node; 
    tmp->NextStackPtr=Stack->NextStackPtr; 
    Stack->NextStackPtr=tmp; 
} 
NODE* CWayAi::Pop()	{								// ... 
    NODE *tmp; 
    AI_STATIC *tmpSTK; 
 
    tmpSTK=Stack->NextStackPtr; 
    tmp=tmpSTK->NodePtr; 
 
    Stack->NextStackPtr=tmpSTK->NextStackPtr; 
    free(tmpSTK); 
    return (tmp); 
} 
 
/**************************************************************************/ 
/***************************** A* Algorithm *******************************/ 
/**************************************************************************/ 
void CWayAi::PropagateDown(NODE *Old)	{			// 가지의 전파... 
    int c,g; 
    NODE *Child, *Father; 
 
    g=Old->g;            // alias. 
    for(c=0;c<8;c++) { 
        if ((Child=Old->Child[c])==NULL)   // create alias for faster access. 
            break; 
        if (g+1 < Child->g) { 
            Child->g=g+1; 
            Child->f=Child->g+Child->h; 
            Child->Parent=Old;           // reset parent to new path. 
            Push(Child);                 // Now the Child's branch need to be 
        }     // checked out. Remember the new cost must be propagated down. 
    } 
    while (Stack->NextStackPtr != NULL) { 
        Father=Pop(); 
        for(c=0;c<8;c++) { 
            if ((Child=Father->Child[c])==NULL)       /* we may stop the propagation 2 ways: either */ 
                break; 
            if (Father->g+1 < Child->g) {       /* there are no children, or that the g value of */ 
                                    /* the child is equal or better than the cost we're propagating */ 
                Child->g=Father->g+1; 
                Child->f=Child->g+Child->h; 
                Child->Parent=Father; 
                Push(Child); 
            } 
        } 
    } 
} 
 
void CWayAi::Insert(NODE *Successor)	{					// ...??? 
    NODE *tmp1,*tmp2; 
    int f; 
 
    if (OPEN->NextNode == NULL) { 
        OPEN->NextNode=Successor; 
        return; 
    } 
 
    // insert into OPEN successor wrt f 
    f=Successor->f; 
    tmp1=OPEN; 
    tmp2=OPEN->NextNode; 
    while ((tmp2 != NULL) && (tmp2->f < f)) { // 값이 작은 것을 찾는다. 
        tmp1=tmp2;	// 다음 노드  
        tmp2=tmp2->NextNode; 
    } 
	Successor->NextNode=tmp2;  // 큰 값을 자기 뒤에 놓는다. 
	tmp1->NextNode=Successor;  // 자신은 사이에 들어간다. 
} 
 
 
// 각각의 노드에 대하여 열린 값이지 체크한다.??? 
NODE* CWayAi::CheckOPEN(int tilenum)	{ 
    NODE *tmp; 
    tmp=OPEN->NextNode; 
    while (tmp != NULL) { 
        if (tmp->NodeNum == tilenum) 
            return (tmp); 
        else 
            tmp=tmp->NextNode; 
    } 
    return (NULL); 
} 
// 각각의 노드에 대하여 닫힌 값인지 체크한다.??? 
NODE* CWayAi::CheckCLOSED(int tilenum)	{ 
    NODE *tmp; 
    tmp=CLOSED->NextNode; 
    while (tmp != NULL) { 
        if (tmp->NodeNum == tilenum) 
            return (tmp); 
        else 
            tmp=tmp->NextNode; 
    } 
    return (NULL); 
} 
 
// 각각 타일의 길찾기 test 성공... 
void CWayAi::GenerateSucc(NODE *BestNode, int x, int y, int dx, int dy)	{ 
    int g,TileNumS,c=0; 
    NODE *Old,*Successor; 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<" GenerateSucc 시작 \r\n"; 
#endif 
 
    g=BestNode->g+1;    // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor 
    TileNumS=y*COLS+x;	// identification purposes 
 
    if ((Old=CheckOPEN(TileNumS)) != NULL) { // if equal to NULL then not in OPEN list, else it returns the Node in Old 
        for(c=0;c<8;c++) 
            if(BestNode->Child[c] == NULL) // Add Old to the list of BestNode's Children (or Successors). 
                break; 
        BestNode->Child[c]=Old; 
        if (g < Old->g) {  // if our new g value is < Old's then reset Old's parent to point to BestNode 
            Old->Parent=BestNode; 
            Old->g=g; 
            Old->f=g+Old->h; 
        } 
    } else if ((Old=CheckCLOSED(TileNumS)) != NULL) { // if equal to NULL then not in OPEN list, else it returns the Node in Old 
        for(c=0;c<8;c++) 
            if (BestNode->Child[c] == NULL) // Add Old to the list of BestNode's Children (or Successors). 
                break; 
        BestNode->Child[c]=Old; 
        if (g < Old->g) { // if our new g value is < Old's then reset Old's parent to point to BestNode 
            Old->Parent=BestNode; 
            Old->g=g; 
            Old->f=g+Old->h; 
            PropagateDown(Old);       /* Since we changed the g value of Old, we need 
                                         to propagate this new value downwards, i.e. 
                                         do a Depth-First traversal of the tree! */ 
        } 
    } else { 
        Successor=(NODE *)calloc(1,sizeof( NODE )); 
        Successor->Parent=BestNode; 
        Successor->g=g; 
        Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);  // should do sqrt(), but since we don't really 
        Successor->f=g+Successor->h;     // care about the distance but just which branch looks 
        Successor->x=x;                  // better this should suffice. Anyayz it's faster. 
        Successor->y=y; 
        Successor->NodeNum=TileNumS; 
        Insert(Successor);     /* Insert Successor on OPEN list wrt f */ 
        for(c=0;c<8;c++) 
            if (BestNode->Child[c] == NULL) /* Add Old to the list of BestNode's Children (or Successors). */ 
                break; 
        BestNode->Child[c]=Successor; 
 
    } 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<" GenerateSucc 끝 \r\n"; 
#endif 
 
} 
 
 
bool CWayAi::isTile(int x, int y)  
{ 
	// 1 -> 오브젝트. 2 -> PC, 3 -> NPC 
	if( x < 0 || y < 0 ||  
		x >= Line[tmap->m_map_size] || y >= Line[tmap->m_map_size] ||  
//		tmap->m_use_path[ x ][ y ] == (char)OBJECT_TILE || tmap->m_use_path[ x ][ y ] == (char)PC_TILE || 
//		tmap->m_use_path[ x ][ y ] == (char)NPC_TILE ) 
		tmap->m_block_table[x][y].bBlocked || tmap->m_block_table[x][y].bNPC || tmap->m_block_table[x][y].bPC || // tmap->m_block_table[x][y].bITEM ||  
		tmap->m_block_table[x][y].bSNPC ) 
		return false; 
	return true; 
} 
 
// 방향 별로 길을 찾아본다... 
void CWayAi::GenerateSuccessors(NODE *BestNode,int dx,int dy)	 
{ 
	int tx,ty; 
 #if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<" GenerateSuccessors시작 \r\n"; 
#endif 
 
	// Upper-Left...(대각선 좌측으로 갈수 있다면...) 
	tx = BestNode->x-1; 
	ty = BestNode->y-1; 
	if( isTile( tx, ty ) )	 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
    
	// Upper... 
	tx=BestNode->x; 
	ty=BestNode->y-1; 
    if (isTile( tx, ty ) )		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
     
	// Upper-Right... 
	tx =BestNode->x+1; 
	ty = BestNode->y-1; 
	if( isTile( tx, ty ) ) 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
  
	// Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y; 
    if (isTile( tx, ty ))		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
   
	// Lower-Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y+1; 
	if( isTile( tx, ty ) )	 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
    
	// Lower... 
	tx=BestNode->x; 
	ty=BestNode->y+1; 
    if ( isTile( tx, ty ) )		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
  
	// Lower-Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y+1; 
	if( isTile( tx, ty ) ) 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
   
	// Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y; 
    if ( isTile( tx, ty ) )		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<" GenerateSuccessors끝 \r\n"; 
#endif 
 
} 
 
 
// 길찾기 중에서 막다를 길을 찾았다면, 이전 길을 선택한다... 
NODE* CWayAi::ReturnBestNode(void)	{ 
    NODE *tmp; 
////////////////////////////////////////////////////////////////////////////////////////////////////////// 
    if (OPEN->NextNode == NULL) {							// 길을 못찾을때... 
//	    printf("ERROR: no more nodes on OPEN\n"); 
//	    exit(0); 
		return NULL; 
	} 
 
/* Pick Node with lowest f, in this case it's the first node in list 
   because we sort the OPEN list wrt lowest f. Call it BESTNODE. */ 
    tmp=OPEN->NextNode;				 // point to first node on OPEN 
    OPEN->NextNode=tmp->NextNode;    // Make OPEN point to nextnode or NULL. 
 
/* Next take BESTNODE (or temp in this case) and put it on CLOSED */ 
    tmp->NextNode=CLOSED->NextNode; 
    CLOSED->NextNode=tmp; 
    return(tmp); 
} 
 
 
// 길찾기를 시작한다. 
NODE* CWayAi::FindPath(int sx,int sy,int dx,int dy, NPC_STATUS status )	{ 
    NODE *Node, *BestNode; 
    int TileNumDest; 
	int Depth=0; 
 
    TileNumDest=dy*COLS+dx; 
 
    OPEN=(NODE *)calloc(1,sizeof( NODE )); 
    CLOSED=(NODE *)calloc(1,sizeof( NODE )); 
 
    Node=(NODE *)calloc(1,sizeof( NODE )); 
    Node->g=0; 
    Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);  // should really use sqrt(). 
    Node->f=Node->g+Node->h; 
    Node->NodeNum=sy*COLS+sx; 
    Node->x=sx; 
    Node->y=sy; 
 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"길찾기 노드할당 끝, 루프 돌기 \r\n"; 
#endif 
    OPEN->NextNode=Node;						 /* make Open List point to first node */ 
    for (;;) { 
		BestNode=(NODE *)ReturnBestNode(); 
		// 내가 
		if( BestNode == NULL ) 
			return NULL; 
 
        if (BestNode->NodeNum == TileNumDest)    /* if we've found the end, break and finish */ 
            break; 
 
		else if( (abs( BestNode->x - dx ) <= 1 && abs( BestNode->y - dy ) <= 1) ) 
		{ 
//			if ( tmap->m_use_path[dx][dy] == (char)PC_TILE  
//				|| tmap->m_use_path[dx][dy] == (char)NPC_TILE  
//				|| tmap->m_use_path[dx][dy] == (char)OBJECT_TILE )	// 다음 위치에 먼가 있으면 못가 스톱 
			if( tmap->m_block_table[dx][dy].bBlocked || tmap->m_block_table[dx][dy].bNPC || tmap->m_block_table[dx][dy].bPC || tmap->m_block_table[dx][dy].bSNPC )//tmap->m_block_table[x][y].bITEM ||  
				break; 
//			else continue;		// 0->빈곳이면 한번 더 돌아서 끝까지 도착 
		} 
 
		else GenerateSuccessors(BestNode,dx,dy); 
		/// 깊이 한계를 둘때.....................................................................		 
		if( DEPTH<++Depth )	{ 
			bWayPossibled = false; 
			break; 
		} 
    } 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"루프 돌기 끝\r\n"; 
#endif 
 
    return (BestNode); 
} 
 
// 길찾기 구조체 설정... 
NODE* CWayAi::SearchWay( int x, int y, int dx, int dy, NPC_STATUS status )		{ 
	NODE *path; 
	bWayPossibled = true; 
	Stack=( AI_STATIC *)calloc(1,sizeof(AI_STATIC));  // setup the Stack. 
	path=FindPath(x,y,dx,dy, status ); 
	Exe = true; 
 
	if( bWayPossibled ) 
		return (path); 
	else  
	{ 
		path = NULL; 
		return (path); 
	} 
 
	return (path); 
 
} 
 
// 3-21 원거리공격 마법등 
DWORD	CWayAi::Return_Distance( int x, int y, int dx, int dy ) 
{ 
	bWayPossibled = true; 
	Stack=( AI_STATIC *)calloc(1,sizeof(AI_STATIC));  // setup the Stack. 
//	path=FindPath(dx,dy,x,y);	// 목표점, 시작점. 
	DWORD dist=FindPath_Distance(x,y,dx,dy); 
 
	return dist; 
} 
 
DWORD CWayAi::FindPath_Distance( int sx, int sy, int dx, int dy ) 
{ 
	int count=0; 
    NODE *Node, *BestNode; 
    int TileNumDest; 
	int Depth=0; 
 
    TileNumDest=dy*COLS+dx; 
 
    OPEN=(NODE *)calloc(1,sizeof( NODE )); 
    CLOSED=(NODE *)calloc(1,sizeof( NODE )); 
 
    Node=(NODE *)calloc(1,sizeof( NODE )); 
    Node->g=0; 
    Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);  // should really use sqrt(). 
    Node->f=Node->g+Node->h; 
    Node->NodeNum=sy*COLS+sx; 
    Node->x=sx; 
    Node->y=sy; 
 
    OPEN->NextNode=Node;						 /* make Open List point to first node */ 
    for (;;) { 
		BestNode=(NODE *)ReturnBestNode(); 
		// 내가 
		if( BestNode == NULL ) 
			return 0; 
 
        if (BestNode->NodeNum == TileNumDest)    /* if we've found the end, break and finish */ 
            break; 
 
//		else if( (abs( BestNode->x - dx ) <= 1 && abs( BestNode->y - dy ) <= 1) ) 
//		{ 
//			if ( tmap->m_use_path[dx][dy] == (char)OBJECT_TILE )	// object 
			if( tmap->m_block_table[dx][dy].bBlocked ) 
			{ 
				count = dx + dy*COLS; 
				break; 
			} 
//		} 
 
		else GenerateSuccMy(BestNode,dx,dy); 
		count++; 
 		/// 깊이 한계를 둘때.....................................................................		 
		if( DEPTH<++Depth )	{ 
			bWayPossibled = false; 
			break; 
		} 
   } 
    return count; 
 
} 
 
void CWayAi::GenerateSuccMy(NODE *BestNode,int dx,int dy) 
{ 
	int tx,ty; 
  
	// Upper-Left...(대각선 좌측으로 갈수 있다면...) 
	tx = BestNode->x-1; 
	ty = BestNode->y-1; 
	if( isTileMy( tx, ty ) )	 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
    
	// Upper... 
	tx=BestNode->x; 
	ty=BestNode->y-1; 
    if (isTileMy( tx, ty ) )		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
     
	// Upper-Right... 
	tx =BestNode->x+1; 
	ty = BestNode->y-1; 
	if( isTileMy( tx, ty ) ) 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
  
	// Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y; 
    if (isTileMy( tx, ty ))		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
   
	// Lower-Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y+1; 
	if( isTileMy( tx, ty ) )	 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
    
	// Lower... 
	tx=BestNode->x; 
	ty=BestNode->y+1; 
    if ( isTileMy( tx, ty ) )		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
  
	// Lower-Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y+1; 
	if( isTileMy( tx, ty ) ) 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
   
	// Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y; 
    if ( isTileMy( tx, ty ) )		 
		GenerateSucc(BestNode,tx,ty,dx,dy); 
 
} 
 
bool CWayAi::isTileMy( int x, int y ) 
{ 
	if( x < 0 || y < 0 ||  
		x >= Line[tmap->m_map_size] || y >= Line[tmap->m_map_size] ||  
//		tmap->m_use_path[ x ][ y ] == (char)OBJECT_TILE ) 
		tmap->m_block_table[x][y].bBlocked ) 
		return false; 
	return true; 
 
} 
 
/////////////////////////////////////////////////////////////////////////////////// 
 
 
 
 
 
// 길찾기 구조체를 지운다... 
void CWayAi::DeleteWay( void )	{ 
    NODE *path, *Node; 
 
    // Free Nodes up 
    Node=OPEN;//->NextNode;??? 
    while (Node != NULL) { 
		path=Node; 
        Node=Node->NextNode; 
		free(path); 
		path = NULL; 
    } 
    Node=CLOSED;//->NextNode;??? 
    while (Node != NULL) { 
		path=Node; 
        Node=Node->NextNode; 
		free(path); 
		path = NULL; 
    } 
/* 
	if( Stack != NULL ) 
	{ 
		free( Stack ); 
		Stack = NULL; 
	} 
*/ 
	free( Stack ); 
	Stack = NULL; 
	Exe = false; 
} 
 
// 길찾기 가능 지역인가 판정... 
bool CWayAi::CheckPossablePoint( int dx, int dy )	{ 
	// 갈수 없는 지역이면, 검색 취소... 
//	if( tmap->m_use_path[dx][dy*COLS] == (char)OBJECT_TILE )	return false;	 
	if( tmap->m_block_table[dx][dy].bBlocked ) return false; 
	return true; 
} 
 
// 큰몹 길찾기 
// 길찾기 구조체 설정... 
NODE* CWayAi::BigSearchWay( int x, int y, int dx, int dy, NPC_SIZE size, int nPos, bool bSummon ) 
{ 
	NODE *path; 
	bWayPossibled = true; 
	Stack=( AI_STATIC *)calloc(1,sizeof(AI_STATIC));  // setup the Stack. 
	path=BigFindPath(x,y,dx,dy, size, nPos, bSummon ); 
	Exe = true; 
 
	if( bWayPossibled ) 
		return (path); 
	else  
	{ 
		path = NULL; 
		return (path); 
	} 
 
	return (path); 
} 
 
NODE* CWayAi::BigFindPath( int sx, int sy, int dx, int dy, NPC_SIZE size, int nPos, bool bSummon ) 
{ 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"Bigfindpath 시작 \r\n"; 
#endif 
    NODE *Node, *BestNode; 
    int TileNumDest; 
	int Depth=0; 
 
    TileNumDest=dy*COLS+dx; 
 
    OPEN=(NODE *)calloc(1,sizeof( NODE )); 
	CLOSED=(NODE *)calloc(1,sizeof( NODE )); 
 
    Node=(NODE *)calloc(1,sizeof( NODE )); 
    Node->g=0; 
    Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);  // should really use sqrt(). 
    Node->f=Node->g+Node->h; 
    Node->NodeNum=sy*COLS+sx; 
    Node->x=sx; 
    Node->y=sy; 
 
    OPEN->NextNode=Node;						 /* make Open List point to first node */ 
    for (;;) { 
		BestNode=(NODE *)ReturnBestNode(); 
		if( BestNode == NULL ) 
			return NULL; 
 
        if (BestNode->NodeNum == TileNumDest)    /* if we've found the end, break and finish */ 
            break; 
 
//		else if( (abs( BestNode->x - dx ) <= 1 && abs( BestNode->y - dy ) <= 1) ) 
		else if( ((abs( BestNode->x - dx ) <= 1 && abs( BestNode->y - dy ) <= 1)) ||  
			((abs( BestNode->x - dx ) <= 1 && abs( BestNode->y - dy ) == 0)) ||  
			((abs( BestNode->x - dx ) == 0 && abs( BestNode->y - dy ) <= 1)) ) 
		{ 
//			if ( tmap->m_use_path[dx][dy] == (char)PC_TILE  
//				|| tmap->m_use_path[dx][dy] == (char)NPC_TILE 
//				|| tmap->m_use_path[dx][dy] == (char)OBJECT_TILE )	// 다음 위치에 먼가 있으면 못가 스톱 
			if( tmap->m_block_table[dx][dy].bBlocked || //tmap->m_block_table[dx][dy].bITEM || 
				tmap->m_block_table[dx][dy].bNPC || tmap->m_block_table[dx][dy].bPC || tmap->m_block_table[dx][dy].bSNPC ) 
				break; 
//			else continue;		// 0->빈곳이면 한번 더 돌아서 끝까지 도착 
		} 
		else BigGenerateSuccessors( BestNode, dx, dy, size, nPos, bSummon ); 
		/// 깊이 한계를 둘때.....................................................................		 
		if( DEPTH<++Depth )	{ 
			bWayPossibled = false; 
			break; 
		} 
    } 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"Bigfindpath end \r\n"; 
#endif 
 
    return (BestNode); 
} 
 
 
bool CWayAi::BigisTile(int x, int y, NPC_SIZE size, int nPos, bool bSummon )  
{ 
	if( x == Line[tmap->m_map_size]-1 || y == Line[tmap->m_map_size]-1 || 
		x == Line[tmap->m_map_size] || y == Line[tmap->m_map_size] || 
		x <= 0 || y <= 0  
		) 
		return false; 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"BigisTile start \r\n"; 
#endif 
	if( bSummon ) 
	{ 
		if( tmap->m_block_table[x][y].bBlocked == true ||  
//			tmap->m_block_table[x][y].bITEM == true || 
			tmap->m_block_table[x][y].bPC == true || 
			tmap->m_block_table[x][y].bNPC == true || 
			( tmap->m_block_table[x][y].bSNPC == true && tmap->m_block_table[x][y].nArrayNo != nPos && tmap->m_block_table[x][y].nArrayNo != -1 ) 
			) 
			return false; 
		if( tmap->m_block_table[x+1][y].bBlocked == true ||  
//			tmap->m_block_table[x+1][y].bITEM == true || 
			tmap->m_block_table[x+1][y].bPC == true || 
			tmap->m_block_table[x+1][y].bNPC == true || 
			( tmap->m_block_table[x+1][y].bSNPC == true && tmap->m_block_table[x+1][y].nArrayNo != nPos && tmap->m_block_table[x+1][y].nArrayNo != -1 ) 
			) 
			return false; 
		if( tmap->m_block_table[x][y+1].bBlocked == true ||  
//			tmap->m_block_table[x][y+1].bITEM == true || 
			tmap->m_block_table[x][y+1].bPC == true || 
			tmap->m_block_table[x][y+1].bNPC == true || 
			( tmap->m_block_table[x][y+1].bSNPC == true && tmap->m_block_table[x][y+1].nArrayNo != nPos && tmap->m_block_table[x][y+1].nArrayNo != -1 ) 
			) 
			return false; 
		if( tmap->m_block_table[x+1][y+1].bBlocked == true ||  
//			tmap->m_block_table[x+1][y+1].bITEM == true || 
			tmap->m_block_table[x+1][y+1].bPC == true || 
			tmap->m_block_table[x+1][y+1].bNPC == true || 
			( tmap->m_block_table[x+1][y+1].bSNPC == true && tmap->m_block_table[x+1][y+1].nArrayNo != nPos && tmap->m_block_table[x+1][y+1].nArrayNo != -1 ) 
			) 
			return false; 
	} 
	else 
	{ 
		if( tmap->m_block_table[x][y].bBlocked == true ||  
//			tmap->m_block_table[x][y].bITEM == true || 
			tmap->m_block_table[x][y].bPC == true || 
			tmap->m_block_table[x][y].bSNPC == true || 
			( tmap->m_block_table[x][y].bNPC == true && tmap->m_block_table[x][y].nArrayNo != nPos && tmap->m_block_table[x][y].nArrayNo != -1 ) 
			) 
			return false; 
		if( tmap->m_block_table[x+1][y].bBlocked == true ||  
//			tmap->m_block_table[x+1][y].bITEM == true || 
			tmap->m_block_table[x+1][y].bPC == true || 
			tmap->m_block_table[x+1][y].bSNPC == true || 
			( tmap->m_block_table[x+1][y].bNPC == true && tmap->m_block_table[x+1][y].nArrayNo != nPos && tmap->m_block_table[x+1][y].nArrayNo != -1 ) 
			) 
			return false; 
		if( tmap->m_block_table[x][y+1].bBlocked == true ||  
//			tmap->m_block_table[x][y+1].bITEM == true || 
			tmap->m_block_table[x][y+1].bPC == true || 
			tmap->m_block_table[x][y+1].bSNPC == true || 
			( tmap->m_block_table[x][y+1].bNPC == true && tmap->m_block_table[x][y+1].nArrayNo != nPos && tmap->m_block_table[x][y+1].nArrayNo != -1 ) 
			) 
			return false; 
		if( tmap->m_block_table[x+1][y+1].bBlocked == true ||  
//			tmap->m_block_table[x+1][y+1].bITEM == true || 
			tmap->m_block_table[x+1][y+1].bPC == true || 
			tmap->m_block_table[x+1][y+1].bSNPC == true || 
			( tmap->m_block_table[x+1][y+1].bNPC == true && tmap->m_block_table[x+1][y+1].nArrayNo != nPos && tmap->m_block_table[x+1][y+1].nArrayNo != -1 ) 
			) 
			return false; 
	} 
	return true; 
} 
 
// 방향 별로 길을 찾아본다... 
void CWayAi::BigGenerateSuccessors(NODE *BestNode,int dx,int dy, NPC_SIZE size, int nPos, bool bSummon ) 
{ 
	int tx,ty; 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"BigGenerateSuccessors시작 \r\n"; 
#endif 
 
	// Upper-Left...(대각선 좌측으로 갈수 있다면...) 
	tx = BestNode->x-1; 
	ty = BestNode->y-1; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
    
	// Upper... 
	tx=BestNode->x; 
	ty=BestNode->y-1; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
     
	// Upper-Right... 
	tx =BestNode->x+1; 
	ty = BestNode->y-1; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
  
	// Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
   
	// Lower-Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y+1; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
    
	// Lower... 
	tx=BestNode->x; 
	ty=BestNode->y+1; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
  
	// Lower-Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y+1; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
   
	// Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y; 
	if( BigisTile( tx, ty, size, nPos, bSummon ) )	 
		BigGenerateSucc(BestNode,tx,ty,dx,dy,size,nPos,bSummon); 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"Biggeneratesuccessor end  \r\n"; 
#endif 
} 
 
// 각각 타일의 길찾기 test 성공... 
void CWayAi::BigGenerateSucc(NODE *BestNode, int x, int y, int dx, int dy, NPC_SIZE size, int nPos, bool bSummon )	 
{ 
    int g,TileNumS,c=0; 
    NODE *Old,*Successor; 
 
    g=BestNode->g+1;    // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor 
    TileNumS=y*COLS+x;	// identification purposes 
 
    if ((Old=CheckOPEN(TileNumS)) != NULL) { // if equal to NULL then not in OPEN list, else it returns the Node in Old 
        for(c=0;c<8;c++) 
            if(BestNode->Child[c] == NULL) // Add Old to the list of BestNode's Children (or Successors). 
                break; 
        BestNode->Child[c]=Old; 
        if (g < Old->g) {  // if our new g value is < Old's then reset Old's parent to point to BestNode 
            Old->Parent=BestNode; 
            Old->g=g; 
            Old->f=g+Old->h; 
        } 
    } else if ((Old=CheckCLOSED(TileNumS)) != NULL) { // if equal to NULL then not in OPEN list, else it returns the Node in Old 
        for(c=0;c<8;c++) 
            if (BestNode->Child[c] == NULL) // Add Old to the list of BestNode's Children (or Successors). 
                break; 
        BestNode->Child[c]=Old; 
        if (g < Old->g) { // if our new g value is < Old's then reset Old's parent to point to BestNode 
            Old->Parent=BestNode; 
            Old->g=g; 
            Old->f=g+Old->h; 
            PropagateDown(Old);       /* Since we changed the g value of Old, we need 
                                         to propagate this new value downwards, i.e. 
                                         do a Depth-First traversal of the tree! */ 
        } 
    } else { 
        Successor=(NODE *)calloc(1,sizeof( NODE )); 
        Successor->Parent=BestNode; 
        Successor->g=g; 
        Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);  // should do sqrt(), but since we don't really 
        Successor->f=g+Successor->h;     // care about the distance but just which branch looks 
        Successor->x=x;                  // better this should suffice. Anyayz it's faster. 
        Successor->y=y; 
        Successor->NodeNum=TileNumS; 
        Insert(Successor);     /* Insert Successor on OPEN list wrt f */ 
        for(c=0;c<8;c++) 
            if (BestNode->Child[c] == NULL) /* Add Old to the list of BestNode's Children (or Successors). */ 
                break; 
        BestNode->Child[c]=Successor; 
    } 
 
} 
 
 
//________________________________________________________________________________ 
// 
// waypoint 길찾기 
//________________________________________________________________________________ 
// 
NODE* CWayAi::WPSearchWay( int x, int y, int dx, int dy ) 
{ 
	NODE *path; 
	bWayPossibled = true; 
	Stack=( AI_STATIC *)calloc(1,sizeof(AI_STATIC));  // setup the Stack. 
	path=WPFindPath(x,y,dx,dy); 
	Exe = true; 
 
	if( bWayPossibled ) 
		return (path); 
	else  
	{ 
		path = NULL; 
		return (path); 
	} 
 
	return (path); 
} 
 
NODE* CWayAi::WPFindPath( int sx, int sy, int dx, int dy ) 
{ 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"WPfindpath start \r\n"; 
#endif 
    NODE *Node, *BestNode; 
    int TileNumDest; 
	int Depth=0; 
 
    TileNumDest=dy*COLS+dx; 
 
    OPEN=(NODE *)calloc(1,sizeof( NODE )); 
	CLOSED=(NODE *)calloc(1,sizeof( NODE )); 
 
    Node=(NODE *)calloc(1,sizeof( NODE )); 
    Node->g=0; 
    Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);  // should really use sqrt(). 
    Node->f=Node->g+Node->h; 
    Node->NodeNum=sy*COLS+sx; 
    Node->x=sx; 
    Node->y=sy; 
 
    OPEN->NextNode=Node;						 /* make Open List point to first node */ 
    for (;;) { 
		BestNode=(NODE *)ReturnBestNode(); 
		if( BestNode == NULL ) 
			return NULL; 
 
        if (BestNode->NodeNum == TileNumDest)    /* if we've found the end, break and finish */ 
            break; 
		else WPGenerateSuccessors( BestNode, dx, dy); 
		/// 깊이 한계를 둘때.....................................................................		 
		if( DEPTH<++Depth )	{ 
			bWayPossibled = false; 
			break; 
		} 
    } 
 
    return (BestNode); 
} 
 
 
bool CWayAi::WPisTile(int x, int y ) 
{ 
	if( x < 0 || y < 0 || x >= (COLS/WAYPOINT) || y >= (ROWS/WAYPOINT) )  
		return false; 
	if( tmap->m_WayPoint[x][y] == 0 ) 
		return false; 
 
	return true; 
} 
 
// 방향 별로 길을 찾아본다... 
void CWayAi::WPGenerateSuccessors(NODE *BestNode,int dx,int dy ) 
{ 
#if defined ( GENERATE_LOG_PATH_FIND ) 
	g_GameServer.m_output<<"WPgeneratesuccessors start \r\n"; 
#endif 
	int tx,ty; 
	// Upper-Left...(대각선 좌측으로 갈수 있다면...) 
	tx = BestNode->x-1; 
	ty = BestNode->y-1; 
	if( WPisTile( tx, ty) ) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
    
	// Upper... 
	tx=BestNode->x; 
	ty=BestNode->y-1; 
	if( WPisTile( tx, ty )) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
     
	// Upper-Right... 
	tx =BestNode->x+1; 
	ty = BestNode->y-1; 
	if( WPisTile( tx, ty)) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
  
	// Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y; 
	if( WPisTile( tx, ty)) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
   
	// Lower-Right... 
	tx=BestNode->x+1; 
	ty=BestNode->y+1; 
	if( WPisTile( tx, ty)) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
    
	// Lower... 
	tx=BestNode->x; 
	ty=BestNode->y+1; 
	if( WPisTile( tx, ty)) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
  
	// Lower-Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y+1; 
	if( WPisTile( tx, ty)) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
   
	// Left... 
	tx=BestNode->x-1; 
	ty=BestNode->y; 
	if( WPisTile( tx, ty)) 
		WPGenerateSucc(BestNode,tx,ty,dx,dy); 
} 
 
// 각각 타일의 길찾기 test 성공... 
void CWayAi::WPGenerateSucc(NODE *BestNode, int x, int y, int dx, int dy ) 
{ 
    int g,TileNumS,c=0; 
    NODE *Old,*Successor; 
 
    g=BestNode->g+1;    // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor 
    TileNumS=y*COLS+x;	// identification purposes 
 
    if ((Old=CheckOPEN(TileNumS)) != NULL) { // if equal to NULL then not in OPEN list, else it returns the Node in Old 
        for(c=0;c<8;c++) 
            if(BestNode->Child[c] == NULL) // Add Old to the list of BestNode's Children (or Successors). 
                break; 
        BestNode->Child[c]=Old; 
        if (g < Old->g) {  // if our new g value is < Old's then reset Old's parent to point to BestNode 
            Old->Parent=BestNode; 
            Old->g=g; 
            Old->f=g+Old->h; 
        } 
    } else if ((Old=CheckCLOSED(TileNumS)) != NULL) { // if equal to NULL then not in OPEN list, else it returns the Node in Old 
        for(c=0;c<8;c++) 
            if (BestNode->Child[c] == NULL) // Add Old to the list of BestNode's Children (or Successors). 
                break; 
        BestNode->Child[c]=Old; 
        if (g < Old->g) { // if our new g value is < Old's then reset Old's parent to point to BestNode 
            Old->Parent=BestNode; 
            Old->g=g; 
            Old->f=g+Old->h; 
            PropagateDown(Old);       /* Since we changed the g value of Old, we need 
                                         to propagate this new value downwards, i.e. 
                                         do a Depth-First traversal of the tree! */ 
        } 
    } else { 
        Successor=(NODE *)calloc(1,sizeof( NODE )); 
        Successor->Parent=BestNode; 
        Successor->g=g; 
        Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);  // should do sqrt(), but since we don't really 
        Successor->f=g+Successor->h;     // care about the distance but just which branch looks 
        Successor->x=x;                  // better this should suffice. Anyayz it's faster. 
        Successor->y=y; 
        Successor->NodeNum=TileNumS; 
        Insert(Successor);     /* Insert Successor on OPEN list wrt f */ 
        for(c=0;c<8;c++) 
            if (BestNode->Child[c] == NULL) /* Add Old to the list of BestNode's Children (or Successors). */ 
                break; 
        BestNode->Child[c]=Successor; 
    } 
 
} 
 
//________________________________________________________________________________ 
// 
// waypoint 길찾기 끝 
//________________________________________________________________________________ 
//