1 /*
2 Copyright © 2011-2012 Clint Bellanger
3 Copyright © 2012 Stefan Beller
4 Copyright © 2012-2016 Justin Jacobs
5
6 This file is part of FLARE.
7
8 FLARE is free software: you can redistribute it and/or modify it under the terms
9 of the GNU General Public License as published by the Free Software Foundation,
10 either version 3 of the License, or (at your option) any later version.
11
12 FLARE is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
14 PARTICULAR PURPOSE. See the GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License along with
17 FLARE. If not, see http://www.gnu.org/licenses/
18 */
19
20 /*
21 * MapCollision.h
22 * RPGEngine
23 *
24 * Handle collisions between objects and the map
25 */
26
27 #ifdef __EMSCRIPTEN__
28 // some of our movement code asserts fail on Emscripten builds
29 // since the game can still run with occasionally bugged movement, we can disable those asserts
30 #define NDEBUG
31 #endif
32
33 #include "AStarContainer.h"
34 #include "AStarNode.h"
35 #include "EngineSettings.h"
36 #include "MapCollision.h"
37 #include "SharedResources.h"
38
39 #include <cfloat>
40 #include <math.h>
41 #include <cassert>
42 #include <cstring>
43
44 // this value is used to determine the greatest possible position within a tile before transitioning to the next tile
45 // so if an entity has a position of (1-MIN_TILE_GAP, 0) and moves to the east, they will move to (1,0)
46 const float MapCollision::MIN_TILE_GAP = 0.001f;
47
MapCollision()48 MapCollision::MapCollision()
49 : map_size(Point())
50 {
51 colmap.resize(1);
52 colmap[0].resize(1);
53 }
54
setMap(const Map_Layer & _colmap,unsigned short w,unsigned short h)55 void MapCollision::setMap(const Map_Layer& _colmap, unsigned short w, unsigned short h) {
56 colmap.resize(w);
57 for (unsigned i=0; i<w; ++i) {
58 colmap[i].resize(h);
59 }
60 for (unsigned i=0; i<w; i++)
61 for (unsigned j=0; j<h; j++)
62 colmap[i][j] = _colmap[i][j];
63
64 map_size.x = w;
65 map_size.y = h;
66 }
67
sgn(float f)68 int sgn(float f) {
69 if (f > 0) return 1;
70 else if (f < 0) return -1;
71 else return 0;
72 }
73
smallStep(float & x,float & y,float step_x,float step_y,int movement_type,int collide_type)74 bool MapCollision::smallStep(float &x, float &y, float step_x, float step_y, int movement_type, int collide_type) {
75 if (isValidPosition(x + step_x, y + step_y, movement_type, collide_type)) {
76 x += step_x;
77 y += step_y;
78 assert(isValidPosition(x,y,movement_type, collide_type));
79 return true;
80 }
81 else {
82 return false;
83 }
84 }
85
smallStepForcedSlideAlongGrid(float & x,float & y,float step_x,float step_y,int movement_type,int collide_type)86 bool MapCollision::smallStepForcedSlideAlongGrid(float &x, float &y, float step_x, float step_y, int movement_type, int collide_type) {
87 if (isValidPosition(x + step_x, y, movement_type, collide_type)) { // slide along wall
88 if (step_x == 0) return true;
89 x += step_x;
90 assert(isValidPosition(x,y,movement_type, collide_type));
91 }
92 else if (isValidPosition(x, y + step_y, movement_type, collide_type)) {
93 if (step_y == 0) return true;
94 y += step_y;
95 assert(isValidPosition(x,y,movement_type, collide_type));
96 }
97 else {
98 return false;
99 }
100 return true;
101 }
102
smallStepForcedSlide(float & x,float & y,float step_x,float step_y,int movement_type,int collide_type)103 bool MapCollision::smallStepForcedSlide(float &x, float &y, float step_x, float step_y, int movement_type, int collide_type) {
104 // is there a singular obstacle or corner we can step around?
105 // only works if we are moving straight
106 const float epsilon = 0.01f;
107 if (step_x != 0) {
108 assert(step_y == 0);
109 float dy = y - floorf(y);
110
111 if (isValidTile(int(x), int(y) + 1, movement_type, collide_type)
112 && isValidTile(int(x) + sgn(step_x), int(y) + 1, movement_type, collide_type)
113 && dy > 0.5) {
114 y += std::min(1 - dy + epsilon, float(fabs(step_x)));
115 }
116 else if (isValidTile(int(x), int(y) - 1, movement_type, collide_type)
117 && isValidTile(int(x) + sgn(step_x), int(y) - 1, movement_type, collide_type)
118 && dy < 0.5) {
119 y -= std::min(dy + epsilon, float(fabs(step_x)));
120 }
121 else {
122 return false;
123 }
124 assert(isValidPosition(x,y,movement_type, collide_type));
125 }
126 else if (step_y != 0) {
127 assert(step_x == 0);
128 float dx = x - floorf(x);
129
130 if (isValidTile(int(x) + 1, int(y), movement_type, collide_type)
131 && isValidTile(int(x) + 1, int(y) + sgn(step_y), movement_type, collide_type)
132 && dx > 0.5) {
133 x += std::min(1 - dx + epsilon, float(fabs(step_y)));
134 }
135 else if (isValidTile(int(x) - 1, int(y), movement_type, collide_type)
136 && isValidTile(int(x) - 1, int(y) + sgn(step_y), movement_type, collide_type)
137 && dx < 0.5) {
138 x -= std::min(dx + epsilon, float(fabs(step_y)));
139 }
140 else {
141 return false;
142 }
143 }
144 else {
145 assert(false);
146 }
147 return true;
148 }
149
150 /**
151 * Process movement for cardinal (90 degree) and ordinal (45 degree) directions
152 * If we encounter an obstacle at 90 degrees, stop.
153 * If we encounter an obstacle at 45 or 135 degrees, slide.
154 */
move(float & x,float & y,float _step_x,float _step_y,int movement_type,int collide_type)155 bool MapCollision::move(float &x, float &y, float _step_x, float _step_y, int movement_type, int collide_type) {
156 // when trying to slide against a bottom or right wall, step_x or step_y can become 0
157 // this causes diag to become false, making this function return false
158 // we try to catch such a scenario and return true early
159 bool force_slide = (_step_x != 0 && _step_y != 0);
160
161 while (_step_x != 0 || _step_y != 0) {
162
163 float step_x = 0;
164 if (_step_x > 0) {
165 // find next interesting value, which is either the whole step, or the transition to the next tile
166 step_x = std::min(ceilf(x) - x, _step_x);
167 // if we are standing on the edge of a tile (ceilf(x) - x == 0), we need to look one tile ahead
168 if (step_x <= MIN_TILE_GAP) step_x = std::min(1.f, _step_x);
169 }
170 else if (_step_x < 0) {
171 step_x = std::max(floorf(x) - x, _step_x);
172 if (step_x == 0) step_x = std::max(-1.f, _step_x);
173 }
174
175 float step_y = 0;
176 if (_step_y > 0) {
177 step_y = std::min(ceilf(y) - y, _step_y);
178 if (step_y <= MIN_TILE_GAP) step_y = std::min(1.f, _step_y);
179 }
180 else if (_step_y < 0) {
181 step_y = std::max(floorf(y) - y, _step_y);
182 if (step_y == 0) step_y = std::max(-1.f, _step_y);
183 }
184
185 _step_x -= step_x;
186 _step_y -= step_y;
187
188 if (!smallStep(x, y, step_x, step_y, movement_type, collide_type)) {
189 if (force_slide) {
190 if (!smallStepForcedSlideAlongGrid(x, y, step_x, step_y, movement_type, collide_type))
191 return false;
192 }
193 else {
194 if (!smallStepForcedSlide(x, y, step_x, step_y, movement_type, collide_type))
195 return false;
196 }
197 }
198 }
199 return true;
200 }
201
202 /**
203 * Determines whether the grid position is outside the map boundary
204 */
isTileOutsideMap(const int & tile_x,const int & tile_y) const205 bool MapCollision::isTileOutsideMap(const int& tile_x, const int& tile_y) const {
206 return (tile_x < 0 || tile_y < 0 || tile_x >= map_size.x || tile_y >= map_size.y);
207 }
208
isOutsideMap(const float & tile_x,const float & tile_y) const209 bool MapCollision::isOutsideMap(const float& tile_x, const float& tile_y) const {
210 return isTileOutsideMap(static_cast<int>(tile_x), static_cast<int>(tile_y));
211 }
212
213 /**
214 * A map space is empty if it contains no blocking type
215 * A position outside the map boundary is not empty
216 */
isEmpty(const float & x,const float & y) const217 bool MapCollision::isEmpty(const float& x, const float& y) const {
218 // map bounds check
219 const int tile_x = static_cast<int>(x);
220 const int tile_y = static_cast<int>(y);
221 if (isTileOutsideMap(tile_x, tile_y)) return false;
222
223 // collision type check
224 return (colmap[tile_x][tile_y] == BLOCKS_NONE || colmap[tile_x][tile_y] == MAP_ONLY || colmap[tile_x][tile_y] == MAP_ONLY_ALT);
225 }
226
227 /**
228 * A map space is a wall if it contains a wall blocking type (normal or hidden)
229 * A position outside the map boundary is a wall
230 */
isWall(const float & x,const float & y) const231 bool MapCollision::isWall(const float& x, const float& y) const {
232 // bounds check
233 const int tile_x = static_cast<int>(x);
234 const int tile_y = static_cast<int>(y);
235 if (isTileOutsideMap(tile_x, tile_y)) return true;
236
237 // collision type check
238 return (colmap[tile_x][tile_y] == BLOCKS_ALL || colmap[tile_x][tile_y] == BLOCKS_ALL_HIDDEN);
239 }
240
241 /**
242 * Is this a valid tile for an entity with this movement type?
243 */
isValidTile(const int & tile_x,const int & tile_y,int movement_type,int collide_type) const244 bool MapCollision::isValidTile(const int& tile_x, const int& tile_y, int movement_type, int collide_type) const {
245 // outside the map isn't valid
246 if (isTileOutsideMap(tile_x,tile_y)) return false;
247
248 if (collide_type == COLLIDE_NORMAL) {
249 if (colmap[tile_x][tile_y] == BLOCKS_ENEMIES)
250 return false;
251 if (colmap[tile_x][tile_y] == BLOCKS_ENTITIES)
252 return false;
253 }
254 else if (collide_type == COLLIDE_HERO) {
255 if (colmap[tile_x][tile_y] == BLOCKS_ENEMIES && !eset->misc.enable_ally_collision)
256 return true;
257 }
258
259 // intangible creatures can be everywhere
260 if (movement_type == MOVE_INTANGIBLE)
261 return true;
262
263 // flying creatures can't be in walls
264 if (movement_type == MOVE_FLYING) {
265 return (!(colmap[tile_x][tile_y] == BLOCKS_ALL || colmap[tile_x][tile_y] == BLOCKS_ALL_HIDDEN));
266 }
267
268 if (colmap[tile_x][tile_y] == MAP_ONLY || colmap[tile_x][tile_y] == MAP_ONLY_ALT)
269 return true;
270
271 // normal creatures can only be in empty spaces
272 return (colmap[tile_x][tile_y] == BLOCKS_NONE);
273 }
274
275 /**
276 * Is this a valid position for an entity with this movement type?
277 */
isValidPosition(const float & x,const float & y,int movement_type,int collide_type) const278 bool MapCollision::isValidPosition(const float& x, const float& y, int movement_type, int collide_type) const {
279 if (x < 0 || y < 0) return false;
280
281 return isValidTile(int(x), int(y), movement_type, collide_type);
282 }
283
284 /**
285 * Does not have the "slide" submovement that move() features
286 * Line can be arbitrary angles.
287 */
lineCheck(const float & x1,const float & y1,const float & x2,const float & y2,int check_type,int movement_type)288 bool MapCollision::lineCheck(const float& x1, const float& y1, const float& x2, const float& y2, int check_type, int movement_type) {
289 float x = x1;
290 float y = y1;
291 float dx = static_cast<float>(fabs(x2 - x1));
292 float dy = static_cast<float>(fabs(y2 - y1));
293 float step_x;
294 float step_y;
295 int steps = static_cast<int>(std::max(dx, dy));
296
297
298 if (dx > dy) {
299 step_x = 1;
300 step_y = dy / dx;
301 }
302 else {
303 step_y = 1;
304 step_x = dx / dy;
305 }
306 // fix signs
307 if (x1 > x2) step_x = -step_x;
308 if (y1 > y2) step_y = -step_y;
309
310
311 if (check_type == CHECK_SIGHT) {
312 for (int i=0; i<steps; i++) {
313 x += step_x;
314 y += step_y;
315 if (isWall(x, y))
316 return false;
317 }
318 }
319 else if (check_type == CHECK_MOVEMENT) {
320 for (int i=0; i<steps; i++) {
321 x += step_x;
322 y += step_y;
323 if (!isValidPosition(x, y, movement_type, COLLIDE_NORMAL))
324 return false;
325 }
326 }
327
328 return true;
329 }
330
lineOfSight(const float & x1,const float & y1,const float & x2,const float & y2)331 bool MapCollision::lineOfSight(const float& x1, const float& y1, const float& x2, const float& y2) {
332 return lineCheck(x1, y1, x2, y2, CHECK_SIGHT, MOVE_NORMAL);
333 }
334
lineOfMovement(const float & x1,const float & y1,const float & x2,const float & y2,int movement_type)335 bool MapCollision::lineOfMovement(const float& x1, const float& y1, const float& x2, const float& y2, int movement_type) {
336 if (isOutsideMap(x2, y2)) return false;
337
338 // intangible entities can always move
339 if (movement_type == MOVE_INTANGIBLE) return true;
340
341 // if the target is blocking, clear it temporarily
342 int tile_x = int(x2);
343 int tile_y = int(y2);
344 bool target_blocks = false;
345 int target_blocks_type = colmap[tile_x][tile_y];
346 if (colmap[tile_x][tile_y] == BLOCKS_ENTITIES || colmap[tile_x][tile_y] == BLOCKS_ENEMIES) {
347 target_blocks = true;
348 unblock(x2,y2);
349 }
350
351 bool has_movement = lineCheck(x1, y1, x2, y2, CHECK_MOVEMENT, movement_type);
352
353 if (target_blocks) block(x2,y2, target_blocks_type == BLOCKS_ENEMIES);
354 return has_movement;
355
356 }
357
358 /**
359 * Checks whether the entity in pos 1 is facing the point at pos 2
360 * based on a 180 degree field of vision
361 */
isFacing(const float & x1,const float & y1,char direction,const float & x2,const float & y2)362 bool MapCollision::isFacing(const float& x1, const float& y1, char direction, const float& x2, const float& y2) {
363
364 // 180 degree fov
365 switch (direction) {
366 case 2: //north west
367 return ((x2-x1) < ((-1 * y2)-(-1 * y1))) && (((-1 * x2)-(-1 * x1)) > (y2-y1));
368 case 3: //north
369 return y2 < y1;
370 case 4: //north east
371 return (((-1 * x2)-(-1 * x1)) < ((-1 * y2)-(-1 * y1))) && ((x2-x1) > (y2-y1));
372 case 5: //east
373 return x2 > x1;
374 case 6: //south east
375 return ((x2-x1) > ((-1 * y2)-(-1 * y1))) && (((-1 * x2)-(-1 * x1)) < (y2-y1));
376 case 7: //south
377 return y2 > y1;
378 case 0: //south west
379 return (((-1 * x2)-(-1 * x1)) > ((-1 * y2)-(-1 * y1))) && ((x2-x1) < (y2-y1));
380 case 1: //west
381 return x2 < x1;
382 }
383 return false;
384 }
385
386 /**
387 * Compute a path from (x1,y1) to (x2,y2)
388 * Store waypoint inside path
389 * limit is the maximum number of explored node
390 * @return true if a path is found
391 */
computePath(const FPoint & start_pos,const FPoint & end_pos,std::vector<FPoint> & path,int movement_type,unsigned int limit)392 bool MapCollision::computePath(const FPoint& start_pos, const FPoint& end_pos, std::vector<FPoint> &path, int movement_type, unsigned int limit) {
393
394 if (isOutsideMap(end_pos.x, end_pos.y)) return false;
395
396 // default limit set to 10% of the total map size
397 if (limit == 0)
398 limit = (map_size.x * map_size.y) / 10;
399
400 // path must be empty
401 if (!path.empty())
402 path.clear();
403
404 // convert start & end to MapCollision precision
405 Point start(start_pos);
406 Point end(end_pos);
407
408 // if the target square has an entity, temporarily clear it to compute the path
409 bool target_blocks = false;
410 int target_blocks_type = colmap[end.x][end.y];
411 if (colmap[end.x][end.y] == BLOCKS_ENTITIES || colmap[end.x][end.y] == BLOCKS_ENEMIES) {
412 target_blocks = true;
413 unblock(end_pos.x, end_pos.y);
414 }
415
416 Point current = start;
417 AStarNode* node = new AStarNode(start);
418 node->setActualCost(0);
419 node->setEstimatedCost(Utils::calcDist(FPoint(start),FPoint(end)));
420 node->setParent(current);
421
422 AStarContainer open(map_size.x, map_size.y, limit);
423 AStarCloseContainer close(map_size.x, map_size.y, limit);
424
425 open.add(node);
426
427 while (!open.isEmpty() && static_cast<unsigned>(close.getSize()) < limit) {
428 node = open.get_shortest_f();
429
430 current.x = node->getX();
431 current.y = node->getY();
432 close.add(node);
433 open.remove(node);
434
435 if ( current.x == end.x && current.y == end.y)
436 break; //path found !
437
438 //limit evaluated nodes to the size of the map
439 std::list<Point> neighbours = node->getNeighbours(map_size.x, map_size.y);
440
441 // for every neighbour of current node
442 for (std::list<Point>::iterator it=neighbours.begin(); it != neighbours.end(); ++it) {
443 Point neighbour = *it;
444
445 // do not exceed the node limit when adding nodes
446 if (static_cast<unsigned>(open.getSize()) >= limit) {
447 break;
448 }
449
450 // if neighbour is not free of any collision, skip it
451 if (!isValidTile(neighbour.x,neighbour.y,movement_type, MapCollision::COLLIDE_NORMAL))
452 continue;
453 // if nabour is already in close, skip it
454 if(close.exists(neighbour))
455 continue;
456
457 // if neighbour isn't inside open, add it as a new Node
458 if(!open.exists(neighbour)) {
459 AStarNode* newNode = new AStarNode(neighbour);
460 newNode->setActualCost(node->getActualCost() + Utils::calcDist(FPoint(current),FPoint(neighbour)));
461 newNode->setParent(current);
462 newNode->setEstimatedCost(Utils::calcDist(FPoint(neighbour),FPoint(end)));
463 open.add(newNode);
464 }
465 // else, update it's cost if better
466 else {
467 AStarNode* i = open.get(neighbour.x, neighbour.y);
468 if (node->getActualCost() + Utils::calcDist(FPoint(current),FPoint(neighbour)) < i->getActualCost()) {
469 Point pos(i->getX(), i->getY());
470 Point parent_pos(node->getX(), node->getY());
471 open.updateParent(pos, parent_pos, node->getActualCost() + Utils::calcDist(FPoint(current),FPoint(neighbour)));
472 }
473 }
474 }
475 }
476
477 if (!(current.x == end.x && current.y == end.y)) {
478
479 //couldnt find the target so map a path to the closest node found
480 node = close.get_shortest_h();
481 current.x = node->getX();
482 current.y = node->getY();
483
484 while (!(current.x == start.x && current.y == start.y)) {
485 path.push_back(collisionToMap(current));
486 current = close.get(current.x, current.y)->getParent();
487 }
488 }
489 else {
490 // store path from end to start
491 path.push_back(collisionToMap(end));
492 while (!(current.x == start.x && current.y == start.y)) {
493 path.push_back(collisionToMap(current));
494 current = close.get(current.x, current.y)->getParent();
495 }
496 }
497 // reblock target if needed
498 if (target_blocks) block(end_pos.x, end_pos.y, target_blocks_type == BLOCKS_ENEMIES);
499
500 return !path.empty();
501 }
502
block(const float & map_x,const float & map_y,bool is_ally)503 void MapCollision::block(const float& map_x, const float& map_y, bool is_ally) {
504 const int tile_x = int(map_x);
505 const int tile_y = int(map_y);
506
507 if (colmap[tile_x][tile_y] == BLOCKS_NONE) {
508 if(is_ally)
509 colmap[tile_x][tile_y] = BLOCKS_ENEMIES;
510 else
511 colmap[tile_x][tile_y] = BLOCKS_ENTITIES;
512 }
513
514 }
515
unblock(const float & map_x,const float & map_y)516 void MapCollision::unblock(const float& map_x, const float& map_y) {
517 const int tile_x = int(map_x);
518 const int tile_y = int(map_y);
519
520 if (colmap[tile_x][tile_y] == BLOCKS_ENTITIES || colmap[tile_x][tile_y] == BLOCKS_ENEMIES) {
521 colmap[tile_x][tile_y] = BLOCKS_NONE;
522 }
523
524 }
525
526 /**
527 * Given a target, trys to return one of the 8+ adjacent tiles
528 * Returns the retargeted position on success, returns the original position on failure
529 */
getRandomNeighbor(const Point & target,int range,bool ignore_blocked)530 FPoint MapCollision::getRandomNeighbor(const Point& target, int range, bool ignore_blocked) {
531 FPoint new_target(target);
532 std::vector<FPoint> valid_tiles;
533
534 for (int i=-range; i<=range; i++) {
535 for (int j=-range; j<=range; j++) {
536 if (i == 0 && j == 0) continue; // skip the middle tile
537 new_target.x = static_cast<float>(target.x + i) + 0.5f;
538 new_target.y = static_cast<float>(target.y + j) + 0.5f;
539 if (isValidPosition(new_target.x, new_target.y, MOVE_NORMAL, COLLIDE_NORMAL) || ignore_blocked)
540 valid_tiles.push_back(new_target);
541 }
542 }
543
544 if (!valid_tiles.empty())
545 return valid_tiles[rand() % valid_tiles.size()];
546 else
547 return FPoint(target);
548 }
549
collisionToMap(const Point & p)550 FPoint MapCollision::collisionToMap(const Point& p) {
551 FPoint ret;
552 ret.x = static_cast<float>(p.x) + 0.5f;
553 ret.y = static_cast<float>(p.y) + 0.5f;
554 return ret;
555 }
556
~MapCollision()557 MapCollision::~MapCollision() {
558 }
559
560 // re-enable asserts in other files
561 #ifdef __EMSCRIPTEN__
562 #undef NDEBUG
563 #endif
564