Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #ifndef __PolyVox_AStarPathfinder_H__
00025 #define __PolyVox_AStarPathfinder_H__
00026
00027 #include "PolyVoxImpl/AStarPathfinderImpl.h"
00028 #include "PolyVoxImpl/TypeDef.h"
00029
00030 #include "PolyVoxCore/Array.h"
00031
00032 #include <list>
00033 #include <stdexcept>
00034
00035 namespace PolyVox
00036 {
00037 const float sqrt_1 = 1.0f;
00038 const float sqrt_2 = 1.4143f;
00039 const float sqrt_3 = 1.7321f;
00040
00041 extern const POLYVOX_API Vector3DInt32 arrayPathfinderFaces[6];
00042 extern const POLYVOX_API Vector3DInt32 arrayPathfinderEdges[12];
00043 extern const POLYVOX_API Vector3DInt32 arrayPathfinderCorners[8];
00044
00047 template< template<typename> class VolumeType, typename VoxelType>
00048 bool aStarDefaultVoxelValidator(const VolumeType<VoxelType>* volData, const Vector3DInt32& v3dPos);
00049
00061 template< template<typename> class VolumeType, typename VoxelType>
00062 struct AStarPathfinderParams
00063 {
00064 public:
00065 AStarPathfinderParams
00066 (
00067 VolumeType<VoxelType>* volData,
00068 const Vector3DInt32& v3dStart,
00069 const Vector3DInt32& v3dEnd,
00070 std::list<Vector3DInt32>* listResult,
00071 float fHBias = 1.0,
00072 uint32_t uMaxNoOfNodes = 10000,
00073 Connectivity connectivity = TwentySixConnected,
00074 polyvox_function<bool (const VolumeType<VoxelType>*, const Vector3DInt32&)> funcIsVoxelValidForPath = &aStarDefaultVoxelValidator<VolumeType, VoxelType>,
00075 polyvox_function<void (float)> funcProgressCallback = 0
00076 )
00077 :volume(volData)
00078 ,start(v3dStart)
00079 ,end(v3dEnd)
00080 ,connectivity(connectivity)
00081 ,hBias(fHBias)
00082 ,result(listResult)
00083 ,maxNumberOfNodes(uMaxNoOfNodes)
00084 ,isVoxelValidForPath(funcIsVoxelValidForPath)
00085 ,progressCallback(funcProgressCallback)
00086 {
00087 }
00088
00090 VolumeType<VoxelType>* volume;
00091
00093 Vector3DInt32 start;
00094
00096 Vector3DInt32 end;
00097
00100 std::list<Vector3DInt32>* result;
00101
00105 Connectivity connectivity;
00106
00115 float hBias;
00116
00121 uint32_t maxNumberOfNodes;
00122
00129 polyvox_function<bool (const VolumeType<VoxelType>*, const Vector3DInt32&)> isVoxelValidForPath;
00130
00136 polyvox_function<void (float)> progressCallback;
00137 };
00138
00163 template< template<typename> class VolumeType, typename VoxelType>
00164 class AStarPathfinder
00165 {
00166 public:
00167 AStarPathfinder(const AStarPathfinderParams<VolumeType, VoxelType>& params);
00168
00169 void execute();
00170
00171 private:
00172 void processNeighbour(const Vector3DInt32& neighbourPos, float neighbourGVal);
00173
00174 float SixConnectedCost(const Vector3DInt32& a, const Vector3DInt32& b);
00175 float EighteenConnectedCost(const Vector3DInt32& a, const Vector3DInt32& b);
00176 float TwentySixConnectedCost(const Vector3DInt32& a, const Vector3DInt32& b);
00177 float computeH(const Vector3DInt32& a, const Vector3DInt32& b);
00178
00179
00180 AllNodesContainer allNodes;
00181 OpenNodesContainer openNodes;
00182 ClosedNodesContainer closedNodes;
00183
00184
00185 AllNodesContainer::iterator current;
00186
00187 float m_fProgress;
00188
00189 AStarPathfinderParams<VolumeType, VoxelType> m_params;
00190 };
00191 }
00192
00193 #include "PolyVoxCore/AStarPathfinder.inl"
00194
00195 #endif //__PolyVox_AStarPathfinder_H__