MapSearchAStar.h

/*----------------------------------------------------------------------
Pac-Man Evolution - Roberto Prieto
Copyright (C) 2018-2024 MegaStorm Systems
contact@megastormsystems.com - http://www.megastormsystems.com
 
This software is provided 'as-is', without any express or implied
warranty.  In no event will the authors be held liable for any damages
arising from the use of this software.
 
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
 
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
 
------------------------------------------------------------------------
 
MapSearch A* class
 
------------------------------------------------------------------------ */
 
#ifndef MAPSEARCHASTARPME_H
#define MAPSEARCHASTARPME_H
  
// Includes and forward definitions
#include "MemoryManager.h"
class GameField;
class MazeNode;
struct MazePoint;
using namespace CRM64Pro;
 
class MapSearchAStar : public CMemPME
{
public:
    explicit MapSearchAStar(GameField*);
    ~MapSearchAStar();
    
    enum eSearchState
    {
        SS_NOT_INITIALISED,
        SS_SEARCHING,
        SS_SUCCEEDED,
        SS_FAILED,
        SS_OUT_OF_MEMORY,
        SS_INVALID
    };
    eSearchState findPath(Sint32, Sint32, Sint32, Sint32, vector<MazePoint>&, Sint32);
 
private:
 
    // Internal methods
    float heuristic(MazeNode*);
    float cost(MazeNode*, Sint32, Sint32);    
    void AStarDoStep();
    bool addSuccessor(MazeNode *);
    bool getSuccessors(MazeNode *, MazeNode *);
    void cancelSearch();
    MazeNode* allocateNode();
    void freeNode(MazeNode *);
    void freeAllNodes();
    void freeUnusedNodes();
    void freeSolutionNodes();
    MazeNode* getSolutionStart();
    MazeNode* getSolutionNext();
    MazeNode* getSolutionEnd();
    MazeNode* getSolutionPrev();
    
    // Node vectors
    vector<MazeNode*> vOpenList; // Opened nodes list
    vector<MazeNode*> vClosedList; // Closed nodes list
    vector<MazeNode*> vSuccessors; // Successors list
 
    // Misc
    Sint32 iAStarSteps;
    eSearchState eSS;
    MazeNode* pNodeStart;
    MazeNode* pNodeGoal;
    MazeNode* pNodeCurrentSolution;
    Sint32 iMinimumAcceptableValue; // Minimum value to be considered as a valid node
    bool bCancelRequest;
 
    // Pointer to needed components
    GameField* pGameField;
 
    // Debugging
    MazeNode* getOpenListStart();
    MazeNode* getOpenListStart(float &, float &, float &);
    MazeNode* getOpenListNext();
    MazeNode* getOpenListNext(float &, float &, float &);
    MazeNode* getClosedListStart();
    MazeNode* getClosedListStart(float &, float &, float &);
    MazeNode* getClosedListNext();
    MazeNode* getClosedListNext(float &, float &, float &);
    vector<MazeNode*>::iterator iterDbgOpen;
    vector<MazeNode*>::iterator iterDbgClosed;
    Sint32 iAllocateNodeCount;
    Sint32 iFreeNodeCount;
};     
 
#endif