1 #pragma once
2 #ifndef CATA_SRC_LINE_H
3 #define CATA_SRC_LINE_H
4
5 #include <algorithm>
6 #include <cmath>
7 #include <functional>
8 #include <iosfwd>
9 #include <vector>
10
11 #include "point.h"
12 #include "units_fwd.h"
13
14 extern bool trigdist;
15
16 /**
17 * Calculate base of an isosceles triangle
18 * @param distance one of the equal lengths
19 * @param vertex the unequal angle
20 * @returns base in equivalent units to distance
21 */
22 double iso_tangent( double distance, const units::angle &vertex );
23
24 //! This compile-time usable function combines the sign of each (x, y, z) component into a single integer
25 //! to allow simple runtime and compile-time mapping of (x, y, z) tuples to @ref direction enumerators.
26 //! Specifically, (0, -, +) => (0, 1, 2); a base-3 number.
27 //! This only works correctly for inputs between -1,-1,-1 and 1,1,1.
28 //! For numbers outside that range, use make_xyz().
make_xyz_unit(const tripoint & p)29 inline constexpr unsigned make_xyz_unit( const tripoint &p ) noexcept
30 {
31 return ( ( p.x > 0 ) ? 2u : ( p.x < 0 ) ? 1u : 0u ) * 1u +
32 ( ( p.y > 0 ) ? 2u : ( p.y < 0 ) ? 1u : 0u ) * 3u +
33 ( ( p.z > 0 ) ? 2u : ( p.z < 0 ) ? 1u : 0u ) * 9u;
34 }
35
36 // This more general version of this function gives correct values for larger inputs.
37 unsigned make_xyz( const tripoint & );
38
39 enum class direction : unsigned {
40 ABOVENORTHWEST = make_xyz_unit( tripoint_above + tripoint_north_west ),
41 NORTHWEST = make_xyz_unit( tripoint_north_west ),
42 BELOWNORTHWEST = make_xyz_unit( tripoint_below + tripoint_north_west ),
43 ABOVENORTH = make_xyz_unit( tripoint_above + tripoint_north ),
44 NORTH = make_xyz_unit( tripoint_north ),
45 BELOWNORTH = make_xyz_unit( tripoint_below + tripoint_north ),
46 ABOVENORTHEAST = make_xyz_unit( tripoint_above + tripoint_north_east ),
47 NORTHEAST = make_xyz_unit( tripoint_north_east ),
48 BELOWNORTHEAST = make_xyz_unit( tripoint_below + tripoint_north_east ),
49
50 ABOVEWEST = make_xyz_unit( tripoint_above + tripoint_west ),
51 WEST = make_xyz_unit( tripoint_west ),
52 BELOWWEST = make_xyz_unit( tripoint_below + tripoint_west ),
53 ABOVECENTER = make_xyz_unit( tripoint_above ),
54 CENTER = make_xyz_unit( tripoint_zero ),
55 BELOWCENTER = make_xyz_unit( tripoint_below ),
56 ABOVEEAST = make_xyz_unit( tripoint_above + tripoint_east ),
57 EAST = make_xyz_unit( tripoint_east ),
58 BELOWEAST = make_xyz_unit( tripoint_below + tripoint_east ),
59
60 ABOVESOUTHWEST = make_xyz_unit( tripoint_above + tripoint_south_west ),
61 SOUTHWEST = make_xyz_unit( tripoint_south_west ),
62 BELOWSOUTHWEST = make_xyz_unit( tripoint_below + tripoint_south_west ),
63 ABOVESOUTH = make_xyz_unit( tripoint_above + tripoint_south ),
64 SOUTH = make_xyz_unit( tripoint_south ),
65 BELOWSOUTH = make_xyz_unit( tripoint_below + tripoint_south ),
66 ABOVESOUTHEAST = make_xyz_unit( tripoint_above + tripoint_south_east ),
67 SOUTHEAST = make_xyz_unit( tripoint_south_east ),
68 BELOWSOUTHEAST = make_xyz_unit( tripoint_below + tripoint_south_east ),
69 };
70
71 template< class T >
72 constexpr inline direction operator%( const direction &lhs, const T &rhs )
73 {
74 return static_cast<direction>( static_cast<T>( lhs ) % rhs );
75 }
76
77 template< class T >
78 constexpr inline T operator+( const direction &lhs, const T &rhs )
79 {
80 return static_cast<T>( lhs ) + rhs;
81 }
82
83 template< class T >
84 constexpr inline bool operator==( const direction &lhs, const T &rhs )
85 {
86 return static_cast<T>( lhs ) == rhs;
87 }
88
89 template< class T >
90 constexpr inline bool operator==( const T &lhs, const direction &rhs )
91 {
92 return operator==( rhs, lhs );
93 }
94
95 template< class T >
96 constexpr inline bool operator!=( const T &lhs, const direction &rhs )
97 {
98 return !operator==( rhs, lhs );
99 }
100
101 template< class T >
102 constexpr inline bool operator!=( const direction &lhs, const T &rhs )
103 {
104 return !operator==( lhs, rhs );
105 }
106
107 direction direction_from( const point &p ) noexcept;
108 direction direction_from( const tripoint &p ) noexcept;
109 direction direction_from( const point &p1, const point &p2 ) noexcept;
110 direction direction_from( const tripoint &p, const tripoint &q );
111
112 point direction_XY( direction dir );
113 std::string direction_name( direction dir );
114 std::string direction_name_short( direction dir );
115
116 /* Get suffix describing vector from p to q (e.g. 1NW, 2SE) or empty string if p == q */
117 std::string direction_suffix( const tripoint &p, const tripoint &q );
118
119 /**
120 * The actual Bresenham algorithm in 2D and 3D, everything else should call these
121 * and pass in an interact functor to iterate across a line between two points.
122 */
123 void bresenham( const point &p1, const point &p2, int t,
124 const std::function<bool( const point & )> &interact );
125 void bresenham( const tripoint &loc1, const tripoint &loc2, int t, int t2,
126 const std::function<bool( const tripoint & )> &interact );
127
128 tripoint move_along_line( const tripoint &loc, const std::vector<tripoint> &line,
129 int distance );
130 // The "t" value decides WHICH Bresenham line is used.
131 std::vector<point> line_to( const point &p1, const point &p2, int t = 0 );
132 // t and t2 decide which Bresenham line is used.
133 std::vector<tripoint> line_to( const tripoint &loc1, const tripoint &loc2, int t = 0, int t2 = 0 );
134 // sqrt(dX^2 + dY^2)
135
trig_dist(const tripoint & loc1,const tripoint & loc2)136 inline float trig_dist( const tripoint &loc1, const tripoint &loc2 )
137 {
138 return std::sqrt( static_cast<double>( ( loc1.x - loc2.x ) * ( loc1.x - loc2.x ) ) +
139 ( ( loc1.y - loc2.y ) * ( loc1.y - loc2.y ) ) +
140 ( ( loc1.z - loc2.z ) * ( loc1.z - loc2.z ) ) );
141 }
trig_dist(const point & loc1,const point & loc2)142 inline float trig_dist( const point &loc1, const point &loc2 )
143 {
144 return trig_dist( tripoint( loc1, 0 ), tripoint( loc2, 0 ) );
145 }
146
147 // Roguelike distance; maximum of dX and dY
square_dist(const tripoint & loc1,const tripoint & loc2)148 inline int square_dist( const tripoint &loc1, const tripoint &loc2 )
149 {
150 const tripoint d = ( loc1 - loc2 ).abs();
151 return std::max( { d.x, d.y, d.z } );
152 }
square_dist(const point & loc1,const point & loc2)153 inline int square_dist( const point &loc1, const point &loc2 )
154 {
155 const point d = ( loc1 - loc2 ).abs();
156 return std::max( d.x, d.y );
157 }
158
159 // Choose between the above two according to the "circular distances" option
rl_dist(const tripoint & loc1,const tripoint & loc2)160 inline int rl_dist( const tripoint &loc1, const tripoint &loc2 )
161 {
162 if( trigdist ) {
163 return trig_dist( loc1, loc2 );
164 }
165 return square_dist( loc1, loc2 );
166 }
rl_dist(const point & a,const point & b)167 inline int rl_dist( const point &a, const point &b )
168 {
169 return rl_dist( tripoint( a, 0 ), tripoint( b, 0 ) );
170 }
171
172 /**
173 * Helper type for the return value of dist_fast().
174 *
175 * This lets us delay the sqrt() call of trigdist until the actual length is needed.
176 */
177 struct FastDistanceApproximation {
178 private:
179 int value;
180 public:
FastDistanceApproximationFastDistanceApproximation181 explicit inline FastDistanceApproximation( int value ) : value( value ) { }
182 template<typename T>
183 inline bool operator<=( const T &rhs ) const {
184 if( trigdist ) {
185 return value <= rhs * rhs;
186 }
187 return value <= rhs;
188 }
189 template<typename T>
190 inline bool operator>=( const T &rhs ) const {
191 if( trigdist ) {
192 return value >= rhs * rhs;
193 }
194 return value >= rhs;
195 }
196 inline explicit operator int() const {
197 if( trigdist ) {
198 return std::sqrt( value );
199 }
200 return value;
201 }
202 };
203
trig_dist_fast(const tripoint & loc1,const tripoint & loc2)204 inline FastDistanceApproximation trig_dist_fast( const tripoint &loc1, const tripoint &loc2 )
205 {
206 return FastDistanceApproximation(
207 ( loc1.x - loc2.x ) * ( loc1.x - loc2.x ) +
208 ( loc1.y - loc2.y ) * ( loc1.y - loc2.y ) +
209 ( loc1.z - loc2.z ) * ( loc1.z - loc2.z ) );
210 }
square_dist_fast(const tripoint & loc1,const tripoint & loc2)211 inline FastDistanceApproximation square_dist_fast( const tripoint &loc1, const tripoint &loc2 )
212 {
213 const tripoint d = ( loc1 - loc2 ).abs();
214 return FastDistanceApproximation( std::max( { d.x, d.y, d.z } ) );
215 }
rl_dist_fast(const tripoint & loc1,const tripoint & loc2)216 inline FastDistanceApproximation rl_dist_fast( const tripoint &loc1, const tripoint &loc2 )
217 {
218 if( trigdist ) {
219 return trig_dist_fast( loc1, loc2 );
220 }
221 return square_dist_fast( loc1, loc2 );
222 }
rl_dist_fast(const point & a,const point & b)223 inline FastDistanceApproximation rl_dist_fast( const point &a, const point &b )
224 {
225 return rl_dist_fast( tripoint( a, 0 ), tripoint( b, 0 ) );
226 }
227
228 float rl_dist_exact( const tripoint &loc1, const tripoint &loc2 );
229 // Sum of distance in both axes
230 int manhattan_dist( const point &loc1, const point &loc2 );
231
232 // get angle of direction represented by point
233 units::angle atan2( const point & );
234
235 // Get the magnitude of the slope ranging from 0.0 to 1.0
236 float get_normalized_angle( const point &start, const point &end );
237 std::vector<tripoint> continue_line( const std::vector<tripoint> &line, int distance );
238 std::vector<point> squares_in_direction( const point &p1, const point &p2 );
239 // Returns a vector of squares adjacent to @from that are closer to @to than @from is.
240 // Currently limited to the same z-level as @from.
241 std::vector<tripoint> squares_closer_to( const tripoint &from, const tripoint &to );
242 void calc_ray_end( units::angle, int range, const tripoint &p, tripoint &out );
243 /**
244 * Calculates the horizontal angle between the lines from (0,0,0) to @p a and
245 * the line from (0,0,0) to @p b.
246 * Returned value is in degree and in the range 0....360.
247 * Example: if @p a is (0,1) and @p b is (1,0), the result will 90 degree
248 * The function currently ignores the z component.
249 */
250 units::angle coord_to_angle( const tripoint &a, const tripoint &b );
251
252 // weird class for 2d vectors where dist is derived from rl_dist
253 struct rl_vec2d {
254 float x;
255 float y;
256
257 // vec2d(){}
xrl_vec2d258 explicit rl_vec2d( float x = 0, float y = 0 ) : x( x ), y( y ) {}
rl_vec2drl_vec2d259 explicit rl_vec2d( const point &p ) : x( p.x ), y( p.y ) {}
260
261 float magnitude() const;
262 rl_vec2d normalized() const;
263 rl_vec2d rotated( float angle ) const;
264 float dot_product( const rl_vec2d &v ) const;
265 bool is_null() const;
266
267 point as_point() const;
268
269 // scale.
270 rl_vec2d operator* ( float rhs ) const;
271 rl_vec2d operator/ ( float rhs ) const;
272 // subtract
273 rl_vec2d operator- ( const rl_vec2d &rhs ) const;
274 // unary negation
275 rl_vec2d operator- () const;
276 rl_vec2d operator+ ( const rl_vec2d &rhs ) const;
277 };
278
279 struct rl_vec3d {
280 float x;
281 float y;
282 float z;
283
xrl_vec3d284 explicit rl_vec3d( float x = 0, float y = 0, float z = 0 ) : x( x ), y( y ), z( z ) {}
rl_vec3drl_vec3d285 explicit rl_vec3d( const tripoint &p ) : x( p.x ), y( p.y ), z( p.z ) {}
286
287 float magnitude() const;
288 rl_vec3d normalized() const;
289 rl_vec3d rotated( float angle ) const;
290 float dot_product( const rl_vec3d &v ) const;
291 bool is_null() const;
292
293 tripoint as_point() const;
294
295 // scale.
296 rl_vec3d operator* ( float rhs ) const;
297 rl_vec3d operator/ ( float rhs ) const;
298 // subtract
299 rl_vec3d operator- ( const rl_vec3d &rhs ) const;
300 // unary negation
301 rl_vec3d operator- () const;
302 rl_vec3d operator+ ( const rl_vec3d &rhs ) const;
303 };
304
305 #endif // CATA_SRC_LINE_H
306