path.cpp

网络游戏龙族 完整的登陆器 C++ 源代码

			return NULL;
		}
	
		lpspTemp = GLPSP_OPEN->lpNext;
		GLPSP_OPEN->lpNext = lpspTemp->lpNext;
		lpspTemp->lpNext = GLPSP_CLOSED->lpNext;
		GLPSP_CLOSED->lpNext = lpspTemp;
	
		if ( lpspTemp->number == nDestTile )
		{
			break;
		}
	
		oldx = lpspTemp->x, oldy = lpspTemp->y;
	
		// upper
		x = lpspTemp->x, y = lpspTemp->y - 1;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy, 2 );
		}
		// left
		x = lpspTemp->x - 1, y = lpspTemp->y;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
		// right
		x = lpspTemp->x + 1, y = lpspTemp->y;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
		// down
		x = lpspTemp->x, y = lpspTemp->y + 1;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ) )
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
	
	
	
		// upper-right
		x = lpspTemp->x + 1, y = lpspTemp->y - 1;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
		// right-down
		x = lpspTemp->x + 1, y = lpspTemp->y + 1;
		if ( FreeTile( lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
		// left-down
		x = lpspTemp->x - 1, y = lpspTemp->y + 1;
		if ( FreeTile( lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
		// left-up
		x = lpspTemp->x - 1, y = lpspTemp->y - 1;
		if ( FreeTile( lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
	}
	
	return	lpspTemp;
}	
	
	
	
	
	
LPSP_NODE
PathFind( LPCHARACTER lpcharacter, int sx, int sy, int dx, int dy )
{	
	LPMAPFILE	lpMapFile = &g_Map.file;
	LPSP_NODE	lpspNode, lpspTemp;
	int			nDestTile = dy * g_Map.file.wWidth + dx;
	int			x, y;
	int         c = 0;
	int			oldx, oldy;
	GLPSP_OPEN = ( LPSP_NODE )GlobalAlloc( GPTR, sizeof( SP_NODE ) );
	GLPSP_CLOSED = ( LPSP_NODE )GlobalAlloc( GPTR, sizeof( SP_NODE ));
	GLPSP_STACK = ( LPSP_STACK )GlobalAlloc( GPTR, sizeof( SP_STACK ) );
	lpspNode = ( LPSP_NODE )GlobalAlloc( GPTR, sizeof( SP_NODE ) );
	if ( GLPSP_OPEN == NULL || GLPSP_CLOSED == NULL || GLPSP_STACK == NULL || lpspNode == NULL )
	{
		return	NULL;
	}
	
	lpspNode->g = 0;
	lpspNode->h = 1;//( sx - dx ) * ( sx - dx ) + ( sy - dy ) * ( sy - dy );
	lpspNode->f = lpspNode->g + lpspNode->h;
	lpspNode->number = sy * g_Map.file.wWidth + sx;
	lpspNode->x = sx;
	lpspNode->y = sy;
	
	GLPSP_OPEN->lpNext = lpspNode;
	while ( 1 )
	{
		if ( GLPSP_OPEN->lpNext == NULL )
		{
			return	NULL;
		}

		c++;
		if( c > 1000 ) 	
		{
			return NULL;
		}

		lpspTemp = GLPSP_OPEN->lpNext;
		GLPSP_OPEN->lpNext = lpspTemp->lpNext;
		lpspTemp->lpNext = GLPSP_CLOSED->lpNext;
		GLPSP_CLOSED->lpNext = lpspTemp;

		if ( lpspTemp->number == nDestTile )
		{
			break;
		}

		oldx = lpspTemp->x, oldy = lpspTemp->y;

		// upper
		x = lpspTemp->x, y = lpspTemp->y - 1;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy, 2 );
		}
		// left
		x = lpspTemp->x - 1, y = lpspTemp->y;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
		// right
		x = lpspTemp->x + 1, y = lpspTemp->y;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}
		// down
		x = lpspTemp->x, y = lpspTemp->y + 1;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ) )
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,2 );
		}



		// upper-right
		x = lpspTemp->x + 1, y = lpspTemp->y - 1;
		if ( FreeTile(lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,3 );
		}
		// right-down
		x = lpspTemp->x + 1, y = lpspTemp->y + 1;
		if ( FreeTile( lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,3 );
		}
		// left-down
		x = lpspTemp->x - 1, y = lpspTemp->y + 1;
		if ( FreeTile( lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,3 );
		}
		// left-up
		x = lpspTemp->x - 1, y = lpspTemp->y - 1;
		if ( FreeTile( lpcharacter, oldx, oldy, x, y ))
		{
			GenerateSucc( lpspTemp, x, y, dx, dy,3 );
		}
	}

	return	lpspTemp;
}

void
GenerateSucc( LPSP_NODE lpspNode, int x, int y, int dx, int dy, int dist )
{
	int			g, nTile;
	int			i;
	LPSP_NODE	lpspOld, lpspSucc = 0;

	g = lpspNode->g + dist;
	nTile = y * g_Map.file.wWidth + x;

	if ( ( lpspOld = CheckOPEN( nTile ) ) != NULL )
	{
		for ( i = 0; i < 8; i++ )
		{
			if ( lpspNode->lpChild[ i ] == NULL )
			{
				break;
			}
		}

		if( i == 8 ) 
		{
			__asm nop;
		}


		lpspNode->lpChild[ i ] = lpspOld;
		if ( g < lpspOld->g )
		{
			lpspOld->lpParent = lpspNode;
			lpspOld->g = g;
			lpspOld->f = g + lpspOld->h;
		}
	}
	else if ( ( lpspOld = CheckCLOSED( nTile ) ) != NULL )
	{
		for ( i = 0; i < 8; i++ )
		{
			if ( lpspNode->lpChild[ i ] == NULL )
			{
				break;
			}
		}
		if( i == 8 ) 
		{
			__asm nop;
		}

		lpspNode->lpChild[ i ] = lpspOld;
		if ( g < lpspOld->g )
		{
			lpspOld->lpParent = lpspNode;
			lpspOld->g = g;
			lpspOld->f = g + lpspOld->h;

			PropagateDown( lpspOld, dist );
		}
	}
	else
	{
		lpspSucc = ( LPSP_NODE )GlobalAlloc( GPTR, sizeof( SP_NODE ) );
		lpspSucc->lpParent = lpspNode;
		lpspSucc->g = g;
	
//		if( rand()% tool_Pathfind )	lpspSucc->h = rand()%50 + 1;
//		else						lpspSucc->h = 1;//( x - dx ) * ( x - dx ) + ( y - dy ) * ( y - dy );
//		if( rand()% tool_Pathfind )	lpspSucc->h = rand()%50 + 1;
		lpspSucc->h =dist;//( x - dx ) * ( x - dx ) + ( y - dy ) * ( y - dy );

		lpspSucc->f = g + lpspSucc->h;
		lpspSucc->x = x;
		lpspSucc->y = y;
		lpspSucc->number = nTile;

		Insert( lpspSucc );

		for( i = 0; i < 8; i++ )
		{
			if ( lpspNode->lpChild[ i ] == NULL )
			{
				break;
			}
		}

		if( i == 8 ) 
		{
			__asm nop;
		}


		lpspNode->lpChild[ i ] = lpspSucc;
	}
}

void
PropagateDown( LPSP_NODE lpspNode, int dist )
{
	int			i;
	int			g = lpspNode->g;
	LPSP_NODE	lpspChild, lpspParent;

	for ( i = 0; i < 8; i++ )
	{
		if ( ( lpspChild = lpspNode->lpChild[ i ] ) == NULL )
		{
			break;
		}

		if ( g + dist < lpspChild->g )
		{
			lpspChild->g = g + dist;
			lpspChild->f = lpspChild->g + lpspChild->h;
			lpspChild->lpParent = lpspNode;
			Push( lpspChild );
		}
	}

	while ( GLPSP_STACK->lpNext != NULL )
	{
		lpspParent = Pop( );
		for ( i = 0; i < 8; i++ )
		{
			if ( ( lpspChild = lpspParent->lpChild[ i ] ) == NULL )
			{
				break;
			}
			if ( lpspParent->g + dist < lpspChild->g )
			{
				lpspChild->g = lpspParent->g + dist;
				lpspChild->f = lpspChild->g + lpspChild->h;
				lpspChild->lpParent = lpspParent;
				Push( lpspChild );
			}
		}
	}
}

LPSP_NODE
CheckOPEN( int tilenum )
{
	LPSP_NODE	lpspNode;

	lpspNode = GLPSP_OPEN->lpNext;
	while ( lpspNode != NULL )
	{
		if ( lpspNode->number == tilenum )
		{
			return	lpspNode;
		}
		else
		{
			lpspNode = lpspNode->lpNext;
		}
	}

	return	NULL;
}

LPSP_NODE
CheckCLOSED( int tilenum )
{
	LPSP_NODE	lpspNode;

	lpspNode = GLPSP_CLOSED->lpNext;
	while ( lpspNode != NULL )
	{
		if ( lpspNode->number == tilenum )
		{
			return	lpspNode;
		}
		else
		{
			lpspNode = lpspNode->lpNext;
		}
	}

	return	NULL;
}

void
Insert( LPSP_NODE lpspNode )
{
	LPSP_NODE	lpspTmp1, lpspTmp2;
	int			f;

	if ( GLPSP_OPEN->lpNext == NULL )
	{
		GLPSP_OPEN->lpNext = lpspNode;
		return;
	}

	f = lpspNode->f;
	lpspTmp1 = GLPSP_OPEN;
	lpspTmp2 = GLPSP_OPEN->lpNext;
	while ( ( lpspTmp2 != NULL ) && ( lpspTmp2->f < f ) )
	{
		lpspTmp1 = lpspTmp2;
		lpspTmp2 = lpspTmp2->lpNext;
	}

	lpspNode->lpNext = lpspTmp2;
	lpspTmp1->lpNext = lpspNode;
}

void
Push( LPSP_NODE lpspNode )
{
	LPSP_STACK	lpspStack = 0;

	lpspStack = ( LPSP_STACK )GlobalAlloc( GPTR, sizeof( SP_STACK ) );
	lpspStack->lpNode = lpspNode;
	lpspStack->lpNext = GLPSP_STACK->lpNext;
	GLPSP_STACK->lpNext = lpspStack;
}

LPSP_NODE
Pop( void )
{
	LPSP_NODE	lpspNode;
	LPSP_STACK	lpspStack;

	lpspStack = GLPSP_STACK->lpNext;
	lpspNode = lpspStack->lpNode;
	GLPSP_STACK->lpNext = lpspStack->lpNext;
	GlobalFree( lpspStack );

	return	lpspNode;
}





// 捞悼格钎痢鳖瘤甫 流急栏肺 弊绢 面倒积扁绰巴捞 乐唱 舅酒夯促. 
//  TileMap[][]阑 眉农窍咯 面倒登搁 0阑 府畔.

// 010724 KHS
int CheckLineCollision( LPCHARACTER ch, int sx, int sy, int ex, int ey )
{
	int t,distance;
	int xerr = 0, yerr = 0, delta_x, delta_y;
	int incx, incy;

	
	if( sx < 0 ) return 0;
	if( sy < 0 ) return 0;
	if( ex >= g_Map.file.wWidth  ) return 0;
	if( ey >= g_Map.file.wHeight ) return 0;

	delta_x = ex - sx;
	delta_y = ey - sy;
	
	incx = (delta_x > 0) ?  1 : ((delta_x == 0) ? 0 : -1) ;
	incy = (delta_y > 0) ?  1 : ((delta_y == 0) ? 0 : -1) ;
	
	delta_x = abs(delta_x);
	delta_y = abs(delta_y);
	
	distance = (delta_x > delta_y) ? delta_x : delta_y ;


	bool occupied_flag = false;
	TILE *pT = &TileMap[ ch->position.x][ ch->position.y];
	if( pT->occupied ) 
	{
		pT->occupied = 0;
		occupied_flag = true;
	}

	if( !FreeTile( ch, sx, sy , sx, sy ) ) goto FALSE_;
	
	for(t=0; t<=distance; t++)
	{
		xerr += delta_x;
		yerr += delta_y;
		if(xerr >= distance)    {        xerr -= distance;       sx += incx;      }
		if(yerr >= distance)    {        yerr -= distance;       sy += incy;      }
		if( !FreeTile( ch, sx, sy , sx, sy ) ) goto FALSE_;
	}

	if( occupied_flag )	pT->occupied = 1;

	return 1;


FALSE_:

	if( occupied_flag )	pT->occupied = 1;

	return 0;
}	






















////////////////////////////////////////////////////////////






// int onefxpal, int old_color, int new_color)
/*
int PaintPath(int x, int y, int ex, int ey )
{
	struct s_v{
		int  x,
			 y;
	} s_val, c_val;
		
	int stack_add[640];
	int ri,rj,i,j,first,sp;
		
	sp=0;
		
	s_val.x = x;
	s_val.y = y;
	sp += 2;
		
	stack_add[sp] = s_val.x;
	stack_add[sp+1] = s_val.y;
	while(sp!=0){
		c_val.x = stack_add[sp];
		c_val.y = stack_add[sp+1];
		sp -= 2;
		
		i = c_val.x;
		j = c_val.y;
		
		while( FreeTile( NULL, i,j, i,j) ) i++;
		ri = i - 1;
		first = 1;
		i = ri;
		
		while( FreeTile( NULL, i,j, i,j) ){
			//PutPixel(i,j,new_color);
			if( FreeTile( NULL, i,j+1, i,j+1) ) first = 1;
			else{
				if((first == 1) && ((GetPixel(i,j+1)) != new_color)){
					s_val.x = i;
					s_val.y = j+1;
					sp +=  2;

					stack_add[sp] = s_val.x;
					stack_add[sp+1] = s_val.y;
					first = 0;
				}
			}
			i --;
		}
		rj = i;

		first = 1;
		i = ri;

		while(rj<i){
			if((GetPixel(i,j-1)) != old_color) first = 1;
			else{
				if((first == 1) && ((GetPixel(i,j-1)) !=new_color)){
					s_val.x = i;
					s_val.y = j-1;
					sp += 2;
					stack_add[sp] = s_val.x;
					stack_add[sp+1] = s_val.y;
					first = 0;
				}
			}
			i --;
		}
	}
}*/