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;
}