Some will be interested in knowing or seeing a shortcut search algorithm. Use this algorithm cost-effectively in games of the following strategy genres, PVP and other turn-based games. Also, finding a short path will be useful for navigating a route. Next, we’ll start creating the class, first you need to create the cell size ALIGNED = 1, its diagonal is equal 1.4 and cell size 82. In program code, it will look like this:

#define ALIGNED 1
#define DIAGONAL 1.4
#define GRID_SIZE 82

Create a class PNode – the cell class that will be created upon initialization of 82×82 size, totaling 6724 cells. The class includes the following: position x, y, index i, j, walkable – an integer cell status, for example 1 refers to water or 2 refers to an obstacle, select is a selected cell or not, I’m not going to paint other parameters like MovieClip can read my previous articles. Below is the PNode class code:

class [[cheerp::genericjs]] PNode
{
public:        
        PNode(int index, float _x, float _y, int _walkable, WebGLRenderingContext* _gl)
        {
        this->_index = index;
        this->_x = _x*25;
        this->_y = _y*25;
        this->_i = _x;
        this->_j = _y;
        this->_walkable = _walkable;
        this->_select = false;
        this->gl = _gl;
        this->_parentNode = NULL;
        char *name = new char[32];
        sprintf(name,"grid:%i",_index);
        if(_gl)
        {
        clipNode = new MovieClip(_gl,25,25);
        clipNode->setName(name);
        clipNode->setPos(this->_x,this->_y);
        clipNode->setColor(1,1,1);
        clipNode->setAlpha(0.45f);
        clipNode->set_timeupdate(true);
        clipNode->set_playing(true);
        clipNode->checkReady();
        }
        this->_walkable = 0;//Math.round(Math.random()*2);
        }
        MovieClip* getClipNode(){return clipNode;}
        void Render(Camera* cam){if(clipNode)clipNode->Render(false,cam);}
        int getIndex(){return _index;}
        float getF(){return _f;}
        void setF(float value){_f = value;}
        float getG(){return _g;}
        void setG(float value){_g = value;}
        float getH(){return _h;}
        void setH(float value){_h = value;}
        PNode* getParentNode(){return _parentNode;}
        void setParentNode(PNode* value)
        {
           if(value)
           {
           _parentNode = new PNode(0,0,0,0,0);
           *_parentNode = *value;
           }
        }
        int getWalkable(){return _walkable;}
        void setWalkable(int value){_walkable = value;}
        float getX(){return _x;}
        float getY(){return _y;}
        int getI(){return _i;}
        int getJ(){return _j;}
        void setSelect(bool value){_select = value;}
        bool getSelect(){return _select;}
        char* toString()
        {
        char* result = new char[64];
        sprintf(result,"%i %i",_i,_j);
        return result;
        }
        bool selectNode(float x, float y)
        {
        	return((x >= _x) && (x < (_x+25))) && ((y >= _y) && (y < (_y+25)));
        }
        void setColor(float r, float g, float b){if(clipNode)clipNode->setColor(r,g,b);}     
protected:

private:
        PNode *_parentNode;
        int _index;
        int _walkable;
        int _i, _j;
        float _f,_g,_h,_x,_y;
        float color[3];
        bool _select;
        MovieClip *clipNode;
        WebGLRenderingContext* gl;
};

MovieClip and WebGLRenderingContext optional parameters, however if you want to display the grid after seeing it on the screen and do some debugging you need to pass the parameter WebGLRenderingContext upon initialization PathFinder. The following class is presented below, a grid consisting of cells:

class [[cheerp::genericjs]] Grid
{
public:
       Grid(int w, int h, WebGLRenderingContext* _gl);
       PNode* getPosNode(float x, float y);
       PNode* getIndexNode(int index);
       PNode* getNode(int x, int y)
       {
       if((x >= 0) && (x <= _width-1) && (y >= 0) && (y <= _height-1))return &_nodes[x][y];
       return NULL;
       }
       int getWidth(){return _width;}
       int getHeight(){return _height;}
       PNode* selectNodes(float x, float y);
       void Clear(WebGLRenderingContext* _gl, vector<int> _gridArr);
       void Render(Camera *cam);
       void Update(float x, float y, bool unselect);
protected:

private:
        vector<vector<PNode>> _nodes;
        int _width,_height;
};

The following functions are available in the grid: initialization, retrieving a cell at the getPosNode position, retrieving a cell at the getIndexNode index, getNode – retrieving a cell at the i, j indices. This algorithm works faster than getPosNode, because this algorithm uses a double cycle to find the cell itself, which greatly complicates the process and delays it. Therefore, I recommend using getNode to search for a cell by position. Further, the functions of obtaining width and height, the function of selecting cells, that is, changing the color of the PNode cell, the function of cleaning the grid, drawing and updating the grid itself. Finally we got to the very “PathFinder” class which is presented below:

class [[cheerp::genericjs]] PathFinder 
{
public:
        void Init()
        {
        _closed.clear();
        _opened.clear();
        _path.clear();
        }
        float getDistance(PNode *one, PNode *two);
        float getLocalDistance(PNode *one, PNode *two);
        vector<PNode> getPath(PNode *_start, PNode *_end, Grid _grid);
        //vector<PNode*> pathReconstruct(PNode* lastNode);
protected:
        
private:
vector<PNode> _closed;
vector<PNode> _opened;
vector<PNode> _path;
};

In the class itself there are not many functions that we need. Let’s look at them:

1) Initialization
2) Determining the distance from one cell to another along the entire route
3) Determining the distance of neighboring cells
4) getPath – a route-laying function; the above-mentioned two functions are used in the getPath function to route a route.
5) pathReconstruct – this function was not used as needed.

After getPath is executed, the function returns a vector array of cells where the path itself is laid. Let’s look at the function itself by the code below:

vector<PNode> PathFinder::getPath(PNode *_start, PNode *_end, Grid _grid)
{
_closed.empty();
_opened.empty();
_path.empty();
_start->setG(0);
_start->setH(getDistance(_start, _end));
_start->setF(_start->getG() + _start->getH());
_start->setParentNode(NULL);
_opened.push_back((PNode)*_start);
while (_opened.size() > 0)
{
PNode currentNode = PNode(0,0,0,0,0);
currentNode = _opened[0];
_closed.push_back(_opened[0]);
for(int x = currentNode.getJ()-1; x <= currentNode.getJ()+1; x++)
    for(int y = currentNode.getI()-1; y <= currentNode.getI()+1; y++)
    {
    PNode *testedNode = new PNode(0,0,0,0,0);
    testedNode = _grid.getNode(x,y);
    if(!testedNode)continue;
    if(testedNode->getWalkable() != 0)continue;
    if(indexOf(_closed,testedNode) != -1)continue;
        if (indexOf(_opened,testedNode) == -1)
        {
        testedNode->setG(currentNode.getG() + getLocalDistance(&currentNode, testedNode));
        testedNode->setH(getDistance(&currentNode, testedNode));
        testedNode->setF(testedNode->getG() + testedNode->getH());
        testedNode->setParentNode(&currentNode);
        _opened.push_back((PNode)*testedNode);
        }
        else
        {
            float tempG = currentNode.getG() + getLocalDistance(&currentNode, testedNode);
            if (tempG < testedNode->getG()) 
            {
            testedNode->setG(tempG);
            testedNode->setF(testedNode->getG() + testedNode->getH());
            testedNode->setParentNode(&currentNode);
            }
        }
    }
    _opened.erase(_opened.begin());
    sort(_opened.begin(),_opened.end(),sortOpen);
    if((_opened.size() > 0) && (_opened[0].getIndex() == _end->getIndex()))
    {
    PNode* lastNode = &_opened[0];
       while(lastNode->getParentNode())
       {
       _path.push_back((PNode)*lastNode);
       lastNode = lastNode->getParentNode();
       }
       reverse(_path.begin(),_path.end());
       return _path;
    }
 }
return _path;
}

Initially, we clear _closed, _opened, and _path. Next, we set the parameters to _start and then add to _opened. Then we go through the loop while _opened the size of the array is greater than zero, we repeat the loop. In the loop, create currentNode, initialize, fill it with _opened, add to _closed and then do some checks on the loop and only then remove the index from the _opened vector array. Next, add to _path, reverse it and return it to the output.

On this I briefly talked about how the “PathFinder” is arranged. In the next lesson I will describe its use and I will definitely try to post links to open source components on GitHub.

Thank you!

K.games

By K.games

Leave a Reply

Your email address will not be published. Required fields are marked *

Secured By miniOrange