China Naming Network - Company naming - How to implement the A-star pathfinding algorithm based on cocos2dx3.x

How to implement the A-star pathfinding algorithm based on cocos2dx3.x

In this game, you play as a petty cat who carefully navigates a dungeon guarded by dangerous dogs. If you try to cross a dog, he'll eat you - unless you can bribe it with a bone!

So in this game your task is to try to pick up the bones in the correct order and then find a route

to escape through the dogs.

Note that the cat can only move horizontally or vertically (for example, it cannot move diagonally), and it will move from the center point of one square to another. Each block can be either passable or impassable.

Try this game and see if you can find a way out! It is recommended that you read the code to familiarize yourself with how it works. This is a fairly ordinary block-map game, which we will modify and use the A-Star pathfinding algorithm in the next tutorial.

Maze Cat and A Star Overview

As you can see, when you click somewhere on the map, the cat will jump to adjacent blocks in the direction you clicked. .

We would like to modify the program so that the cat continues to move in the direction of the block you click, like many RPGs or point-and-click adventure games.

Let's take a look at how the code that controls touch events works. If you open the HelloWorldScene.cpp file, you will see the touch operation like this:

auto

listener =

EventListenerTouchOneByOne::create() ;

listener-gt; setSwallowTouches( true

);

listener-gt; onTouchBegan = [ this ](Touch *touch, Event *event){

if

(_gameOver)

{

return false ;

}

Point touchLocation =

_tileMap-gt;convertTouchToNodeSpace(touch);

_cat-gt;moveToward(touchLocation);

return

true

};

_eventDispatcher-gt; addEventListenerWithSceneGraphPriority(listener,

this

);

You can see that here is just a method called on the cat elf to let the cat move to the place you click on the block map.

What we need to do now is to modify the following method in the CatSprite.m file, find the shortest path to that point, and start moving forward:

void

CatSprite::moveToward(const Point & target)

{

}

Creating the ShortestPathStep class

We start by creating an internal Class, representing a step operation on the path. In this case, it's a square and the F, G and H scores calculated by the A-star algorithm.

class ShortestPathStep: public cocos2d::Object

{

public

:

ShortestPathStep();

~ShortestPathStep();

static 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::Point, _position, Position);

CC_SYNTHESIZE( int,

_gScore, GScore);

CC_SYNTHESIZE(int, _hScore,

HScore);

CC_SYNTHESIZE(ShortestPathStep*, _parent,

Parent);

};

Now add the following code to the top of the CatSprite.cpp file.

CatSprite::ShortestPathStep::ShortestPathStep()

:

_position(Point::ZERO),

_gScore(0) ,

_hScore(0),

_parent(nullptr)

{

}

CatSprite:: ShortestPathStep::~ShortestPathStep()

{

}

CatSprite::ShortestPathStep

*CatSprite::ShortestPathStep::createWithPosition( const Point

amp; pos)

{

ShortestPathStep *pRet = new ShortestPathStep();

if (pRet

amp;amp;

pRet-gt;initWithPosition(pos))

{

pRet-gt;autorelease();

return

pRet;

}

else

{

CC_SAFE_DELETE(pRet);

return

nullptr;

}

}

bool CatSprite::ShortestPathStep::initWithPosition( const

Point amp; pos)

{

bool bRet = false;

do

{

this

-gt; setPosition(pos);

bRet = true;

} while (0);

return

bRet;

}

int CatSprite::ShortestPathStep::getFScore() const

{

return

this -gt;getGScore() this -gt;getHScore();

}

bool

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

const

{

return this -gt; getPosition() ==

const

p>

other-gt;getPosition();

}

std::string

CatSprite::ShortestPathStep::getDescription() const

{

return

StringUtils::format( "pos=[.0f;.0f] g=d h=d f=d" ,

>this

-gt; getPosition().x, this -gt; getPosition().y,

this -gt; getGScore(), this

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

}

As you can see, this is a very simple class that records the following:

-

The coordinates of the block

- G value (remember, this is the number of blocks from the starting point to the current point)

- H value (remember, this is the estimated number of blocks from the current point to the target point)

-

Parent is its previous operation

-

-

p>

F value, this is the sum value of the block (it is the value of G H)

The getDescription method is defined here to facilitate debugging. The isEquals method is created, if and only if the block coordinates of two ShortestPathSteps are the same, they are equal (for example, they represent the same block).

Create Open and Closed lists

Open the CatSprite.h file and add the following code:

cocos2d::Vector

_spOpenSteps;

cocos2d::Vector

_spClosedSteps;

Check the start and end points

Reimplement the moveToward method to obtain the current block coordinates and target block coordinates, then checks whether a path needs to be calculated, and finally tests whether the target block coordinates are walkable (only walls are unwalkable here).

Open the CatSprite.cpp file and modify the moveToward method as follows:

void

CatSprite:: moveToward( const Point amp; target)

{

Point fromTileCoord =

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

Point toTileCoord

= _layer-gt; tileCoordForPosition(target);

if (fromTileCoord ==

toTileCoord)

{

CCLOG( "You're already there! :P" );

return ;

}

if

(!_layer-gt; isValidTileCoord(toTileCoord) ||

_layer-gt; isWallAtTileCoord(toTileCoord))

{

SimpleAudioEngine::getInstance()-gt; playEffect(

"hitWall .wav" );

return ;

}

CCLOG( "From: f, f" , fromTileCoord.x,

fromTileCoord.y);

CCLOG( "To: f, f" , toTileCoord.x,

toTileCoord.y);

}

Compile and run, click on the map, if you do not click on the wall, you can see the following information in the console:

From:

24.000000, 0.000000

To: 20.000000, 0.000000

Where **From**

is the cat’s block coordinates, and **To** is the clicked block coordinates.

Implementing the A-star algorithm

According to the algorithm, the first step is to add the current coordinates to the open list.

Three auxiliary methods are also needed:

-

A method to insert a ShortestPathStep object into the appropriate position (ordered F value)

- A The method is used to calculate the movement value from one block to the adjacent block

-

One method is to calculate the H value of the block based on the "Manhattan distance" algorithm

Open the CatSprite.cpp file and add the following method:

void

CatSprite::insertInOpenSteps(CatSprite::ShortestPathStep *step)

{

int

stepFScore = step-gt; getFScore();

ssize_t count =

_spOpenSteps.size();

ssize_t i = 0;

for (; i lt; count; i)

{

if

(stepFScore lt; = _spOpenSteps.at(i)-gt;getFScore())

{

break

}

}

_spOpenSteps.insert(i, step);

}

int

CatSprite::computeHScoreFromCoordToCoord( const Point & fromCoord, const

Point & toCoord)

{

// Ignores various obstacles that may be on the way

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

fromCoord.y);

}

int CatSprite::costToMoveFromStepToAdjacentStep( const

ShortestPathStep *fromStep, const ShortestPathStep *toStep)

{

//

Because you cannot walk diagonally, and because the terrain is the cost of walkable and unwalkable All the same

//If it can move diagonally, or has swamps, hills, etc., then it must be different

return

1 ;

}

Next, we need a method to get all adjacent walkable blocks of a given block. Since in this game HelloWorld manages the map, add the method there.

Open the HelloWorldScene.cpp file and add the following methods:

PointArray

*HelloWorld::walkableAdjacentTilesCoordForTileCoord( const Point & tileCoord)

const

{

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

// on

Point

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

if ( this -gt; isValidTileCoord(p)

amp; ! this

-gt; isWallAtTileCoord(p))

{

tmp-gt;addControlPoint(p);

}

//

Left

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

if ( this

-gt; isValidTileCoord(p) amp;amp; ! this

-gt;isWallAtTileCoord(p))

{

tmp-gt;addControlPoint(p);

}

//

Next

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

if ( this

-gt; isValidTileCoord(p) amp; amp; ! this

-gt; isWallAtTileCoord(p))

{

tmp-gt;addControlPoint(p);

}

//

right

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

if ( this

-gt; isValidTileCoord(p) amp; ! this

-gt; isWallAtTileCoord(p) )

{

tmp-gt;addControlPoint(p);

}

return

tmp;

}

You can continue with the moveToward method in CatSprite.cpp. After the moveToward method, add the following code:

bool

pathFound = false;

_spOpenSteps.clear();

_spClosedSteps.clear();

//

First, add Cat's block coordinates to the open list

this

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

do

{

//

Get the smallest F value step

// Because it is an ordered list, the first step is always the smallest F value

ShortestPathStep *currentStep =

_spOpenSteps .at(0);

//

Add the current step to the closed list

_spClosedSteps.pushBack(currentStep);

/ /

Remove it from the open list

//

It should be noted that if you want to remove it from the open list first, you should be careful Object's memory

_spOpenSteps.erase(0);

//

If the current step is the coordinates of the target block, then it is completed

if (currentStep-gt; getPosition() ==

toTileCoord)

{

pathFound = true ;

ShortestPathStep * tmpStep =

currentStep;

CCLOG( "PATH FOUND:" );

do

{

CCLOG( "s" ,

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

tmpStep = tmpStep-gt; getParent(); //

Backward

} while (tmpStep); //

Until there is no previous step

_spOpenSteps.clear();

_spClosedSteps .clear();

break

}

//Get the coordinates of adjacent blocks of the current step

PointArray *adjSteps =

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

for

(ssize_t i = 0; i lt; adjSteps-gt; count (); i)

{

ShortestPathStep *step

=

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

//

Check whether the step is already in the closed list

if ( this -gt; getStepIndex(_spClosedSteps, step) !=

p>

-1)

{

continue;

}

// Calculate the time from the current step to this step Cost

int moveCost = this

-gt; costToMoveFromStepToAdjacentStep(currentStep, step);

//

Check whether this step has been In the open list

ssize_t index

= this -gt;getStepIndex(_spOpenSteps,

step);

//It is not in the open list, add it

if (index == -1)

{

//

Set the current step as the previous step

step-gt; setParent(currentStep);

//The G value is equal to the G value of the previous step

The cost from the previous step to here

step-gt; setGScore(currentStep-gt; getGScore() moveCost) ;

//

The H value is the estimated movement amount from this step to the target block coordinates

step-gt; setHScore( this

-gt;computeHScoreFromCoordToCoord(step-gt;getPosition(), toTileCoord));

//

Add to open list in order

this -gt;insertInOpenSteps(step);

}

else

{

//

Get the old step, its value has been calculated

step = _spOpenSteps.at(index);

//Check whether the G value is lower than the value from the current step to this step

if

((currentStep-gt; getGScore() moveCost) lt; step-gt; getGScore())

{

//

The G value is equal to the cost of the G value from the previous step to here

step-gt; setGScore(currentStep-gt; getGScore()

moveCost );

// Because the G value changes, the F value will also change accordingly

// So in order to keep the open list in order, you need to remove this step and press it again Sequential insertion

//

Before removing, you need to keep the reference

step-gt; retain();

/ /

Now you can safely remove without worrying about being released

_spOpenSteps.erase(index);

// Re-insert in order

this

-gt;insertInOpenSteps(step);

//

It can be released now because the open list should hold it

step-gt; release();

}

}

}

} while

(_spOpenSteps.size() gt; 0);

if

(!pathFound)

{

SimpleAudioEngine:: getInstance()-gt; playEffect(

"hitWall.wav" );

}

Add the following method:

ssize_t CatSprite ::getStepIndex( const

coco

s2d::Vector & steps, const CatSprite::ShortestPathStep *step)

{

for

(ssize_t i = 0; i lt; steps. size(); i)

{

if

(steps.at(i)-gt; isEqual(step))

{

return i;

}

}

return

-1;

}