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
|
/* Copyright (C) 2011 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. 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, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. 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 0 A.D. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef INCLUDED_ICMPPATHFINDER
#define INCLUDED_ICMPPATHFINDER
#include "simulation2/system/Interface.h"
#include "simulation2/helpers/Position.h"
#include "maths/FixedVector2D.h"
#include <map>
#include <vector>
class IObstructionTestFilter;
template<typename T> class Grid;
/**
* Pathfinder algorithms.
*
* There are two different modes: a tile-based pathfinder that works over long distances and
* accounts for terrain costs but ignore units, and a 'short' vertex-based pathfinder that
* provides precise paths and avoids other units.
*
* Both use the same concept of a Goal: either a point, circle or square.
* (If the starting point is inside the goal shape then the path will move outwards
* to reach the shape's outline.)
*
* The output is a list of waypoints.
*/
class ICmpPathfinder : public IComponent
{
public:
typedef u16 pass_class_t;
typedef u8 cost_class_t;
struct Goal
{
enum Type {
POINT,
CIRCLE,
SQUARE
} type;
entity_pos_t x, z; // position of center
CFixedVector2D u, v; // if SQUARE, then orthogonal unit axes
entity_pos_t hw, hh; // if SQUARE, then half width & height; if CIRCLE, then hw is radius
};
struct Waypoint
{
entity_pos_t x, z;
};
/**
* Returned path.
* Waypoints are in *reverse* order (the earliest is at the back of the list)
*/
struct Path
{
std::vector<Waypoint> m_Waypoints;
};
/**
* Get the list of all known passability classes.
*/
virtual std::map<std::string, pass_class_t> GetPassabilityClasses() = 0;
/**
* Get the tag for a given passability class name.
* Logs an error and returns something acceptable if the name is unrecognised.
*/
virtual pass_class_t GetPassabilityClass(const std::string& name) = 0;
/**
* Get the tag for a given movement cost class name.
* Logs an error and returns something acceptable if the name is unrecognised.
*/
virtual cost_class_t GetCostClass(const std::string& name) = 0;
virtual const Grid<u16>& GetPassabilityGrid() = 0;
/**
* Compute a tile-based path from the given point to the goal, and return the set of waypoints.
* The waypoints correspond to the centers of horizontally/vertically adjacent tiles
* along the path.
*/
virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, Path& ret) = 0;
/**
* Asynchronous version of ComputePath.
* The result will be sent as CMessagePathResult to 'notify'.
* Returns a unique non-zero number, which will match the 'ticket' in the result,
* so callers can recognise each individual request they make.
*/
virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, entity_id_t notify) = 0;
/**
* If the debug overlay is enabled, render the path that will computed by ComputePath.
*/
virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass) = 0;
/**
* Compute a precise path from the given point to the goal, and return the set of waypoints.
* The path is based on the full set of obstructions that pass the filter, such that
* a unit of radius 'r' will be able to follow the path with no collisions.
* The path is restricted to a box of radius 'range' from the starting point.
*/
virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, pass_class_t passClass, Path& ret) = 0;
/**
* Asynchronous version of ComputeShortPath (using ControlGroupObstructionFilter).
* The result will be sent as CMessagePathResult to 'notify'.
* Returns a unique non-zero number, which will match the 'ticket' in the result,
* so callers can recognise each individual request they make.
*/
virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t group, entity_id_t notify) = 0;
/**
* Find the speed factor (typically around 1.0) for a unit of the given cost class
* at the given position.
*/
virtual fixed GetMovementSpeed(entity_pos_t x0, entity_pos_t z0, cost_class_t costClass) = 0;
/**
* Returns the coordinates of the point on the goal that is closest to pos in a straight line.
*/
virtual CFixedVector2D GetNearestPointOnGoal(CFixedVector2D pos, const Goal& goal) = 0;
/**
* Check whether the given movement line is valid and doesn't hit any obstructions
* or impassable terrain.
* Returns true if the movement is okay.
*/
virtual bool CheckMovement(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, pass_class_t passClass) = 0;
/**
* Check whether a unit placed here is valid and doesn't hit any obstructions
* or impassable terrain.
* Returns true if the placement is okay.
*/
virtual bool CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass) = 0;
/**
* Check whether a building placed here is valid and doesn't hit any obstructions
* or impassable terrain.
* Returns true if the placement is okay.
*/
virtual bool CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass) = 0;
/**
* Toggle the storage and rendering of debug info.
*/
virtual void SetDebugOverlay(bool enabled) = 0;
/**
* Finish computing asynchronous path requests and send the CMessagePathResult messages.
*/
virtual void FinishAsyncRequests() = 0;
/**
* Process moves during the same turn they were created in to improve responsiveness.
*/
virtual void ProcessSameTurnMoves() = 0;
DECLARE_INTERFACE_TYPE(Pathfinder)
};
#endif // INCLUDED_ICMPPATHFINDER
|
