1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 //=============================================================================
24 //
25 // PathFinder v2.00 (AC2 customized version)
26 // (c) 1998-99 Chris Jones
27 //
28 //=============================================================================
29
30 #include "ags/engine/ac/route_finder_impl_legacy.h"
31 #include "ags/lib/std/math.h"
32
33 #include "ags/shared/ac/common.h" // quit()
34 #include "ags/shared/ac/common_defines.h"
35 #include "ags/shared/game/room_struct.h"
36 #include "ags/engine/ac/move_list.h" // MoveList
37 #include "ags/shared/gfx/bitmap.h"
38 #include "ags/shared/debugging/out.h"
39 #include "ags/globals.h"
40
41 namespace AGS3 {
42
43 extern void update_polled_stuff_if_runtime();
44
45 using AGS::Shared::Bitmap;
46 namespace BitmapHelper = AGS::Shared::BitmapHelper;
47
48 // #define DEBUG_PATHFINDER
49
50 #ifdef DEBUG_PATHFINDER
51 // extern Bitmap *mousecurs[10];
52 #endif
53
54 namespace AGS {
55 namespace Engine {
56 namespace RouteFinderLegacy {
57
58 #define MANOBJNUM 99
59
60 #define MAXPATHBACK 1000
61 static int *pathbackx = nullptr;
62 static int *pathbacky = nullptr;
63 static int waspossible = 1;
64 static int suggestx;
65 static int suggesty;
66 static int line_failed = 0;
67
init_pathfinder()68 void init_pathfinder() {
69 pathbackx = (int *)malloc(sizeof(int) * MAXPATHBACK);
70 pathbacky = (int *)malloc(sizeof(int) * MAXPATHBACK);
71 }
72
set_wallscreen(Bitmap * wallscreen_)73 void set_wallscreen(Bitmap *wallscreen_) {
74 _G(wallscreen) = wallscreen_;
75 }
76
77 // TODO: find a way to reimpl this with Bitmap
line_callback(BITMAP * bmpp,int x,int y,int d)78 static void line_callback(BITMAP *bmpp, int x, int y, int d) {
79 /* if ((x>=320) | (y>=200) | (x<0) | (y<0)) line_failed=1;
80 else */ if (getpixel(bmpp, x, y) < 1)
81 line_failed = 1;
82 else if (line_failed == 0) {
83 _G(lastcx) = x;
84 _G(lastcy) = y;
85 }
86 }
87
88
89
can_see_from(int x1,int y1,int x2,int y2)90 int can_see_from(int x1, int y1, int x2, int y2) {
91 assert(_G(wallscreen) != nullptr);
92
93 line_failed = 0;
94 _G(lastcx) = x1;
95 _G(lastcy) = y1;
96
97 if ((x1 == x2) && (y1 == y2))
98 return 1;
99
100 // TODO: need some way to use Bitmap with callback
101 do_line((BITMAP *)_G(wallscreen)->GetAllegroBitmap(), x1, y1, x2, y2, 0, line_callback);
102 if (line_failed == 0)
103 return 1;
104
105 return 0;
106 }
107
get_lastcpos(int & lastcx_,int & lastcy_)108 void get_lastcpos(int &lastcx_, int &lastcy_) {
109 lastcx_ = _G(lastcx);
110 lastcy_ = _G(lastcy);
111 }
112
113
find_nearest_walkable_area(Bitmap * tempw,int fromX,int fromY,int toX,int toY,int destX,int destY,int granularity)114 int find_nearest_walkable_area(Bitmap *tempw, int fromX, int fromY, int toX, int toY, int destX, int destY, int granularity) {
115 assert(tempw != nullptr);
116
117 int ex, ey, nearest = 99999, thisis, nearx = 0, neary = 0;
118 if (fromX < 0) fromX = 0;
119 if (fromY < 0) fromY = 0;
120 if (toX >= tempw->GetWidth()) toX = tempw->GetWidth() - 1;
121 if (toY >= tempw->GetHeight()) toY = tempw->GetHeight() - 1;
122
123 for (ex = fromX; ex < toX; ex += granularity) {
124 for (ey = fromY; ey < toY; ey += granularity) {
125 if (tempw->GetScanLine(ey)[ex] != 232)
126 continue;
127
128 thisis = (int)::sqrt((double)((ex - destX) * (ex - destX) + (ey - destY) * (ey - destY)));
129 if (thisis < nearest) {
130 nearest = thisis;
131 nearx = ex;
132 neary = ey;
133 }
134 }
135 }
136
137 if (nearest < 90000) {
138 suggestx = nearx;
139 suggesty = neary;
140 return 1;
141 }
142
143 return 0;
144 }
145
146 #define MAX_GRANULARITY 3
147 static int walk_area_granularity[MAX_WALK_AREAS + 1];
is_route_possible(int fromx,int fromy,int tox,int toy,Bitmap * wss)148 static int is_route_possible(int fromx, int fromy, int tox, int toy, Bitmap *wss) {
149 _G(wallscreen) = wss;
150 suggestx = -1;
151
152 // ensure it's a memory bitmap, so we can use direct access to line[] array
153 if ((wss == nullptr) || (wss->GetColorDepth() != 8))
154 quit("is_route_possible: invalid walkable areas bitmap supplied");
155
156 if (_G(wallscreen)->GetPixel(fromx, fromy) < 1)
157 return 0;
158
159 Bitmap *tempw = BitmapHelper::CreateBitmapCopy(_G(wallscreen), 8);
160 if (tempw == nullptr)
161 quit("no memory for route calculation");
162
163 int dd, ff;
164 // initialize array for finding widths of walkable areas
165 int thisar, inarow = 0, lastarea = 0;
166 int walk_area_times[MAX_WALK_AREAS + 1];
167 for (dd = 0; dd <= MAX_WALK_AREAS; dd++) {
168 walk_area_times[dd] = 0;
169 walk_area_granularity[dd] = 0;
170 }
171
172 for (ff = 0; ff < tempw->GetHeight(); ff++) {
173 const uint8_t *tempw_scanline = tempw->GetScanLine(ff);
174 for (dd = 0; dd < tempw->GetWidth(); dd++) {
175 thisar = tempw_scanline[dd];
176 // count how high the area is at this point
177 if ((thisar == lastarea) && (thisar > 0))
178 inarow++;
179 else if (lastarea > MAX_WALK_AREAS)
180 quit("!Calculate_Route: invalid colours in walkable area mask");
181 else if (lastarea != 0) {
182 walk_area_granularity[lastarea] += inarow;
183 walk_area_times[lastarea]++;
184 inarow = 0;
185 }
186 lastarea = thisar;
187 }
188 }
189
190 for (dd = 0; dd < tempw->GetWidth(); dd++) {
191 for (ff = 0; ff < tempw->GetHeight(); ff++) {
192 uint8_t *tempw_scanline = tempw->GetScanLineForWriting(ff);
193 thisar = tempw_scanline[dd];
194 if (thisar > 0)
195 tempw_scanline[dd] = 1;
196 // count how high the area is at this point
197 if ((thisar == lastarea) && (thisar > 0))
198 inarow++;
199 else if (lastarea != 0) {
200 walk_area_granularity[lastarea] += inarow;
201 walk_area_times[lastarea]++;
202 inarow = 0;
203 }
204 lastarea = thisar;
205 }
206 }
207
208 // find the average "width" of a path in this walkable area
209 for (dd = 1; dd <= MAX_WALK_AREAS; dd++) {
210 if (walk_area_times[dd] == 0) {
211 walk_area_granularity[dd] = MAX_GRANULARITY;
212 continue;
213 }
214
215 walk_area_granularity[dd] /= walk_area_times[dd];
216 if (walk_area_granularity[dd] <= 4)
217 walk_area_granularity[dd] = 2;
218 else if (walk_area_granularity[dd] <= 15)
219 walk_area_granularity[dd] = 3;
220 else
221 walk_area_granularity[dd] = MAX_GRANULARITY;
222
223 #ifdef DEBUG_PATHFINDER
224 AGS::Shared::Debug::Printf("area %d: Gran %d", dd, walk_area_granularity[dd]);
225 #endif
226 }
227 walk_area_granularity[0] = MAX_GRANULARITY;
228
229 tempw->FloodFill(fromx, fromy, 232);
230 if (tempw->GetPixel(tox, toy) != 232) {
231 // Destination pixel is not walkable
232 // Try the 100x100 square around the target first at 3-pixel granularity
233 int tryFirstX = tox - 50, tryToX = tox + 50;
234 int tryFirstY = toy - 50, tryToY = toy + 50;
235
236 if (!find_nearest_walkable_area(tempw, tryFirstX, tryFirstY, tryToX, tryToY, tox, toy, 3)) {
237 // Nothing found, sweep the whole room at 5 pixel granularity
238 find_nearest_walkable_area(tempw, 0, 0, tempw->GetWidth(), tempw->GetHeight(), tox, toy, 5);
239 }
240
241 delete tempw;
242 return 0;
243 }
244 delete tempw;
245
246 return 1;
247 }
248
249 static int leftorright = 0;
250 static int nesting = 0;
251 static int pathbackstage = 0;
252 static int finalpartx = 0;
253 static int finalparty = 0;
254 static short **beenhere = nullptr; //[200][320];
255 static int beenhere_array_size = 0;
256 static const int BEENHERE_SIZE = 2;
257
258 #define DIR_LEFT 0
259 #define DIR_RIGHT 2
260 #define DIR_UP 1
261 #define DIR_DOWN 3
262
try_this_square(int srcx,int srcy,int tox,int toy)263 static int try_this_square(int srcx, int srcy, int tox, int toy) {
264 assert(pathbackx != nullptr);
265 assert(pathbacky != nullptr);
266 assert(beenhere != nullptr);
267
268 if (beenhere[srcy][srcx] & 0x80)
269 return 0;
270
271 // nesting of 8040 leads to stack overflow
272 if (nesting > 7000)
273 return 0;
274
275 nesting++;
276 if (can_see_from(srcx, srcy, tox, toy)) {
277 finalpartx = srcx;
278 finalparty = srcy;
279 nesting--;
280 pathbackstage = 0;
281 return 2;
282 }
283
284 #ifdef DEBUG_PATHFINDER
285 // wputblock(_G(lastcx), _G(lastcy), mousecurs[C_CROSS], 1);
286 #endif
287
288 int trydir = DIR_UP;
289 int xdiff = abs(srcx - tox), ydiff = abs(srcy - toy);
290 if (ydiff > xdiff) {
291 if (srcy > toy)
292 trydir = DIR_UP;
293 else
294 trydir = DIR_DOWN;
295 } else if (srcx > tox)
296 trydir = DIR_LEFT;
297 else if (srcx < tox)
298 trydir = DIR_RIGHT;
299
300 int iterations = 0;
301
302 try_again:
303 int nextx = srcx, nexty = srcy;
304 if (trydir == DIR_LEFT)
305 nextx--;
306 else if (trydir == DIR_RIGHT)
307 nextx++;
308 else if (trydir == DIR_DOWN)
309 nexty++;
310 else if (trydir == DIR_UP)
311 nexty--;
312
313 iterations++;
314 if (iterations > 5) {
315 #ifdef DEBUG_PATHFINDER
316 AGS::Shared::Debug::Printf("not found: %d,%d beenhere 0x%X\n", srcx, srcy, beenhere[srcy][srcx]);
317 #endif
318 nesting--;
319 return 0;
320 }
321
322 if (((nextx < 0) | (nextx >= _G(wallscreen)->GetWidth()) | (nexty < 0) | (nexty >= _G(wallscreen)->GetHeight())) ||
323 (_G(wallscreen)->GetPixel(nextx, nexty) == 0) || ((beenhere[srcy][srcx] & (1 << trydir)) != 0)) {
324
325 if (leftorright == 0) {
326 trydir++;
327 if (trydir > 3)
328 trydir = 0;
329 } else {
330 trydir--;
331 if (trydir < 0)
332 trydir = 3;
333 }
334 goto try_again;
335 }
336 beenhere[srcy][srcx] |= (1 << trydir);
337 // srcx=nextx; srcy=nexty;
338 beenhere[srcy][srcx] |= 0x80; // being processed
339
340 int retcod = try_this_square(nextx, nexty, tox, toy);
341 if (retcod == 0)
342 goto try_again;
343
344 nesting--;
345 beenhere[srcy][srcx] &= 0x7f;
346 if (retcod == 2) {
347 pathbackx[pathbackstage] = srcx;
348 pathbacky[pathbackstage] = srcy;
349 pathbackstage++;
350 if (pathbackstage >= MAXPATHBACK - 1)
351 return 0;
352
353 return 2;
354 }
355 return 1;
356 }
357
358
359 #define CHECK_MIN(cellx, celly) { \
360 if (beenhere[celly][cellx] == -1) {\
361 adjcount = 0; \
362 if ((_G(wallscreen)->GetScanLine(celly)[cellx] != 0) && (beenhere[j][i]+modifier <= min)) {\
363 if (beenhere[j][i]+modifier < min) { \
364 min = beenhere[j][i]+modifier; \
365 numfound = 0; } \
366 if (numfound < 40) { \
367 newcell[numfound] = (celly) * _G(wallscreen)->GetWidth() + (cellx);\
368 cheapest[numfound] = j * _G(wallscreen)->GetWidth() + i;\
369 numfound++; \
370 }\
371 } \
372 }}
373
374 #define MAX_TRAIL_LENGTH 5000
375
376 // Round down the supplied co-ordinates to the area granularity,
377 // and move a bit if this causes them to become non-walkable
round_down_coords(int & tmpx,int & tmpy)378 static void round_down_coords(int &tmpx, int &tmpy) {
379 assert(_G(wallscreen) != nullptr);
380
381 int startgran = walk_area_granularity[_G(wallscreen)->GetPixel(tmpx, tmpy)];
382 tmpy = tmpy - tmpy % startgran;
383
384 if (tmpy < 0)
385 tmpy = 0;
386
387 tmpx = tmpx - tmpx % startgran;
388 if (tmpx < 0)
389 tmpx = 0;
390
391 if (_G(wallscreen)->GetPixel(tmpx, tmpy) == 0) {
392 tmpx += startgran;
393 if ((_G(wallscreen)->GetPixel(tmpx, tmpy) == 0) && (tmpy < _G(wallscreen)->GetHeight() - startgran)) {
394 tmpy += startgran;
395
396 if (_G(wallscreen)->GetPixel(tmpx, tmpy) == 0)
397 tmpx -= startgran;
398 }
399 }
400 }
401
find_route_dijkstra(int fromx,int fromy,int destx,int desty)402 static int find_route_dijkstra(int fromx, int fromy, int destx, int desty) {
403 int i, j;
404
405 assert(_G(wallscreen) != nullptr);
406 assert(pathbackx != nullptr);
407 assert(pathbacky != nullptr);
408 assert(beenhere != nullptr);
409
410 // This algorithm doesn't behave differently the second time, so ignore
411 if (leftorright == 1)
412 return 0;
413
414 for (i = 0; i < _G(wallscreen)->GetHeight(); i++)
415 memset(&beenhere[i][0], 0xff, _G(wallscreen)->GetWidth() * BEENHERE_SIZE);
416
417 round_down_coords(fromx, fromy);
418 beenhere[fromy][fromx] = 0;
419
420 int temprd = destx, tempry = desty;
421 round_down_coords(temprd, tempry);
422 if ((temprd == fromx) && (tempry == fromy)) {
423 // already at destination
424 pathbackstage = 0;
425 return 1;
426 }
427
428 int allocsize = int(_G(wallscreen)->GetWidth()) * int(_G(wallscreen)->GetHeight()) * sizeof(int);
429 int *parent = (int *)malloc(allocsize);
430 int min = 999999, cheapest[40], newcell[40], replace[40];
431 int *visited = (int *)malloc(MAX_TRAIL_LENGTH * sizeof(int));
432 int iteration = 1;
433 visited[0] = fromy * _G(wallscreen)->GetWidth() + fromx;
434 parent[visited[0]] = -1;
435
436 int granularity = 3, newx = -1, newy, foundAnswer = -1, numreplace;
437 int changeiter, numfound, adjcount;
438 int destxlow = destx - MAX_GRANULARITY;
439 int destylow = desty - MAX_GRANULARITY;
440 int destxhi = destxlow + MAX_GRANULARITY * 2;
441 int destyhi = destylow + MAX_GRANULARITY * 2;
442 int modifier = 0;
443 int totalfound = 0;
444 int DIRECTION_BONUS = 0;
445
446 update_polled_stuff_if_runtime();
447
448 while (foundAnswer < 0) {
449 min = 29999;
450 changeiter = iteration;
451 numfound = 0;
452 numreplace = 0;
453
454 for (int n = 0; n < iteration; n++) {
455 if (visited[n] == -1)
456 continue;
457
458 i = visited[n] % _G(wallscreen)->GetWidth();
459 j = visited[n] / _G(wallscreen)->GetWidth();
460 granularity = walk_area_granularity[_G(wallscreen)->GetScanLine(j)[i]];
461 adjcount = 1;
462
463 if (i >= granularity) {
464 modifier = (destx < i) ? DIRECTION_BONUS : 0;
465 CHECK_MIN(i - granularity, j)
466 }
467
468 if (j >= granularity) {
469 modifier = (desty < j) ? DIRECTION_BONUS : 0;
470 CHECK_MIN(i, j - granularity)
471 }
472
473 if (i < _G(wallscreen)->GetWidth() - granularity) {
474 modifier = (destx > i) ? DIRECTION_BONUS : 0;
475 CHECK_MIN(i + granularity, j)
476 }
477
478 if (j < _G(wallscreen)->GetHeight() - granularity) {
479 modifier = (desty > j) ? DIRECTION_BONUS : 0;
480 CHECK_MIN(i, j + granularity)
481 }
482
483 // If all the adjacent cells have been done, stop checking this one
484 if (adjcount) {
485 if (numreplace < 40) {
486 visited[numreplace] = -1;
487 replace[numreplace] = n;
488 numreplace++;
489 }
490 }
491 }
492
493 if (numfound == 0) {
494 free(visited);
495 free(parent);
496 return 0;
497 }
498
499 totalfound += numfound;
500 for (int p = 0; p < numfound; p++) {
501 newx = newcell[p] % _G(wallscreen)->GetWidth();
502 newy = newcell[p] / _G(wallscreen)->GetWidth();
503 beenhere[newy][newx] = beenhere[cheapest[p] / _G(wallscreen)->GetWidth()][cheapest[p] % _G(wallscreen)->GetWidth()] + 1;
504 // int wal = walk_area_granularity[->GetPixel(_G(wallscreen), newx, newy)];
505 // beenhere[newy - newy%wal][newx - newx%wal] = beenhere[newy][newx];
506 parent[newcell[p]] = cheapest[p];
507
508 // edges of screen pose a problem, so if current and dest are within
509 // certain distance of the edge, say we've got it
510 if ((newx >= _G(wallscreen)->GetWidth() - MAX_GRANULARITY) && (destx >= _G(wallscreen)->GetWidth() - MAX_GRANULARITY))
511 newx = destx;
512
513 if ((newy >= _G(wallscreen)->GetHeight() - MAX_GRANULARITY) && (desty >= _G(wallscreen)->GetHeight() - MAX_GRANULARITY))
514 newy = desty;
515
516 // Found the desination, abort loop
517 if ((newx >= destxlow) && (newx <= destxhi) && (newy >= destylow)
518 && (newy <= destyhi)) {
519 foundAnswer = newcell[p];
520 break;
521 }
522
523 if (totalfound >= 1000) {
524 //Doesn't work cos it can see the destination from the point that's
525 //not nearest
526 // every so often, check if we can see the destination
527 if (can_see_from(newx, newy, destx, desty)) {
528 DIRECTION_BONUS -= 50;
529 totalfound = 0;
530 }
531
532 }
533
534 if (numreplace > 0) {
535 numreplace--;
536 changeiter = replace[numreplace];
537 } else
538 changeiter = iteration;
539
540 visited[changeiter] = newcell[p];
541 if (changeiter == iteration)
542 iteration++;
543
544 changeiter = iteration;
545 if (iteration >= MAX_TRAIL_LENGTH) {
546 free(visited);
547 free(parent);
548 return 0;
549 }
550 }
551 if (totalfound >= 1000) {
552 update_polled_stuff_if_runtime();
553 totalfound = 0;
554 }
555 }
556 free(visited);
557
558 int on;
559 pathbackstage = 0;
560 pathbackx[pathbackstage] = destx;
561 pathbacky[pathbackstage] = desty;
562 pathbackstage++;
563
564 for (on = parent[foundAnswer];; on = parent[on]) {
565 if (on == -1)
566 break;
567
568 newx = on % _G(wallscreen)->GetWidth();
569 newy = on / _G(wallscreen)->GetWidth();
570 if ((newx >= destxlow) && (newx <= destxhi) && (newy >= destylow)
571 && (newy <= destyhi))
572 break;
573
574 pathbackx[pathbackstage] = on % _G(wallscreen)->GetWidth();
575 pathbacky[pathbackstage] = on / _G(wallscreen)->GetWidth();
576 pathbackstage++;
577 if (pathbackstage >= MAXPATHBACK) {
578 free(parent);
579 return 0;
580 }
581 }
582 free(parent);
583 return 1;
584 }
585
__find_route(int srcx,int srcy,short * tox,short * toy,int noredx)586 static int __find_route(int srcx, int srcy, short *tox, short *toy, int noredx) {
587 assert(_G(wallscreen) != nullptr);
588 assert(beenhere != nullptr);
589 assert(tox != nullptr);
590 assert(toy != nullptr);
591
592 if ((noredx == 0) && (_G(wallscreen)->GetPixel(tox[0], toy[0]) == 0))
593 return 0; // clicked on a wall
594
595 pathbackstage = 0;
596
597 if (leftorright == 0) {
598 waspossible = 1;
599
600 findroutebk:
601 if ((srcx == tox[0]) && (srcy == toy[0])) {
602 pathbackstage = 0;
603 return 1;
604 }
605
606 if ((waspossible = is_route_possible(srcx, srcy, tox[0], toy[0], _G(wallscreen))) == 0) {
607 if (suggestx >= 0) {
608 tox[0] = suggestx;
609 toy[0] = suggesty;
610 goto findroutebk;
611 }
612 return 0;
613 }
614 }
615
616 if (leftorright == 1) {
617 if (waspossible == 0)
618 return 0;
619 }
620
621 // Try the new pathfinding algorithm
622 if (find_route_dijkstra(srcx, srcy, tox[0], toy[0])) {
623 return 1;
624 }
625
626 // if the new pathfinder failed, try the old one
627 pathbackstage = 0;
628 memset(&beenhere[0][0], 0, _G(wallscreen)->GetWidth() * _G(wallscreen)->GetHeight() * BEENHERE_SIZE);
629 if (try_this_square(srcx, srcy, tox[0], toy[0]) == 0)
630 return 0;
631
632 return 1;
633 }
634
set_route_move_speed(int speed_x,int speed_y)635 void set_route_move_speed(int speed_x, int speed_y) {
636 // negative move speeds like -2 get converted to 1/2
637 if (speed_x < 0) {
638 _G(move_speed_x) = itofix(1) / (-speed_x);
639 } else {
640 _G(move_speed_x) = itofix(speed_x);
641 }
642
643 if (speed_y < 0) {
644 _G(move_speed_y) = itofix(1) / (-speed_y);
645 } else {
646 _G(move_speed_y) = itofix(speed_y);
647 }
648 }
649
650 // Calculates the X and Y per game loop, for this stage of the
651 // movelist
calculate_move_stage(MoveList * mlsp,int aaa)652 void calculate_move_stage(MoveList *mlsp, int aaa) {
653 assert(mlsp != nullptr);
654
655 // work out the x & y per move. First, opp/adj=tan, so work out the angle
656 if (mlsp->pos[aaa] == mlsp->pos[aaa + 1]) {
657 mlsp->xpermove[aaa] = 0;
658 mlsp->ypermove[aaa] = 0;
659 return;
660 }
661
662 short ourx = (mlsp->pos[aaa] >> 16) & 0x000ffff;
663 short oury = (mlsp->pos[aaa] & 0x000ffff);
664 short destx = ((mlsp->pos[aaa + 1] >> 16) & 0x000ffff);
665 short desty = (mlsp->pos[aaa + 1] & 0x000ffff);
666
667 // Special case for vertical and horizontal movements
668 if (ourx == destx) {
669 mlsp->xpermove[aaa] = 0;
670 mlsp->ypermove[aaa] = _G(move_speed_y);
671 if (desty < oury)
672 mlsp->ypermove[aaa] = -mlsp->ypermove[aaa];
673
674 return;
675 }
676
677 if (oury == desty) {
678 mlsp->xpermove[aaa] = _G(move_speed_x);
679 mlsp->ypermove[aaa] = 0;
680 if (destx < ourx)
681 mlsp->xpermove[aaa] = -mlsp->xpermove[aaa];
682
683 return;
684 }
685
686 fixed xdist = itofix(abs(ourx - destx));
687 fixed ydist = itofix(abs(oury - desty));
688
689 fixed useMoveSpeed;
690
691 if (_G(move_speed_x) == _G(move_speed_y)) {
692 useMoveSpeed = _G(move_speed_x);
693 } else {
694 // different X and Y move speeds
695 // the X proportion of the movement is (x / (x + y))
696 fixed xproportion = fixdiv(xdist, (xdist + ydist));
697
698 if (_G(move_speed_x) > _G(move_speed_y)) {
699 // speed = y + ((1 - xproportion) * (x - y))
700 useMoveSpeed = _G(move_speed_y) + fixmul(xproportion, _G(move_speed_x) - _G(move_speed_y));
701 } else {
702 // speed = x + (xproportion * (y - x))
703 useMoveSpeed = _G(move_speed_x) + fixmul(itofix(1) - xproportion, _G(move_speed_y) - _G(move_speed_x));
704 }
705 }
706
707 fixed angl = fixatan(fixdiv(ydist, xdist));
708
709 // now, since new opp=hyp*sin, work out the Y step size
710 //fixed newymove = useMoveSpeed * fsin(angl);
711 fixed newymove = fixmul(useMoveSpeed, fixsin(angl));
712
713 // since adj=hyp*cos, work out X step size
714 //fixed newxmove = useMoveSpeed * fcos(angl);
715 fixed newxmove = fixmul(useMoveSpeed, fixcos(angl));
716
717 if (destx < ourx)
718 newxmove = -newxmove;
719 if (desty < oury)
720 newymove = -newymove;
721
722 mlsp->xpermove[aaa] = newxmove;
723 mlsp->ypermove[aaa] = newymove;
724
725 #ifdef DEBUG_PATHFINDER
726 AGS::Shared::Debug::Printf("stage %d from %d,%d to %d,%d Xpermove:%X Ypm:%X", aaa, ourx, oury, destx, desty, newxmove, newymove);
727 // wtextcolor(14);
728 // wgtprintf((reallyneed[aaa] >> 16) & 0x000ffff, reallyneed[aaa] & 0x000ffff, _G(cbuttfont), "%d", aaa);
729 #endif
730 }
731
732
733 #define MAKE_INTCOORD(x,y) (((unsigned short)x << 16) | ((unsigned short)y))
734
find_route(short srcx,short srcy,short xx,short yy,Bitmap * onscreen,int movlst,int nocross,int ignore_walls)735 int find_route(short srcx, short srcy, short xx, short yy, Bitmap *onscreen, int movlst, int nocross, int ignore_walls) {
736 assert(onscreen != nullptr);
737 assert(_G(mls) != nullptr);
738 assert(pathbackx != nullptr);
739 assert(pathbacky != nullptr);
740
741 #ifdef DEBUG_PATHFINDER
742 // __wnormscreen();
743 #endif
744 _G(wallscreen) = onscreen;
745 leftorright = 0;
746 int aaa;
747
748 if (_G(wallscreen)->GetHeight() > beenhere_array_size) {
749 beenhere = (short **)realloc(beenhere, sizeof(short *) * _G(wallscreen)->GetHeight());
750 beenhere_array_size = _G(wallscreen)->GetHeight();
751
752 if (beenhere == nullptr)
753 quit("insufficient memory to allocate pathfinder beenhere buffer");
754
755 for (aaa = 0; aaa < _G(wallscreen)->GetHeight(); aaa++) {
756 beenhere[aaa] = nullptr;
757 }
758 }
759
760 int orisrcx = srcx, orisrcy = srcy;
761 finalpartx = -1;
762
763 if (ignore_walls) {
764 pathbackstage = 0;
765 } else if (can_see_from(srcx, srcy, xx, yy)) {
766 pathbackstage = 0;
767 } else {
768 beenhere[0] = (short *)malloc((_G(wallscreen)->GetWidth()) * (_G(wallscreen)->GetHeight()) * BEENHERE_SIZE);
769
770 for (aaa = 1; aaa < _G(wallscreen)->GetHeight(); aaa++)
771 beenhere[aaa] = beenhere[0] + aaa * (_G(wallscreen)->GetWidth());
772
773 if (__find_route(srcx, srcy, &xx, &yy, nocross) == 0) {
774 leftorright = 1;
775 if (__find_route(srcx, srcy, &xx, &yy, nocross) == 0)
776 pathbackstage = -1;
777 }
778 free(beenhere[0]);
779
780 for (aaa = 0; aaa < _G(wallscreen)->GetHeight(); aaa++) {
781 beenhere[aaa] = nullptr;
782 }
783 }
784
785 if (pathbackstage >= 0) {
786 int nearestpos = 0, nearestindx;
787 int reallyneed[MAXNEEDSTAGES], numstages = 0;
788 reallyneed[numstages] = MAKE_INTCOORD(srcx, srcy);
789 numstages++;
790 nearestindx = -1;
791
792 int lastpbs = pathbackstage;
793
794 stage_again:
795 nearestpos = 0;
796 aaa = 1;
797 // find the furthest point that can be seen from this stage
798 for (aaa = pathbackstage - 1; aaa >= 0; aaa--) {
799 #ifdef DEBUG_PATHFINDER
800 AGS::Shared::Debug::Printf("stage %2d: %2d,%2d\n", aaa, pathbackx[aaa], pathbacky[aaa]);
801 #endif
802 if (can_see_from(srcx, srcy, pathbackx[aaa], pathbacky[aaa])) {
803 nearestpos = MAKE_INTCOORD(pathbackx[aaa], pathbacky[aaa]);
804 nearestindx = aaa;
805 }
806 }
807
808 if ((nearestpos == 0) && (can_see_from(srcx, srcy, xx, yy) == 0) &&
809 (srcx >= 0) && (srcy >= 0) && (srcx < _G(wallscreen)->GetWidth()) && (srcy < _G(wallscreen)->GetHeight()) && (pathbackstage > 0)) {
810 // If we couldn't see anything, we're stuck in a corner so advance
811 // to the next square anyway (but only if they're on the screen)
812 nearestindx = pathbackstage - 1;
813 nearestpos = MAKE_INTCOORD(pathbackx[nearestindx], pathbacky[nearestindx]);
814 }
815
816 if (nearestpos > 0) {
817 reallyneed[numstages] = nearestpos;
818 numstages++;
819 if (numstages >= MAXNEEDSTAGES - 1)
820 quit("too many stages for auto-walk");
821 srcx = (nearestpos >> 16) & 0x000ffff;
822 srcy = nearestpos & 0x000ffff;
823 #ifdef DEBUG_PATHFINDER
824 AGS::Shared::Debug::Printf("Added: %d, %d pbs:%d", srcx, srcy, pathbackstage);
825 #endif
826 lastpbs = pathbackstage;
827 pathbackstage = nearestindx;
828 goto stage_again;
829 }
830
831 if (finalpartx >= 0) {
832 reallyneed[numstages] = MAKE_INTCOORD(finalpartx, finalparty);
833 numstages++;
834 }
835
836 // Make sure the end co-ord is in there
837 if (reallyneed[numstages - 1] != MAKE_INTCOORD(xx, yy)) {
838 reallyneed[numstages] = MAKE_INTCOORD(xx, yy);
839 numstages++;
840 }
841
842 if ((numstages == 1) && (xx == orisrcx) && (yy == orisrcy)) {
843 return 0;
844 }
845 #ifdef DEBUG_PATHFINDER
846 AGS::Shared::Debug::Printf("Route from %d,%d to %d,%d - %d stage, %d stages", orisrcx, orisrcy, xx, yy, pathbackstage, numstages);
847 #endif
848 int mlist = movlst;
849 _G(mls)[mlist].numstage = numstages;
850 memcpy(&_G(mls)[mlist].pos[0], &reallyneed[0], sizeof(int) * numstages);
851 #ifdef DEBUG_PATHFINDER
852 AGS::Shared::Debug::Printf("stages: %d\n", numstages);
853 #endif
854
855 for (aaa = 0; aaa < numstages - 1; aaa++) {
856 calculate_move_stage(&_G(mls)[mlist], aaa);
857 }
858
859 _G(mls)[mlist].fromx = orisrcx;
860 _G(mls)[mlist].fromy = orisrcy;
861 _G(mls)[mlist].onstage = 0;
862 _G(mls)[mlist].onpart = 0;
863 _G(mls)[mlist].doneflag = 0;
864 _G(mls)[mlist].lastx = -1;
865 _G(mls)[mlist].lasty = -1;
866 #ifdef DEBUG_PATHFINDER
867 // getch();
868 #endif
869 (void)lastpbs;
870
871 return mlist;
872 } else {
873 return 0;
874 }
875
876 #ifdef DEBUG_PATHFINDER
877 // __unnormscreen();
878 #endif
879 }
880
shutdown_pathfinder()881 void shutdown_pathfinder() {
882 if (pathbackx != nullptr) {
883 free(pathbackx);
884 }
885 if (pathbacky != nullptr) {
886 free(pathbacky);
887 }
888 if (beenhere != nullptr) {
889 if (beenhere[0] != nullptr) {
890 free(beenhere[0]);
891 }
892 free(beenhere);
893 }
894
895 pathbackx = nullptr;
896 pathbacky = nullptr;
897 beenhere = nullptr;
898 beenhere_array_size = 0;
899 }
900
901 } // namespace RouteFinderLegacy
902 } // namespace Engine
903 } // namespace AGS
904 } // namespace AGS3
905