1/*
2 * LegacyClonk
3 *
4 * Copyright (c) 1998-2000, Matthes Bender (RedWolf Design)
5 * Copyright (c) 2017-2021, The LegacyClonk Team and contributors
6 *
7 * Distributed under the terms of the ISC license; see accompanying file
8 * "COPYING" for details.
9 *
10 * "Clonk" is a registered trademark of Matthes Bender, used with permission.
11 * See accompanying file "TRADEMARK" for details.
12 *
13 * To redistribute this file separately, substitute the full license texts
14 * for the above references.
15 */
16
17/* Finds the way through the Clonk landscape */
18
19/* Notes
20
21 09-30-99
22 I have had the concept for this code for more than two years now.
23 Finally, it is written.
24
25 10-26-99
26 C4PathFinderRay::Crawl use IsCrawlAttach instead of GetCrawlAttach (which
27 might not correctly indicate attach loss). Otherwise 1 pixel clefts can lead
28 to backward crawl looping. Surprised, I haven't noticed this before.
29 Also do not check attach loss on first crawl for that be might diagonal.
30 C4PF_Ray_Crawl try new ray: don't worry about checking backwards jump if
31 path to target is all free.
32 C4PathFinderRay::FindCrawlAttachDiagonal check according to desired
33 direction or else might lead off to no attach.
34
35 11-24-99
36 TransferZones
37
38 12-11-99
39 SetCompletePath don't set move-to waypoint if setting use-zone waypoint (is
40 done by C4Command::Transfer on demand and would only cause no-good-entry-point
41 move-to's on crawl-zone-entries).
42*/
43
44#include <C4Include.h>
45#include <C4PathFinder.h>
46
47#include <C4FacetEx.h>
48#include <C4Game.h>
49
50const int32_t C4PF_MaxDepth = 35,
51 C4PF_MaxCrawl = 800,
52 C4PF_MaxRay = 350,
53 C4PF_Threshold = 10,
54
55 C4PF_Direction_Left = -1,
56 C4PF_Direction_Right = +1,
57 C4PF_Direction_None = 0,
58
59 C4PF_Ray_Launch = 0,
60 C4PF_Ray_Crawl = 1,
61 C4PF_Ray_Still = 2,
62 C4PF_Ray_Failure = 3,
63 C4PF_Ray_Deleted = 4,
64
65 C4PF_Crawl_NoAttach = 0,
66 C4PF_Crawl_Top = 1,
67 C4PF_Crawl_Right = 2,
68 C4PF_Crawl_Bottom = 3,
69 C4PF_Crawl_Left = 4,
70
71 C4PF_Draw_Rate = 10;
72
73// C4PathFinderRay
74
75C4PathFinderRay::C4PathFinderRay()
76{
77 Default();
78}
79
80C4PathFinderRay::~C4PathFinderRay()
81{
82 Clear();
83}
84
85void C4PathFinderRay::Default()
86{
87 Status = C4PF_Ray_Launch;
88 X = Y = X2 = Y2 = TargetX = TargetY = 0;
89 Direction = 0;
90 Depth = 0;
91 UseZone = nullptr;
92 From = nullptr;
93 Next = nullptr;
94 pPathFinder = nullptr;
95 CrawlStartX = CrawlStartY = CrawlAttach = 0;
96}
97
98void C4PathFinderRay::Clear() {}
99
100bool C4PathFinderRay::Execute()
101{
102 C4TransferZone *pZone = nullptr;
103 int32_t iX, iY, iLastX, iLastY;
104 switch (Status)
105 {
106 case C4PF_Ray_Launch:
107 // In zone: use zone
108 if (UseZone)
109 {
110 // Mark zone used
111 UseZone->Used = true;
112 // Target in transfer zone: success
113 if (UseZone->At(iX: TargetX, iY: TargetY))
114 {
115 // Set end point
116 X2 = TargetX; Y2 = TargetY;
117 // Set complete path
118 SetCompletePath();
119 // Done
120 pPathFinder->Success = true;
121 Status = C4PF_Ray_Still;
122 }
123 // Continue from other end of zone
124 else
125 {
126 // Find exit point
127 if (!UseZone->GetEntryPoint(rX&: X2, rY&: Y2, iToX: TargetX, iToY: TargetY))
128 {
129 Status = C4PF_Ray_Failure; break;
130 }
131 // Launch new ray (continue direction of entrance ray)
132 if (!pPathFinder->AddRay(iFromX: X2, iFromY: Y2, iToX: TargetX, iToY: TargetY, iDepth: Depth + 1, iDirection: Direction, pFrom: this))
133 {
134 Status = C4PF_Ray_Failure; break;
135 }
136 // Still
137 Status = C4PF_Ray_Still;
138 }
139 return true;
140 }
141 // Not in zone: check path to target
142 // Path free: success
143 else if (PathFree(rX&: X2, rY&: Y2, iToX: TargetX, iToY: TargetY, ppZone: &pZone))
144 {
145 // Set complete path
146 SetCompletePath();
147 // Done
148 pPathFinder->Success = true;
149 Status = C4PF_Ray_Still;
150 return true;
151 }
152 // Path intersected by transfer zone
153 else if (pZone)
154 {
155 // Zone entry point adjust (if not already in zone)
156 if (!pZone->At(iX: X, iY: Y))
157 pZone->GetEntryPoint(rX&: X2, rY&: Y2, iToX: X2, iToY: Y2);
158 // Add use-zone ray
159 if (!pPathFinder->AddRay(iFromX: X2, iFromY: Y2, iToX: TargetX, iToY: TargetY, iDepth: Depth + 1, iDirection: Direction, pFrom: this, pUseZone: pZone))
160 {
161 Status = C4PF_Ray_Failure; break;
162 }
163 // Still
164 Status = C4PF_Ray_Still;
165 // Continue
166 return true;
167 }
168 // Path intersected by solid
169 else
170 {
171 // Start crawling
172 Status = C4PF_Ray_Crawl;
173 CrawlStartX = X2; CrawlStartY = Y2;
174 CrawlAttach = FindCrawlAttach(iX: X2, iY: Y2);
175 CrawlLength = 0;
176 if (!CrawlAttach) CrawlAttach = FindCrawlAttachDiagonal(iX: X2, iY: Y2, iDirection: Direction);
177 CrawlStartAttach = CrawlAttach;
178 // Intersected but no attach found: unexpected failure
179 if (!CrawlAttach) { Status = C4PF_Ray_Failure; break; }
180 // Continue
181 return true;
182 }
183 break;
184
185 case C4PF_Ray_Crawl:
186 // Crawl
187 iLastX = X2; iLastY = Y2;
188 if (!Crawl())
189 {
190 Status = C4PF_Ray_Failure; break;
191 }
192 // Back at crawl starting position: done and still
193 if ((X2 == CrawlStartX) && (Y2 == CrawlStartY) && (CrawlAttach == CrawlStartAttach))
194 {
195 Status = C4PF_Ray_Still; break;
196 }
197 // Check unused zone intersection
198 if (pPathFinder->TransferZonesEnabled)
199 if (pPathFinder->TransferZones)
200 if (pZone = pPathFinder->TransferZones->Find(iX: X2, iY: Y2))
201 if (!pZone->Used)
202 {
203 // Add use-zone ray (with zone entry point adjust)
204 iX = X2; iY = Y2; if (pZone->GetEntryPoint(rX&: iX, rY&: iY, iToX: X2, iToY: Y2))
205 if (!pPathFinder->AddRay(iFromX: iX, iFromY: iY, iToX: TargetX, iToY: TargetY, iDepth: Depth + 1, iDirection: Direction, pFrom: this, pUseZone: pZone))
206 {
207 Status = C4PF_Ray_Failure; break;
208 }
209 // Continue crawling
210 return true;
211 }
212 // Crawl length
213 CrawlLength++;
214 if (CrawlLength >= C4PF_MaxCrawl * pPathFinder->Level)
215 {
216 Status = C4PF_Ray_Still; break;
217 }
218 // Check back path intersection
219 iX = X; iY = Y;
220 if (!PathFree(rX&: iX, rY&: iY, iToX: X2, iToY: Y2))
221 // Insert split ray
222 if (!pPathFinder->SplitRay(pRay: this, iAtX: iLastX, iAtY: iLastY))
223 {
224 Status = C4PF_Ray_Failure; break;
225 }
226 // Try new ray at target
227 iX = X2; iY = Y2;
228 // If has been crawling for a while
229 if (CrawlLength > C4PF_Threshold)
230 // If all free...
231 if (PathFree(rX&: iX, rY&: iY, iToX: TargetX, iToY: TargetY)
232 // ...or at least beyond threshold and not backwards toward crawl start
233 || ((Distance(iX1: iX, iY1: iY, iX2: X2, iY2: Y2) > C4PF_Threshold) && (Distance(iX1: iX, iY1: iY, iX2: CrawlStartX, iY2: CrawlStartY) > Distance(iX1: X2, iY1: Y2, iX2: CrawlStartX, iY2: CrawlStartY))))
234 {
235 // Still
236 Status = C4PF_Ray_Still;
237 // Launch new rays
238 if (!pPathFinder->AddRay(iFromX: X2, iFromY: Y2, iToX: TargetX, iToY: TargetY, iDepth: Depth + 1, iDirection: C4PF_Direction_Left, pFrom: this)
239 || !pPathFinder->AddRay(iFromX: X2, iFromY: Y2, iToX: TargetX, iToY: TargetY, iDepth: Depth + 1, iDirection: C4PF_Direction_Right, pFrom: this))
240 {
241 Status = C4PF_Ray_Failure; break;
242 }
243 }
244 break;
245
246 case C4PF_Ray_Still: case C4PF_Ray_Failure: case C4PF_Ray_Deleted:
247 return false;
248 }
249 return true;
250}
251
252void C4PathFinderRay::Draw(C4FacetEx &cgo)
253{
254 uint8_t byColor = CRed;
255 switch (Status)
256 {
257 case C4PF_Ray_Crawl: byColor = CRed; break;
258 case C4PF_Ray_Still: byColor = CDRed; break;
259 case C4PF_Ray_Failure: byColor = CYellow; break;
260 case C4PF_Ray_Deleted: byColor = CGray2; break;
261 }
262 if (UseZone) byColor = CBlue;
263
264 // Crawl attachment
265 if (Status == C4PF_Ray_Crawl)
266 {
267 int32_t iX = 0, iY = 0; CrawlToAttach(rX&: iX, rY&: iY, iAttach: CrawlAttach);
268 lpDDraw->DrawLine(sfcTarget: cgo.Surface,
269 x1: cgo.X + X2 - cgo.TargetX, y1: cgo.Y + Y2 - cgo.TargetY,
270 x2: cgo.X + X2 - cgo.TargetX + 7 * iX, y2: cgo.Y + Y2 - cgo.TargetY + 7 * iY,
271 byCol: CRed);
272 }
273
274 // Ray line
275 lpDDraw->DrawLine(sfcTarget: cgo.Surface,
276 x1: cgo.X + X - cgo.TargetX, y1: cgo.Y + Y - cgo.TargetY,
277 x2: cgo.X + X2 - cgo.TargetX, y2: cgo.Y + Y2 - cgo.TargetY,
278 byCol: byColor);
279
280 // Crawler point
281 lpDDraw->DrawFrame(sfcDest: cgo.Surface,
282 x1: cgo.X + X2 - cgo.TargetX - 1, y1: cgo.Y + Y2 - cgo.TargetY - 1,
283 x2: cgo.X + X2 - cgo.TargetX + 1, y2: cgo.Y + Y2 - cgo.TargetY + 1,
284 col: (Status == C4PF_Ray_Crawl) ? ((Direction == C4PF_Direction_Left) ? CGreen : CBlue) : byColor);
285
286 // Search target point
287 lpDDraw->DrawFrame(sfcDest: cgo.Surface,
288 x1: cgo.X + TargetX - cgo.TargetX - 2, y1: cgo.Y + TargetY - cgo.TargetY - 2,
289 x2: cgo.X + TargetX - cgo.TargetX + 2, y2: cgo.Y + TargetY - cgo.TargetY + 2,
290 col: CYellow);
291}
292
293bool C4PathFinderRay::PathFree(int32_t &rX, int32_t &rY, int32_t iToX, int32_t iToY, C4TransferZone **ppZone)
294{
295 int32_t d, dx, dy, aincr, bincr, xincr, yincr, x, y;
296 // Y based
297 if (Abs(val: iToX - rX) < Abs(val: iToY - rY))
298 {
299 xincr = (iToX > rX) ? +1 : -1; yincr = (iToY > rY) ? +1 : -1;
300 dy = Abs(val: iToY - rY); dx = Abs(val: iToX - rX);
301 d = 2 * dx - dy; aincr = 2 * (dx - dy); bincr = 2 * dx; x = rX; y = rY;
302 for (y = rY; y != iToY; y += yincr)
303 {
304 // Check point free
305 if (PointFree(iX: x, iY: y)) { rY = y; rX = x; }
306 else return false;
307 // Check transfer zone intersection
308 if (ppZone)
309 if (pPathFinder->TransferZonesEnabled)
310 if (pPathFinder->TransferZones)
311 if (*ppZone = pPathFinder->TransferZones->Find(iX: rX, iY: rY))
312 return false;
313 // Advance
314 if (d >= 0) { x += xincr; d += aincr; }
315 else d += bincr;
316 }
317 }
318 // X based
319 else
320 {
321 yincr = (iToY > rY) ? +1 : -1; xincr = (iToX > rX) ? +1 : -1;
322 dx = Abs(val: iToX - rX); dy = Abs(val: iToY - rY);
323 d = 2 * dy - dx; aincr = 2 * (dy - dx); bincr = 2 * dy; x = rX; y = rY;
324 for (x = rX; x != iToX; x += xincr)
325 {
326 // Check point free
327 if (PointFree(iX: x, iY: y)) { rY = y; rX = x; }
328 else return false;
329 // Check transfer zone intersection
330 if (ppZone)
331 if (pPathFinder->TransferZonesEnabled)
332 if (pPathFinder->TransferZones)
333 if (*ppZone = pPathFinder->TransferZones->Find(iX: rX, iY: rY))
334 return false;
335 // Advance
336 if (d >= 0) { y += yincr; d += aincr; }
337 else d += bincr;
338 }
339 }
340
341 return true;
342}
343
344bool C4PathFinderRay::Crawl()
345{
346 // No attach: crawl failure (shouldn't ever get here)
347 if (!CrawlAttach)
348 return false;
349
350 // Last attach lost (don't check on first crawl for that might be a diagonal attach)
351 if (CrawlLength)
352 if (!IsCrawlAttach(iX: X2, iY: Y2, iAttach: CrawlAttach))
353 {
354 // Crawl corner by last attach
355 CrawlToAttach(rX&: X2, rY&: Y2, iAttach: CrawlAttach);
356 TurnAttach(rAttach&: CrawlAttach, iDirection: -Direction);
357 // Safety: new attach not found - unexpected failure
358 if (!IsCrawlAttach(iX: X2, iY: Y2, iAttach: CrawlAttach))
359 return false;
360 // Corner okay
361 return true;
362 }
363
364 // Check crawl target by attach
365 int32_t iTurned = 0;
366 while (!CrawlTargetFree(iX: X2, iY: Y2, iAttach: CrawlAttach, iDirection: Direction))
367 {
368 // Crawl target not free: turn attach
369 TurnAttach(rAttach&: CrawlAttach, iDirection: Direction); iTurned++;
370 // Turned four times: all enclosed, crawl failure
371 if (iTurned == 4)
372 return false;
373 }
374
375 // Crawl by attach
376 CrawlByAttach(rX&: X2, rY&: Y2, iAttach: CrawlAttach, iDirection: Direction);
377
378 // Success
379 return true;
380}
381
382void C4PathFinderRay::SetCompletePath()
383{
384 C4PathFinderRay *pRay;
385 // Back shorten
386 for (pRay = this; pRay->From; pRay = pRay->From)
387 while (pRay->CheckBackRayShorten());
388 // Set all waypoints
389 for (pRay = this; pRay->From; pRay = pRay->From)
390 {
391 // Transfer waypoint
392 if (pRay->UseZone)
393 pPathFinder->SetWaypoint(pRay->X2, pRay->Y2, reinterpret_cast<intptr_t>(pRay->UseZone->Object),
394 pPathFinder->WaypointParameter);
395 // MoveTo waypoint
396 else
397 pPathFinder->SetWaypoint(pRay->From->X2, pRay->From->Y2, 0,
398 pPathFinder->WaypointParameter);
399 }
400}
401
402bool C4PathFinderRay::PointFree(int32_t iX, int32_t iY)
403{
404 return pPathFinder->PointFree(iX, iY);
405}
406
407bool C4PathFinderRay::CrawlTargetFree(int32_t iX, int32_t iY, int32_t iAttach, int32_t iDirection)
408{
409 CrawlByAttach(rX&: iX, rY&: iY, iAttach, iDirection);
410 return PointFree(iX, iY);
411}
412
413void C4PathFinderRay::CrawlByAttach(int32_t &rX, int32_t &rY, int32_t iAttach, int32_t iDirection)
414{
415 switch (iAttach)
416 {
417 case C4PF_Crawl_Top: rX += iDirection; break;
418 case C4PF_Crawl_Bottom: rX -= iDirection; break;
419 case C4PF_Crawl_Left: rY -= iDirection; break;
420 case C4PF_Crawl_Right: rY += iDirection; break;
421 }
422}
423
424void C4PathFinderRay::TurnAttach(int32_t &rAttach, int32_t iDirection)
425{
426 rAttach += iDirection;
427 if (rAttach > C4PF_Crawl_Left) rAttach = C4PF_Crawl_Top;
428 if (rAttach < C4PF_Crawl_Top) rAttach = C4PF_Crawl_Left;
429}
430
431int32_t C4PathFinderRay::FindCrawlAttach(int32_t iX, int32_t iY)
432{
433 if (!PointFree(iX, iY: iY - 1)) return C4PF_Crawl_Top;
434 if (!PointFree(iX, iY: iY + 1)) return C4PF_Crawl_Bottom;
435 if (!PointFree(iX: iX - 1, iY)) return C4PF_Crawl_Left;
436 if (!PointFree(iX: iX + 1, iY)) return C4PF_Crawl_Right;
437 return C4PF_Crawl_NoAttach;
438}
439
440void C4PathFinderRay::CrawlToAttach(int32_t &rX, int32_t &rY, int32_t iAttach)
441{
442 switch (iAttach)
443 {
444 case C4PF_Crawl_Top: rY--; break;
445 case C4PF_Crawl_Bottom: rY++; break;
446 case C4PF_Crawl_Left: rX--; break;
447 case C4PF_Crawl_Right: rX++; break;
448 }
449}
450
451bool C4PathFinderRay::IsCrawlAttach(int32_t iX, int32_t iY, int32_t iAttach)
452{
453 CrawlToAttach(rX&: iX, rY&: iY, iAttach);
454 return !PointFree(iX, iY);
455}
456
457int32_t C4PathFinderRay::FindCrawlAttachDiagonal(int32_t iX, int32_t iY, int32_t iDirection)
458{
459 // Going left
460 if (iDirection == C4PF_Direction_Left)
461 {
462 // Top Left
463 if (!PointFree(iX: iX - 1, iY: iY - 1)) return C4PF_Crawl_Top;
464 // Bottom left
465 if (!PointFree(iX: iX - 1, iY: iY + 1)) return C4PF_Crawl_Left;
466 // Top right
467 if (!PointFree(iX: iX + 1, iY: iY - 1)) return C4PF_Crawl_Right;
468 // Bottom right
469 if (!PointFree(iX: iX + 1, iY: iY + 1)) return C4PF_Crawl_Bottom;
470 }
471 // Going right
472 if (iDirection == C4PF_Direction_Right)
473 {
474 // Top Left
475 if (!PointFree(iX: iX - 1, iY: iY - 1)) return C4PF_Crawl_Left;
476 // Bottom left
477 if (!PointFree(iX: iX - 1, iY: iY + 1)) return C4PF_Crawl_Bottom;
478 // Top right
479 if (!PointFree(iX: iX + 1, iY: iY - 1)) return C4PF_Crawl_Top;
480 // Bottom right
481 if (!PointFree(iX: iX + 1, iY: iY + 1)) return C4PF_Crawl_Right;
482 }
483 return C4PF_Crawl_NoAttach;
484}
485
486bool C4PathFinderRay::CheckBackRayShorten()
487{
488 C4PathFinderRay *pRay, *pRay2;
489 int32_t iX, iY;
490 for (pRay = From; pRay; pRay = pRay->From)
491 {
492 // Don't shorten transfer over zones
493 if (pRay->UseZone) return false;
494 // Skip self
495 if (pRay == From) continue;
496 // Check shortcut
497 iX = X; iY = Y;
498 if (PathFree(rX&: iX, rY&: iY, iToX: pRay->X, iToY: pRay->Y))
499 {
500 // Delete jumped rays
501 for (pRay2 = From; pRay2 != pRay; pRay2 = pRay2->From)
502 pRay2->Status = C4PF_Ray_Deleted;
503 // Shorten pRay to this
504 pRay->X2 = X; pRay->Y2 = Y;
505 From = pRay;
506 // Success
507 return true;
508 }
509 }
510 return false;
511}
512
513// C4PathFinder
514
515C4PathFinder::C4PathFinder()
516{
517 Default();
518}
519
520C4PathFinder::~C4PathFinder()
521{
522 Clear();
523}
524
525void C4PathFinder::Default()
526{
527 PointFree = nullptr;
528 SetWaypoint = nullptr;
529 FirstRay = nullptr;
530 WaypointParameter = 0;
531 Success = false;
532 TransferZones = nullptr;
533 TransferZonesEnabled = true;
534 Level = 1;
535}
536
537void C4PathFinder::Clear()
538{
539 C4PathFinderRay *pRay, *pNext;
540 for (pRay = FirstRay; pRay; pRay = pNext) { pNext = pRay->Next; delete pRay; }
541 FirstRay = nullptr;
542}
543
544void C4PathFinder::Init(bool(*fnPointFree)(int32_t, int32_t), C4TransferZones *pTransferZones)
545{
546 // Set data
547 PointFree = fnPointFree;
548 TransferZones = pTransferZones;
549}
550
551void C4PathFinder::EnableTransferZones(bool fEnabled)
552{
553 TransferZonesEnabled = fEnabled;
554}
555
556void C4PathFinder::SetLevel(int iLevel)
557{
558 Level = BoundBy(bval: iLevel, lbound: 1, rbound: 10);
559}
560
561void C4PathFinder::Draw(C4FacetEx &cgo)
562{
563 if (TransferZones) TransferZones->Draw(cgo);
564 for (C4PathFinderRay *pRay = FirstRay; pRay; pRay = pRay->Next) pRay->Draw(cgo);
565}
566
567void C4PathFinder::Run()
568{
569 if (TransferZones) TransferZones->ClearUsed();
570 Success = false;
571 while (!Success && Execute());
572 // Notice that ray zone-pointers might be invalid after run
573}
574
575bool C4PathFinder::Execute()
576{
577 // Execute & count rays
578 bool fContinue = false;
579 int32_t iRays = 0;
580 for (C4PathFinderRay *pRay = FirstRay; pRay && !Success; pRay = pRay->Next, iRays++)
581 if (pRay->Execute())
582 fContinue = true;
583
584 // Max ray limit
585 if (iRays >= C4PF_MaxRay) return false;
586
587 // Draw
588 if (Game.GraphicsSystem.ShowPathfinder)
589 {
590 static int32_t iDelay = 0;
591 iDelay++; if (iDelay > C4PF_Draw_Rate)
592 {
593 iDelay = 0;
594 Game.GraphicsSystem.Execute();
595 }
596 }
597
598 return fContinue;
599}
600
601bool C4PathFinder::Find(int32_t iFromX, int32_t iFromY, int32_t iToX, int32_t iToY, bool(*fnSetWaypoint)(int32_t, int32_t, intptr_t, intptr_t), intptr_t iWaypointParameter)
602{
603 // Prepare
604 Clear();
605
606 // Parameter safety
607 if (!fnSetWaypoint) return false;
608 SetWaypoint = fnSetWaypoint;
609 WaypointParameter = iWaypointParameter;
610
611 // Start & target coordinates must be free
612 if (!PointFree(iFromX, iFromY) || !PointFree(iToX, iToY)) return false;
613
614 // Add the first two rays
615 if (!AddRay(iFromX, iFromY, iToX, iToY, iDepth: 0, iDirection: C4PF_Direction_Left, pFrom: nullptr)) return false;
616 if (!AddRay(iFromX, iFromY, iToX, iToY, iDepth: 0, iDirection: C4PF_Direction_Right, pFrom: nullptr)) return false;
617
618 // Run
619 Run();
620
621 // Success
622 return Success;
623}
624
625bool C4PathFinder::AddRay(int32_t iFromX, int32_t iFromY, int32_t iToX, int32_t iToY, int32_t iDepth, int32_t iDirection, C4PathFinderRay *pFrom, C4TransferZone *pUseZone)
626{
627 // Max depth
628 if (iDepth >= C4PF_MaxDepth * Level) return false;
629 // Allocate and set new ray
630 auto ray = std::make_unique<C4PathFinderRay>();
631 ray->X = iFromX; ray->Y = iFromY;
632 ray->X2 = iFromX; ray->Y2 = iFromY;
633 ray->TargetX = iToX; ray->TargetY = iToY;
634 ray->Depth = iDepth;
635 ray->Direction = iDirection;
636 ray->From = pFrom;
637 ray->pPathFinder = this;
638 ray->Next = FirstRay;
639 ray->UseZone = pUseZone;
640 FirstRay = ray.release();
641 return true;
642}
643
644bool C4PathFinder::SplitRay(C4PathFinderRay *pRay, int32_t iAtX, int32_t iAtY)
645{
646 // Max depth
647 if (pRay->Depth >= C4PF_MaxDepth * Level) return false;
648 // Allocate and set new ray
649 auto newRay = std::make_unique<C4PathFinderRay>();
650 newRay->Status = C4PF_Ray_Still;
651 newRay->X = pRay->X; newRay->Y = pRay->Y;
652 newRay->X2 = iAtX; newRay->Y2 = iAtY;
653 newRay->TargetX = pRay->TargetX; newRay->TargetY = pRay->TargetY;
654 newRay->Depth = pRay->Depth;
655 newRay->Direction = pRay->Direction;
656 newRay->From = pRay->From;
657 newRay->pPathFinder = this;
658 newRay->Next = FirstRay;
659 FirstRay = newRay.get();
660 // Adjust split ray
661 pRay->From = newRay.release();
662 pRay->X = iAtX; pRay->Y = iAtY;
663 return true;
664}
665