Cómo implementar el algoritmo de búsqueda de rutas de estrella A basado en cocos2dx3.x
Entonces, en este juego, tu tarea es recoger los huesos en el orden correcto y luego encontrar una ruta a través de la jauría de perros.
Escapar.
Ten en cuenta que el gato sólo puede moverse horizontal o verticalmente (es decir, no en diagonal), y se moverá del centro de un cuadrado a otro. Cada casilla puede ser transitable o intransitable.
¡Prueba este juego y comprueba si puedes encontrar la salida! Se recomienda leer el código y familiarizarse con su funcionamiento. Este es un juego de estilo de mapa de cubos bastante común, que modificaremos y usaremos el algoritmo de búsqueda de rutas de estrella A en el siguiente tutorial.
Descripción general de Maze Cat y A-Star
Como puedes ver, cuando haces clic en algún lugar del mapa, Maze Cat saltará en la dirección en la que hiciste clic en el cuadrado adyacente.
Esperamos modificar el programa para que el gato siga moviéndose en la dirección del cuadrado en el que haces clic, como muchos RPG o juegos de aventuras point-and-click.
Veamos cómo funciona el código que controla los eventos táctiles. Si abre el archivo HelloWorldScene.cpp, verá un código similar al siguiente para implementar operaciones táctiles:
auto
listener =
EventListenerTouchOneByOne::create ( );
oyente ->setSwallowTouches( true
);
oyente->onTouchBegan = [ this ](Toque *toque, Evento *evento){
si
(_gameOver)
{
devuelve falso;
}
Punto touchLocation =
_tileMap->convertTouchToNodeSpace(touch);
_cat->.moveToward(touchLocation);
regresar
true
};
_eventDispatcher->addEventListenerWithSceneGraphPriority( oyente,
este
);
Puedes mira Sí, esto es solo una llamada al método del objeto gato para hacer que el gato se mueva en el mapa de bloques a la ubicación en la que hiciste clic.
Lo que tenemos que hacer ahora es modificar el siguiente método en el archivo CatSprite.m para encontrar el camino más corto hasta ese punto y empezar a avanzar:
void
CatSprite::moveToward( const Point &target)
{
}
Crear la clase ShortestPathStep
Primero creamos una clase interna clase, representa una operación de paso en la ruta. En este caso, es un cuadrado y las puntuaciones F, G y H se calculan mediante el algoritmo de la estrella A.
clase ShortestPathStep : public cocos2d::Object
{
public
:
ShortestPathStep();
~ShortestPathStep();
estático ShortestPathStep
*createWithPosition( const cocos2d：*createWithPosition( const cocos2d::Point &pos) ;
bool initWithPosition(
const cocos2d::Point &pos);
int getFScore() const ;
bool isEqual(
const ShortestPathStep *other) const ;
std::string getDescription() const
CC_SYNTHESIZE(cocos2d::Punto, _posición, Posición);
CC_SYNTHESIZE( int,
_gScore, GScore);
CC_SYNTHESIZE( int, _hScore,
HScore);
CC_SYNTHESIZE(ShortestPathStep*, _ parent,
Parent);
};
Ahora agregue el siguiente código en la parte superior del archivo CatSprite.cpp. Agregue el siguiente código en la parte superior. del archivo cpp.
CatSprite::ShortestPathStep::ShortestPathStep()
:
_position(Punto::CERO),
_gScore(0) ,
_hScore(0),
_parent(nullptr)
{
}
CatSprite:: ShortestPathStep::~ShortestPathStep()
{
}
CatSprite::.ShortestPathStep
*CatSprite::ShortestPathStep::createWithPosition ( punto const
&pos)
{
Pasoderutamáscorto * pRet = newPasoderutamáscorto();
if (pRet
&&
pRet->initWithPosition(pos))
{
pRet->.autorelease();
Regresar
pRet;
}
else
{
CC_SAFE_DELETE(pRet);
return
nullptr;
}
}
bool CatSprite::ShortestPathStep::initWithPosition( const
Punto &pos)
{
bool bRet = false ;
haz
{
esto
->setPosition(pos);
bRet = true ;
} while (0);
return
bRet;
}
int CatSprite::ShortestPathStep::getFScore() const
{
return
this ->getGScore() + this ->getHScore();
}
bool
CatSprite::ShortestPathStep::isEqual( const CatSprite ::ShortestPathStep *otro)
const
{
devuelve esto -> esto ->.getPosition() ==
otro ->getPosition();
}
std::string
CatSprite::ShortestPathStep::getDescription() const
{
return
StringUtils::format( "pos=[%.0f;%.0f] g=%d h=%d f=%d" ,
esto
->getPosition().x, esto -> getPosition().y,
this ->getGScore(), this
->getHScore(), this ->getFScore());
}
Como puedes ver, esto es una clase muy simple que registra lo siguiente:
-
Las coordenadas del cuadrado
- El valor G (recuerda, esto es desde el punto inicial a Número de cuadrados desde el punto actual)
- Valor H (recuerde, este es el número estimado de cuadrados desde el punto actual hasta el punto objetivo)
-
Parent Es la última operación
-
El valor F es la suma del número de cuadrados (es el valor de G+H)
El método getDescription se define aquí, para fines de depuración. Creó un método isEquals que equivale a dos ShortestPathSteps solo si tienen las mismas coordenadas cuadradas (por ejemplo, representan el mismo cuadrado).
Crea una lista de apertura y cierre
Abre el archivo CatSprite.h y agrega el siguiente código:
Crea un archivo h de lista de apertura y cierre y agrega el siguiente código:
p>
cocos2d::Vector
_spOpenSteps;
cocos2d::Vector
_ spClosedSteps;
Verifique los puntos inicial y final
Vuelva a implementar el método moveToward, obtenga las coordenadas de la cuadrícula actual y las coordenadas de la cuadrícula de destino, luego verifique si es necesario calcular la ruta y finalmente pruebe si la Las coordenadas de la cuadrícula objetivo son transitables (en este caso, solo la pared es intransitable).
Abra el archivo CatSprite.cpp y modifique el método moveToward de la siguiente manera:
void
CatSprite:: moveToward( const Point &target)
{
Punto deTileCoord =
_layer->tileCoordForPosition( this ->getPosition());
Apunte aTileCoord
= _layer->tileCoordForPosition(destino) ;
Apunta aTileCoord p>
if (fromTileCoord =
toTileCoord)
{
CCLOG( "Ya estás ¡ahí!:P" );
Regresar;
}
if
(!_layer->isValidTileCoord(toTileCoord) ||
_layer-> isWallAtTileCoord(toTileCoord))
{
SimpleAudioEngine:.getInstance()->playEffect(
"hitWall. wav" );
return ;
}
CCLOG( "De: %f, %f" , deTileCoord.x,
fromTileCoord.y);
CCLOG( "Para: %f, %f" , toTileCoord.x,
toTileCoord.y);
}
Compílalo y ejecútalo, luego haz clic en el mapa, si no hiciste clic en el muro, podrás ver lo siguiente en la consola:
Desde:
24.000000, 0.000000
Hasta: 20.000000, 0.000000
Entre ellos, **Desde**
es la coordenada del cuadrado donde se encuentra el gato. y **A** es la coordenada del cuadrado en el que se hizo clic.
Implementando el algoritmo A-Star
Según este algoritmo, el primer paso es agregar las coordenadas actuales a la lista abierta. Se requieren tres métodos auxiliares:
-
- Un método que inserta un objeto ShortestPathStep en la posición apropiada (valores F ordenados)
- Un método que calcula el método A para mover un cuadrado al valor de un cuadrado adyacente
-
- Un método para calcular el valor H de un cuadrado basado en el algoritmo de "distancia de Manhattan".
Abra el archivo CatSprite.cpp y agregue el siguiente método:
void
CatSprite::insertInOpenSteps(CatSprite::ShortestPathStep *step)
{
int
stepFScore = paso->getFScore();
size_t count =
_spOpenSteps.size() ;
size_t i = 0;
for (; i <. count; ++i)
{
si
(stepFScore <= _spOpenSteps.at(i)->getFScore())
{
descanso
}
}
_ spOpenSteps.insert(i, paso);
}
int
CatSprite::computeHScoreFromCoordToCoord( const Punto &fromCoord, const
Point & toCoord)
{
// Ignora varios obstáculos posibles
return abs(toCoord.x - fromCoord .x) + abs(toCoord.y -
fromCoord.y);
}
int CatSprite::costToMoveFromStepToAdjacentStep( const
ShortestPathStep *fromStep, const ShortestPathStep *toStep)
{<
//
Debido a que no puedes caminar en Diagon, el terreno es diferente para transitable y intransitable El costo de caminar es el mismo
// Si puedes moverte en diagonal, o hay pantanos, colinas y otros terrenos. ,
Devoluciones
1;
}
A continuación, necesita un método para obtener todas las fases de un cuadrado determinado, cuadrados transitables adyacentes. . Dado que HelloWorld administra el mapa en este juego, agrega el método aquí.
Abra el archivo HelloWorldScene.cpp y agregue los siguientes métodos:
PointArray
*HelloWorld::walkableAdjacentTilesCoordForTileCoord( Const Point &.tileCoord)
const
{
PointArray *tmp = PointArray::create(4);
// arriba
Punto
p (tileCoord .x, TileCoord.y - 1 );
if ( this ->isValidTileCoord(p)
&& !
->isWallAtTileCoord(p) )
{
tmp->addControlPoint(p);
}
//
izquierda
p.setPoint(tileCoord.x - 1,tileCoord.y);
if ( esto
->isValidTileCoord(p) && ! esto
->isWallAtTileCoord(p))
{
tmp->addControlPoint(p);
}
/ /
bajo
p.setPoint(tileCoord.x,tileCoord.y);
si (este
->isValidTileCoord( p) &&! esto
->isWallAtTileCoord(p))
{
tmp->addControlPoint(p);
}
return
tmp;
}
Podría continuar con el método moveToward en CatSprite.cpp y agregar el siguiente código después del método moveToward :
bool
pathFound = false ;
_spOpenSteps.clear();
_ spClosedSteps.clear();
//
Primero, agregue las coordenadas del cuadrado del gato a la lista abierta
this
->insertInOpenSteps(ShortestPathStep:.createWithPosition( fromTileCoord)) ;
do
{
//
Obtener el paso de valor F más pequeño
// porque esta es una lista ordenada, por lo que el primer paso es siempre el valor F más pequeño
ShortestPathStep * currentStep =
_spOpenSteps.at(0);
/ /
Agregar el paso actual a la lista cerrada
_spClosedSteps.pushBack(currentStep);
/
Eliminarlo de la lista abierta Quitar de
/
Cabe señalar que si primero desea eliminar el objeto de la lista abierta, debe tener cuidado
La memoria del objeto de gestión
_spOpenSteps.erase(0);
/
Si el paso actual es la coordenada de la cuadrícula de destino, entonces se completa
if (currentStep->getPosition() ==
toTileCoord)
{
pathFound = true
ShortestPathStep *tmpStep; =
p>
pasoactual;
CCLOG( "RUTA ENCONTRADA: " );
hacer
{
CCLOG( "% s" ,
tmpStep->getDescription().c_str());
tmpStep = tmpStep->getParent(); p>
hacia atrás
} while (tmpStep); //
hasta que no haya ningún paso previo
_spOpenSteps.clear(); >
_ spClosedSteps.clear ();
break
}
// Obtener las coordenadas de los cuadrados adyacentes del paso actual
PointArray *adjSteps =
_layer-> walkableAdjacentTilesCoordForTileCoord(currentStep-> getPosition());
for
(ssize_t i = 0; i < adjSteps->count(); + +i)
{
PasoDeRutaMásCorto *paso
=
ShortestPathStep::createWithPosition(adjSteps->getControlPointAtIndex( i));
/
Compruebe si el paso ya está en la lista de cierre
if ( this - >getStepIndex(_spClosedSteps, paso) !=
-1)
{
continuar
}
int moveCost = this
-> costToMoveFromStep(_spClosedSteps) ! costToMoveFromStepToAdjacentStep(currentStep, step);
//
Comprueba si este paso ya está en la lista abierta
size_t index = this -> getStepIndex(_ spOpenSteps ,
paso);
// no está en la lista abierta, agréguelo
if (index == -1)
{
//
/
Establecer el paso actual como la operación anterior
step ->setParent( currentStep);
// El valor G es igual al valor G del paso anterior +
El costo de llegar aquí desde el paso anterior
step-> (curre
ntStep->getGScore() + moveCost);
/
El valor H es la cantidad de movimiento estimada desde este paso hasta las coordenadas de la cuadrícula de destino
paso- > setHScore(this
->computeHScoreFromCoordToCoord(step->getPosition(), toTileCoord) );
//
Agregar a la lista abierta por turno
p>esto ->insertInOpenSteps(paso);
}
else
{
//
//
Obtiene el paso anterior cuyo valor ha sido calculado
step = _spOpenSteps.at(index);
/Checks si el valor G es menor que el valor del paso actual hasta este paso
if
((currentStep->getGScore() + moveCost) < step->.getGScore( ))
{
//
El valor G es igual al valor G del paso anterior + el coste de llegar hasta aquí desde el paso anterior
step->setGScore( currentStep->getGScore() +
moveCost);
// Porque cuando el valor G cambia, el valor F también cambiará en consecuencia
// Entonces, para mantener la lista abierta en orden, este paso debe eliminarse y volver a insertarse en orden
/
La referencia debe permanece sin cambios antes de ser eliminado
step->retrieve();
Ahora se puede eliminar sin preocuparse por ser liberado
_spOpenSteps.erase(index);
// Vuelva a insertar en secuencia
esto
->insertInOpenSteps(paso);
//
Ahora puedes liberarlo porque la lista abierta debería guardarlo
paso->liberar();
}
}
}
}
}
}
} mientras
(_spOpenSteps.size() > 0);
if
(!pathFound)
{
SimpleAudioEngine::getInstance()->playEffect (
"hitWall .wav" );
}
Agregue el siguiente método:
Agregue el siguiente método:
size_t CatSprite::getStepIndex( const
cocos2d::Vector &steps, const CatSprite::ShortestPathStep *paso)
{
para
(ssize_t i = 0; i < pasos.tamaño (); ++i)
{
si
(pasos.at(i)- >esEqual(paso))
{
return i;
}<
/p>
}
regresar
-1;
}