walkpoly.h

Go to the documentation of this file.

/*
* walkpoly.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 ___WALKPOLY_HEADER___
#define ___WALKPOLY_HEADER___
#if USE_WALKPOLY
//=============================================================================
// Crystal Space Includes
//=============================================================================
#include <csgeom/vector3.h>
#include <csgeom/box.h>
#include <iutil/objreg.h>
#include <csutil/array.h>
#include <csutil/csstring.h>
#include <csutil/list.h>

//=============================================================================
// Local Includes
//=============================================================================
#include "pathfind.h"

class psNPCClient;

void Dump3(const char* name, const csVector3 &p);
void Dump(const char* name, const csBox3 &b);
void Dump(const char* name, const csVector3 &p);

float Calc2DDistance(const csVector3 &a, const csVector3 &b);
float AngleDiff(float a1, float a2);

class ps2DLine
{
public:
    float a, b, c;

    void Dump();
    void Calc(const csVector3 &p1, const csVector3 &p2);
    void CalcPerp(const csVector3 &begin, const csVector3 &end);
    float CalcDist(const csVector3 &point);
    float CalcRel(const csVector3 &point);
    void Copy(ps2DLine &dest);
};

class psWalkPoly;
class psMapWalker;

struct iSector;
class CelBase;
struct iDocumentNode;
struct iVFS;

/**************************************************************************
*   psSpatialIndex is a tree-style data structure.
*   Its purpose is fast search of the psWalkPoly that is under your feet
*   or close to you.
*   It recursively splits the space into pairs of rectangular subspaces.
*
*   Each subspace corresponds to one node of the tree.
*   Each node keeps list of psWalkPolys whose psWalkPoly::box
*   collides with the subspace of the node.
***************************************************************************/

class psSpatialIndexNode
{
    friend class psSpatialIndex;
public:
    psSpatialIndexNode();

    psSpatialIndexNode* FindNodeOfPoint(const csVector3 &p);

    void Add(psWalkPoly* poly);

    csBox3 &GetBBox()
    {
        return bbox;
    }

    csList<psWalkPoly*>* GetPolys()
    {
        return &polys;
    };

protected:

    int GetTreeLevel();

    void Split();

    void ChooseSplit();

    psSpatialIndexNode* child1, * child2;
    psSpatialIndexNode* parent;

    csBox3 bbox;        
    float splitValue;   
    char splitAxis;     
    csList<psWalkPoly*> polys; 
    int numPolys;              
};

class psSpatialIndex
{
public:

    psSpatialIndex();

    void Add(psWalkPoly* poly);

    void Rebuild();

    psSpatialIndexNode* FindNodeOfPoint(const csVector3 &p, psSpatialIndexNode* hint=NULL);

    //psSpatialIndexNode * FindNodeOfPoly(psWalkPoly * poly);

    psWalkPoly* FindPolyOfPoint(const csVector3 &p, psSpatialIndexNode* hint=NULL);

    psANode* FindNearbyANode(const csVector3 &pos);

protected:
    psSpatialIndexNode root;
};

class psSeed
{
public:
    psSeed();
    psSeed(csVector3 pos, iSector* sector, float quality);
    psSeed(csVector3 edgePos, csVector3 pos, iSector* sector, float quality);
    void SaveToString(csString &str);
    void LoadFromXML(iDocumentNode* node, iEngine* engine);
    bool CheckValidity(psMapWalker* walker);

    bool edgeSeed;
    float quality;
    csVector3 pos, edgePos;
    iSector* sector;
};

class psSeedSet
{
public:
    psSeedSet(iObjectRegistry* objReg);
    psSeed PickUpBestSeed();
    void AddSeed(const psSeed &seed);
    bool IsEmpty()
    {
        return seeds.IsEmpty();
    }

    bool LoadFromString(const csString &str);
    bool LoadFromFile(const csString &path);

    void SaveToString(csString &str);
    bool SaveToFile(const csString &path);

protected:
    iObjectRegistry* objReg;
    csList<psSeed> seeds;
};

/*****************************************************************
* The areas of map that are without major obstacles are denoted
* by set of polygons that cover these areas. This is used
* to precisely calculate very short paths. Other paths
* are calculated using A*, and later fine-tuned with this map.
******************************************************************/

class psWalkPolyCont
{
public:
    csVector3 begin, end;   
    psWalkPoly* poly;       
};

class psWalkPolyVert
{
public:
    csVector3 pos;
    ps2DLine line;      
    csArray<psWalkPolyCont> conts;
    csString info;      

    bool touching, stuck;
    bool followingEdge;

    float angle;

    psWalkPolyVert();
    psWalkPolyVert(const csVector3 &pos);

    psWalkPoly* FindCont(const csVector3 &point);

    void CalcLineTo(const csVector3 &point);
};

class psWalkPolyMap
{
    friend class psWalkPoly;
public:
    psWalkPolyMap(iObjectRegistry* objReg);
    psWalkPolyMap();

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

    void AddPoly(psWalkPoly*);

    bool CheckDirectPath(csVector3 start, csVector3 goal);

    void Generate(psNPCClient* npcclient, psSeedSet &seeds, iSector* sector);

    void CalcConts();

    csString DumpPolys();

    void BuildBasicAMap(psAMap &AMap);

    void LoadFromXML(iDocumentNode* node);
    bool LoadFromString(const csString &str);
    bool LoadFromFile(const csString &path);

    void SaveToString(csString &str);
    bool SaveToFile(const csString &path);

    psANode* FindNearbyANode(const csVector3 &pos);

    psWalkPoly* FindPoly(int id);

    void PrunePolys();

    void DeleteContsWith(psWalkPoly* poly);

protected:

    csList<psWalkPoly*> polys;
    psSpatialIndex index;

    csHash<psWalkPoly*> polyByID;

    iObjectRegistry* objReg;
    csRef<iVFS> vfs;
};

/********************************************************************
 * A convex polygon that denotes area without major obstacles .
 * It is not necessarily a real polygon, because its vertices
 * do not have to be on the same 3D plane (just "roughly").
 * The walkable area within the polygon borders is rarely flat, too.
 ********************************************************************/

class psWalkPoly
{
    friend class psWalkPolyMap;
public:
    psWalkPoly();
    ~psWalkPoly();

    void AddVert(const csVector3 &pos, int beforeIndex=-1);
    size_t GetNumVerts()
    {
        return verts.GetSize();
    }

    void AddNode(psANode* node);
    void DeleteNode(psANode* node);

    void SetSector(iSector* sector);


    bool MoveToNextPoly(const csVector3 &goal, csVector3 &point, psWalkPoly* &nextPoly);

    void AddSeeds(psMapWalker* walker, psSeedSet &seeds);

    bool CheckConvexity(int vertNum);

    void Clear();

    //ignores y
    void Cut(const csVector3 &cut1, const csVector3 &cut2);
    //ignores y
    void Intersect(const psWalkPoly &other);

    float EstimateY(const csVector3 &point);

    void Dump(const char* name);
    void DumpJS(const char* name);
    void DumpPureJS();
    void DumpPolyJS(const char* name);

    int Stretch(psMapWalker &walker, psWalkPolyMap &map, float stepSize);
    void GlueToNeighbours(psMapWalker &walker, psWalkPolyMap &map);

    float GetBoxSize();
    float GetArea();
    float GetTriangleArea(int vertNum);
    float GetLengthOfEdges();
    void GetShape(float &min, float &max);
    float GetNarrowness();

    void PruneUnboundVerts(psMapWalker &walker);
    void PruneInLineVerts();

    bool IsNearWalls(psMapWalker &walker, int vertNum);

    bool StretchVert(psMapWalker &walker, psWalkPolyMap &map, int vertNum, const csVector3 &newPos, float stepSize);

    void SetMini(psMapWalker &walker, const csVector3 &pos, int numVerts);

    void CalcBox();
    csBox3 &GetBox()
    {
        return box;
    }

    bool IsInLine();

    void ClearInfo();

    bool CollidesWithPolys(psWalkPolyMap &map, csList<psWalkPoly*>* polys);

    void SaveToString(csString &str);
    void LoadFromXML(iDocumentNode* node, iEngine* engine);

    void CalcConts(psWalkPolyMap &map);

    void RecalcAllEdges();

    void ConnectNodeToPoly(psANode* node, bool bidirectional);

    bool TouchesPoly(psWalkPoly* poly);
    bool NeighboursTouchEachOther();

    psANode* GetFirstNode();

    int GetID()
    {
        return id;
    }
    iSector* GetSector()
    {
        return sector;
    }

    bool PointIsIn(const csVector3 &p, float maxRel=0);

    csVector3 GetClosestPoint(const csVector3 &point, float &angle);

    int GetNumConts();

    size_t GetNumNodes()
    {
        return nodes.GetSize();
    }

    bool ReachableFromNeighbours();

    psWalkPoly* GetNearNeighbour(const csVector3 &pos, float maxDist);

    void DeleteContsWith(psWalkPoly* poly);

    bool NeighbourSupsMe(psWalkPoly* neighbour);

    void MovePointInside(csVector3 &point, const csVector3 &goal);

protected:

    void RecalcEdges(int vertNum);

    int FindClosestEdge(const csVector3 pos);

    psWalkPoly* FindCont(const csVector3 &point, int edgeNum);

    bool MoveToBorder(const csVector3 &goal, csVector3 &point, int &edgeNum);


    void CalcEdges();


    int GetNeighbourIndex(int vertNum, int offset) const;

    bool HandleProblems(psMapWalker &walker, psWalkPolyMap &map, int vertNum, const csVector3 &oldPos);
    csVector3 GetClosestCollisionPoint(csList<psWalkPoly*> &collisions, ps2DLine &line);
    bool HandlePolyCollisions(psWalkPolyMap &map, int vertNum, const csVector3 &oldPos);

    int id;
    static int nextID;
    bool supl;

    csArray<psWalkPolyVert> verts;       
    iSector* sector;
    csBox3 box;       
    csArray<psANode*> nodes;
};

#endif

#endif