1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
/* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
#ifndef PATHESTIMATOR_H
#define PATHESTIMATOR_H
#include <string>
#include <list>
#include <queue>
#include "IPath.h"
#include "PathConstants.h"
#include "PathDataTypes.h"
#include "System/float3.h"
#include <boost/thread/thread.hpp>
#include <boost/detail/atomic_count.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/barrier.hpp>
#include <boost/cstdint.hpp>
struct MoveData;
class CPathFinder;
class CPathEstimatorDef;
class CPathFinderDef;
class CPathCache;
class CPathEstimator {
public:
/**
* Creates a new estimator based on a couple of parameters
* @param pathFinder
* The pathfinder to be used for exact cost-calculation of vertices.
*
* @param BLOCK_SIZE
* The resolution of the estimator, given in mapsquares.
*
* @param cacheFileName
* Name of the file on disk where pre-calculated data is stored.
* The name given are added to the end of the filename, after the
* name of the corresponding map.
* Ex. PE-name "pe" + Mapname "Desert" => "Desert.pe"
*/
CPathEstimator(CPathFinder* pathFinder, unsigned int BLOCK_SIZE, const std::string& cacheFileName, const std::string& map);
~CPathEstimator();
#if !defined(USE_MMGR)
void* operator new(size_t size);
void operator delete(void* p, size_t size);
#endif
/**
* Returns an aproximate, low-resolution path from the starting location to
* the goal defined in CPathEstimatorDef, whenever any such are available.
* If no complete paths are found, then a path leading as "close" as
* possible to the goal is returned instead, together with
* SearchResult::OutOfRange.
* Only if no position closer to the goal than the starting location itself
* could be found, no path and SearchResult::CantGetCloser is returned.
* @param moveData
* Defining the footprint of the unit to use the path.
*
* @param start
* The starting location of the search.
*
* @param peDef
* Object defining the goal of the search.
* Could also be used to add constraints to the search.
*
* @param path
* If a path could be found, it's generated and put into this structure.
*
* @param maxSearchedBlocks
* The maximum number of nodes/blocks the search is allowed to analyze.
* This restriction could be used in cases where CPU-consumption is
* critical.
*/
IPath::SearchResult GetPath(
const MoveData& moveData,
float3 start,
const CPathFinderDef& peDef,
IPath::Path& path,
unsigned int maxSearchedBlocks,
bool synced = true
);
/**
* This is called whenever the ground structure of the map changes
* (for example on explosions and new buildings).
* The affected rectangular area is defined by (x1, z1)-(x2, z2).
* The estimator itself will decided if an update of the area is needed.
*/
void MapChanged(unsigned int x1, unsigned int z1, unsigned int x2, unsigned int z2);
/**
* called every frame
*/
void Update();
/**
* Returns a checksum that can be used to check if every player has the same
* path data.
*/
boost::uint32_t GetPathChecksum() const { return pathChecksum; }
unsigned int GetBlockSize() const { return BLOCK_SIZE; }
unsigned int GetNumBlocksX() const { return nbrOfBlocksX; }
unsigned int GetNumBlocksZ() const { return nbrOfBlocksZ; }
PathNodeStateBuffer& GetNodeStateBuffer() { return blockStates; }
private:
void InitEstimator(const std::string& cacheFileName, const std::string& map);
void InitVertices();
void InitBlocks();
void CalcOffsetsAndPathCosts(int thread);
void CalculateBlockOffsets(int, int);
void EstimatePathCosts(int, int);
const unsigned int BLOCK_SIZE;
const unsigned int BLOCK_PIXEL_SIZE;
const unsigned int BLOCKS_TO_UPDATE;
struct SingleBlock {
int2 block;
const MoveData* moveData;
};
void FindOffset(const MoveData&, int, int);
void CalculateVertices(const MoveData&, int, int, int thread = 0);
void CalculateVertex(const MoveData&, int, int, unsigned int, int thread = 0);
IPath::SearchResult InitSearch(const MoveData&, const CPathFinderDef&, bool);
IPath::SearchResult DoSearch(const MoveData&, const CPathFinderDef&, bool);
void TestBlock(const MoveData&, const CPathFinderDef&, PathNode&, unsigned int, bool);
void FinishSearch(const MoveData& moveData, IPath::Path& path);
void ResetSearch();
bool ReadFile(const std::string& cacheFileName, const std::string& map);
void WriteFile(const std::string& cacheFileName, const std::string& map);
unsigned int Hash() const;
/// Number of blocks on the X axis of the map.
int nbrOfBlocksX;
/// Number of blocks on the Z axis of the map.
int nbrOfBlocksZ;
PathNodeBuffer openBlockBuffer;
PathNodeStateBuffer blockStates;
/// The priority-queue used to select next block to be searched.
PathPriorityQueue openBlocks;
std::vector<float> vertices;
/// List of blocks changed in last search.
std::list<int> dirtyBlocks;
/// Blocks that may need an update due to map changes.
std::list<SingleBlock> needUpdate;
static const int PATH_DIRECTIONS = 8;
static const int PATH_DIRECTION_VERTICES = PATH_DIRECTIONS / 2;
int2 directionVector[PATH_DIRECTIONS];
int directionVertex[PATH_DIRECTIONS];
float3 start;
int2 startBlock;
int2 goalBlock;
int startBlocknr;
float goalHeuristic;
int2 goalSqrOffset;
unsigned int maxBlocksToBeSearched;
unsigned int testedBlocks;
float maxNodeCost;
std::vector<CPathFinder*> pathFinders;
std::vector<boost::thread*> threads;
CPathFinder* pathFinder;
CPathCache* pathCache;
/// currently crc from the zip
boost::uint32_t pathChecksum;
boost::mutex loadMsgMutex;
boost::barrier* pathBarrier;
boost::detail::atomic_count offsetBlockNum;
boost::detail::atomic_count costBlockNum;
int nextOffsetMessage;
int nextCostMessage;
};
#endif
|
