pathfind.h

Go to the documentation of this file.

/*
* pathfind.h
*
* Copyright (C) 2005 Atomic Blue (info@planeshift.it, http://www.atomicblue.org)
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation (version 2
* of the License).
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/

#ifndef ___PATHFIND_HEADER___
#define ___PATHFIND_HEADER___

#ifdef USE_WALKPOLY

//=============================================================================
// Crystal Space Includes
//=============================================================================
#include <csgeom/vector3.h>
#include <csgeom/box.h>
#include <csutil/hash.h>
#include <iutil/objreg.h>
#include <csutil/array.h>
#include <csutil/csstring.h>
#include <csutil/list.h>

class psANode;
class psWalkPoly;
class psWalkPolyMap;
class psAMap;
struct iVFS;
struct iSector;
struct iCollection;
struct iEngine;
struct iDocumentNode;

/***************************************************************************/
class psPFMap
{
public:
    csString name;
    iCollection* region;
    psWalkPolyMap* wpMap;
    psAMap* aMap;
};

/***************************************************************************/
class psPFMaps
{
public:
    psPFMaps(iObjectRegistry* objReg);
    psPFMap* GetRegionBySector(const csString &sectorName);
    psPFMap* GetRegionBySector(iSector* sector);
    psPFMap* FindRegionByName(const csString &regionName);

protected:
    iCollection* GetCSRegionOfSector(const csString &sectorName);

    csList<psPFMap*> regions;

    csHash<psPFMap*, csString> regionMap;

    iObjectRegistry* objReg;
    csRef<iEngine> engine;
};

/***************************************************************************/
class psAEdge
{
public:
    psAEdge(psANode* neighbour, float cost);
    psANode* neighbour;
    float cost;    
};

/* Empty subclass that unites psACluster and psAHierarchyNode
class psAHierarchyNode
{
};*/

/*************************************************************/
class psACluster
{
public:
    bool Contains(psANode* node);
    bool AddNode(psANode* node);
    void DeleteNode(psANode* node);

    void GrowClusterFrom(psANode* start, int level, csList <psANode*> &unassigned);

protected:

    int CalcFreeBorderSize(int level);

    csList <psANode*> parts;
    csList <psANode*> exits;
};

/*******************************************************************************/
enum psAState {AState_open, AState_closed, AState_unknown};


/************************************************************************/
class psANode
{
public:
    psANode();
    ~psANode();
    psANode(const csVector3 &point);
    psANode(const csVector3 &point, iSector* sector);

    void EnsureNodeIsInited(int currARunNum);

    void SetBestPrev(psANode* bestPrev, float cost);
    void CalcHeur(psANode* goal);
    void AddEdge(psANode* neighbour, float cost, int level, bool bidirectional=true);
    void DeleteEdges(psANode* neighbour);

    void ConnectToPoly(psWalkPoly* poly, bool bidirectional);

    bool ShouldBePruned(psAMap &map);

    void SaveToString(csString &str);

    //wpMap can be NULL
    void LoadBasicsFromXML(iDocumentNode* node, psWalkPolyMap* wpMap, iEngine* engine);
    void LoadEdgesFromXML(iDocumentNode* node, psAMap &map);

    void DumpJS();

    psWalkPoly* GetSomePoly();

    //works on 0th level only !
    void DeleteConnectionsFromNeighbours();
    void RestoreConnectionsFromNeighbours();

    //on 0th level
    float GetEdgeCost(psANode* neighbour);

    csVector3 point;
    iSector* sector;
    csArray<csArray<psAEdge> > edges;
    psACluster* cluster;

    int id;
    psWalkPoly* poly1, * poly2;
    static int nextID;

    /* The following variables are temporary A* state valid for one A* run only */
    int ARunNum;          
    psAState state;
    psANode* prevInOpen, * nextInOpen;   
    psANode* bestPrev;
    float bestCost;
    float heur;
    float total;
};

class psAPath
{
public:
    psAPath();
    psAPath(psPFMaps* regions);

    void SetMaps(psPFMaps* maps);

    void AddNodeToFront(psANode* node);

    // resets
    void SetDest(const csVector3 &dest);
    csVector3 GetDest()
    {
        return dest;
    }

    void CalcLocalDest(const csVector3 &currPoint, iSector* currSector, csVector3 &localDest);

    void Dump();
    void ResetNodes();

    float CalcCost();

protected:

    csList<psANode*>::Iterator FindDirectNode(const csVector3 &currPoint);
    void InsertSubpath(psAPath &subpath);
    csString GetRegionNameOfSector(const csString &sectorName);
    psANode* GetNthNode(int n);
    void RandomizeFirst(const csVector3 &currPoint);

    bool CalcLocalDestFromLocalPath(const csVector3 &currPoint, csVector3 &localDest);

    psANode* FindNearbyANode(const csVector3 &pos, iSector* sector);

    csVector3 dest;
    csList<psANode*> nodes;
    psPFMaps* maps;
};

class psAMap
{
public:
    psAMap(iObjectRegistry* objReg);
    psAMap();

    void SetObjReg(iObjectRegistry* objReg)
    {
        this->objReg=objReg;
    }
    void AddNode(psANode* node);

    void PruneSuperfluous();

    void BuildHierarchy();

    bool RunA(psANode* start, psANode* goal, int level, int maxExpands, psAPath &path);

    void DumpJS();

    bool LoadFromString(const csString &str, psWalkPolyMap* wpMap);
    bool LoadFromFile(const csString &path, psWalkPolyMap* wpMap);
    void SaveToString(csString &str);
    bool SaveToFile(const csString &path);

    psANode* FindNode(int id);

protected:
    csList <psANode*> nodes;
    csList <psACluster*> clusters;
    iObjectRegistry* objReg;
    csRef<iVFS> vfs;
};

#endif

#endif