Cómo implementar el algoritmo de búsqueda de rutas de estrella A basado en cocos2dx3.x

En este juego, juegas como un gato mezquino, recorriendo con cuidado una mazmorra custodiada por perros peligrosos. Si intentas cruzarte con un perro, te comerá, ¡a menos que puedas sobornarlo con un hueso!

Entonces, en este juego tu tarea es intentar recoger los huesos en el orden correcto y luego encontrar una ruta

para escapar a través de los perros.

Ten en cuenta que el gato sólo puede moverse horizontal o verticalmente (por ejemplo, no puede moverse en diagonal), y se moverá desde el punto central de un cuadrado a otro. Cada bloque puede ser transitable o intransitable.

¡Prueba este juego y comprueba si puedes encontrar una salida! Se recomienda leer el código para familiarizarse con su funcionamiento. Este es un juego de mapas de bloques bastante común, que modificaremos y usaremos el algoritmo de búsqueda de rutas A-Star en el siguiente tutorial.

Descripción general de Maze Cat and A Star

Como puedes ver, cuando haces clic en algún lugar del mapa, el gato saltará a los bloques adyacentes en la dirección en la que hiciste clic.

Nos gustaría modificar el programa para que el gato siga moviéndose en la dirección del bloque 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á la operación táctil como esta:

auto

listener =

EventListenerTouchOneByOne::create() ;

oyente->setSwallowTouches( true

);

oyente->onTouchBegan = [ this ](Toque *toque, Evento *evento){

oyente-> p>

(_gameOver)

{

return false ;

}

Point touchLocation =

_tileMap->convertTouchToNodeSpace(touch);

_cat->moveToward(touchLocation);

return

true

} ;

_eventDispatcher->addEventListenerWithSceneGraphPriority(listener,

this

);

Puedes ver aquí Simplemente llama a un método en el gato elfo para permitir que el gato se mueva al lugar donde haces clic en el mapa de bloques.

Lo que debemos hacer ahora es modificar el siguiente método en el archivo CatSprite.m, encontrar la ruta más corta hasta ese punto y comenzar a avanzar:

void

CatSprite::moveToward( const Point &target)

{

}

Crear la clase ShortestPathStep

Empezamos a crear una clase interna, Representa un paso en el camino. En este caso, es un bloque 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::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.

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();

return

pRet;

}

else

{

CC_SAFE_DELETE(pRet);

return

nullptr;

}

bool CatSprite::ShortestPathStep::initWithPosition( const

Punto &pos)

{

bool bRet = false ;

hacer

{

este

->setPosition(pos);

bRet = true ;

} while (0);

return

bRet;

}

int CatSprite::ShortestPathStep::getFScore() const

{

return

esto ->getGScore() + esto ->getHScore();

}

bool

CatSprite::ShortestPathStep::isEqual ( const CatSprite:: ShortestPathStep *otro)

const

{

devuelve 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,

esto ->getGScore(), esto

->getHScore (), this - >getFScore());

}

Como puedes ver, esta es una clase muy simple que registra el siguiente contenido:

Coordenadas del bloque

-Valor G (recuerda, este es el número de bloques desde el punto inicial hasta el punto actual)

-Valor H (recuerde, este es el número de bloques desde el punto actual hasta el número estimado de bloques en el punto objetivo)

El padre es su operación anterior

Valor F, que es el valor de suma del bloque (es el valor de G+H)

El método getDescription se define aquí para facilitar la depuración.

El método isEquals se crea si y solo si las coordenadas del bloque de dos ShortestPathSteps son iguales, son iguales (por ejemplo, representan el mismo bloque).

Crear listas abiertas y cerradas

Abra el archivo CatSprite.h y agregue el siguiente código:

cocos2d::Vector

_spOpenSteps ;

cocos2d::Vector

_spClosedSteps;

Comprueba los puntos inicial y final

Vuelve a implementar el método moveToward para obtener el bloque actual coordenadas y coordenadas del bloque objetivo, luego verifique si es necesario calcular una ruta y, finalmente, pruebe si las coordenadas del bloque objetivo son transitables (aquí solo las paredes son intransitables). Abra el archivo CatSprite.cpp y modifique el método moveToward de la siguiente manera:

void

CatSprite::moveToward( const Point &target)

{

Punto desdeTileCoord =

_layer->tileCoordForPosition( this ->getPosition());

Apunta aTileCoord

= _layer->tileCoordForPosition(destino)

if (fromTileCoord ==

toTileCoord)

{

CCLOG( "¡Ya estás ahí! :P" ) ;

return ;

}

(!_layer->isValidTileCoord(toTileCoord) ||

_layer->isWallAtTileCoord(toTileCoord))

{

SimpleAudioEngine::getInstance()->playEffect(

"hitWall.wav" );

return ;

}

CCLOG( "De: %f, %f" , deTileCoord.x,

deTileCoord.y);

CCLOG( "A: %f, %f" , toTileCoord.x,

toTileCoord.y);

}

Compile Ejecutar y haga clic en el mapa. Si no hace clic en el muro, podrá ver la siguiente información en la consola:

De:

24.000000, 0.000000

Hasta: 20.000000, 0.000000

Donde **Desde**

son las coordenadas del bloque del gato y **Hasta** son las coordenadas del bloque en el que se hizo clic.

Implementación del algoritmo de la estrella A

Según el algoritmo, el primer paso es agregar las coordenadas actuales a la lista abierta.

También se necesitan tres métodos auxiliares:

Un método para insertar un objeto ShortestPathStep en la posición apropiada (valor F ordenado)

- a El método es se utiliza para calcular el valor de movimiento de un bloque al bloque adyacente

Un método es calcular el valor H del bloque según 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();

ssize_t count =

_spOpenSteps.size();

ssize_t i = 0;

for (; i < count; ++i)

{

(stepFScore <= _spOpenSteps.at(i)->getFScore())

{

descanso

}

_spOpenSteps.insert(i, paso);

}

int

CatSprite::computeHScoreFromCoordToCoord( const Punto &fromCoord, const

Point &toCoord)

{

// Ignorando varios obstáculos que puedan haber en el camino

return abs(toCoord.x - fromCoord. x) + abs( toCoord.y -

fromCoord.y);

}

int CatSprite::costToMoveFromStepToAdjacentStep( const

ShortestPathStep *fromStep, const ShortestPathStep *toStep)

{

Debido a que no se puede caminar en diagonal y debido a que el terreno es transitable y no transitable, el costo es el mismo

// Si puede moverse en diagonal, o tiene pantanos, colinas, etc., entonces debe ser diferente

regresar

1 ;

}

A continuación, necesitamos un método para obtener todos los bloques transitables adyacentes de un bloque determinado. Dado que en este juego HelloWorld administra el mapa, agrega el método allí.

Abra el archivo HelloWorldScene.cpp y agregue el siguiente método:

PointArray

*HelloWorld::walkableAdjacentTilesCoordForTileCoord( const Point &tileCoord)

const

{

PointArray *tmp = PointArray::create(4);

// en

Punto

p(tileCoord .x , TileCoord.y - 1);

if ( esto ->isValidTileCoord(p)

&& ! esto

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p);

}

Izquierda

p.setPoint(tileCoord.x - 1,tileCoord.y);

if ( esto

->isValidTileCoord(p) && ! esto

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p);

}

// p>

Abajo

p.setPoint(tileCoord.x,tileCoord.y + 1);

if (este

->isValidTileCoord(p ) && ! esto

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p);

}

Derecha

p.setPoint(tileCoord.x + 1,tileCoord.y);

si ( esto

->isValidTileCoord(p) && ! esto

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p) ;

}

return

tmp;

}

Puedes continuar con el método moveToward en CatSprite.cpp. Ahora, agrega el siguiente código después del método moveToward:

bool

pathFound = false ;

_spOpenSteps.clear();

_spClosedSteps.clear();

Primero, agregue las coordenadas del bloque del gato a la lista abierta

esto

-> insertInOpenSteps(ShortestPathStep::createWithPosition(fromTileCoord));

hacer

{

/ /

Obtener el paso del valor F mínimo

// Debido a que es una lista ordenada, 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

Cabe señalar que si desea eliminar primero desde la lista abierta, debes tener cuidado con la memoria del objeto

_spOpenSteps.erase(0);

Si el objeto actual el paso es la coordenada del bloque objetivo, luego se completa

if (currentStep-> getPosition() ==

toTileCoord)

{

rutaEncontrada = true ;

PasoDeRutaMásCorto *tmpStep =

PasoActual;

CCLOG( "RUTA ENCONTRADA :" );

hacer

{

CCLOG( "%s" ,

tmpStep->getDescription().c_str());

tmpStep = tmpStep->getParent(); //

Hacia atrás

} while (tmpStep); //

Hasta que no haya un paso anterior

_spOpenSteps.clear();

_spClosedSteps.clear();

break

}

//Obtener las coordenadas de bloques adyacentes del paso actual

PointArray *adjSteps =

_layer-> walkableAdjacentTilesCoordForTileCoord(currentStep->getPosition());

for

(ssize_t i = 0; i < adjSteps->count(); ++i)

{

ShortestPathStep *paso

ShortestPathStep::createWithPosition(adjSteps->getControlPointAtIndex(i));

Comprueba si el paso ya está en la lista cerrada

if (esto ->getStepIndex(_spClosedSteps, paso) !=

-1)

{

continuar ;

}

// Calcular el costo desde el paso actual hasta este paso

int moveCost = this

->costToMoveFromStepToAdjacentStep(currentStep, step);

Compruebe si este paso ya está en la lista abierta

ssize_t index = this ->getStepIndex(_spOpenSteps,

step);

//No está en la lista abierta, agréguelo

if (index == -1)

{

Establecer el paso actual como el paso anterior

step->setParent(currentStep);

/ / El valor G es igual al valor G del paso anterior paso +

El costo desde el paso anterior hasta aquí

paso->setGScore(currentStep->getGScore() + moveCost);

El valor H es la cantidad de movimiento estimada desde este paso hasta las coordenadas del bloque objetivo

step->setHScore( this

-> ComputeHScoreFromCoordToCoord(step->getPosition( ), toTileCoord));

Agregar a la lista abierta en orden

this ->insertInOpenSteps(step); }

else

{

Obtener el paso anterior cuyo valor se ha calculado

paso = _spOpenSteps.at(index);

// Compruebe si el valor G es inferior al valor desde el paso actual hasta este paso

( (currentStep->getGScore() + moveCost) < step->getGScore())

{

El valor G es equivalente al valor G del paso anterior + coste desde el paso anterior hasta aquí

step->setGScore(currentStep->getGScore() +

moveCost);

/ / Debido a que el valor G cambia, el valor F también cambiará en consecuencia

// Por lo tanto, para mantener la lista abierta en orden, este paso debe eliminarse y luego insertarse nuevamente en orden

/ /

Antes de eliminar, debes mantener la referencia

paso->retain();

Puedes estar tranquilo ahora Eliminar, no te preocupes por ser liberado

_spOpenSteps.erase(index);

// Volver a insertar en orden

this

- >insertInOpenSteps(step);

Se puede publicar ahora porque la lista abierta debería contenerlo

paso->liberar();

}

} mientras

(_spOpenSteps. size() > 0);

(!pathFound)

{

SimpleAudioEngine::getInstance()->playEffect (

"hitWall.wav" );

}

Agregue el siguiente método:

ssize_t CatSprite::getStepIndex( const

cocos2d:: Vector &pasos, const CatSprite::ShortestPathStep *paso)

{

for

(ssize_t i = 0; i < pasos.tamaño(); ++ i)

{

(pasos.at(i)->isEqual(paso))

{

devuelve i;

}

devuelve

-1;

}

上篇: Las mujeres sueñan con beber agua. 下篇: ¿Es normal el sangrado de color rojo brillante después de una histeroscopia?