1;----------------------------------------------------------------------------;
2; Does A* pathfinding for rockraiders and vehicles
3;
4; Copyright 2015 Ruben De Smet
5;
6; Redistribution and use in source and binary forms, with or without
7; modification, are permitted provided that the following conditions are
8; met:
9;
10;     (1) Redistributions of source code must retain the above copyright
11;         notice, this list of conditions and the following disclaimer.
12;
13;     (2) Redistributions in binary form must reproduce the above copyright
14;         notice, this list of conditions and the following disclaimer in
15;         the documentation and/or other materials provided with the
16;         distribution.
17;
18;     (3) The name of the author may not be used to
19;         endorse or promote products derived from this software without
20;         specific prior written permission.
21;
22; THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23; IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
24; WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
25; DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
26; INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
27; (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
28; SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29; HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
30; STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
31; IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32; POSSIBILITY OF SUCH DAMAGE.
33;
34;----------------------------------------------------------------------------;
35
36IDEAL
37P386
38MODEL FLAT, C
39ASSUME cs:_TEXT,ds:FLAT,es:FLAT,fs:FLAT,gs:FLAT
40
41INCLUDE "ASTAR.INC"
42INCLUDE "READLVL.INC"
43INCLUDE "DEBUG.INC"
44
45STRUC TPriorityField
46    heuristic dd ?
47    distance dd ?
48    x db ?
49    y db ?
50    fromx db ?
51    fromy db ?
52ENDS
53
54STRUC TField
55    distance dd ?
56    x db ?
57    y db ?
58ENDS
59
60CODESEG
61
62PROC getPath
63        USES ecx
64        ARG @@tgtx:dword, \
65            @@tgty:dword \
66        RETURNS eax, ebx ; eax contains x, ebx contains y
67
68        call getLevelWidth
69        imul eax, [@@tgty]
70        add eax, [@@tgtx]
71        imul eax, SIZE TField
72        add eax, offset backtraceGraph
73        mov ecx, eax
74
75        xor eax, eax
76        xor ebx, ebx
77
78        mov al, [(TField ptr ecx).x]
79        mov bl, [(TField ptr ecx).y]
80
81        ret
82ENDP getPath
83
84PROC findPath
85        ; eax will contain a 1 when a path has been found
86        ;                    0 otherwise.
87        ARG @@srcx:dword, \
88            @@srcy:dword, \
89            @@tgtx:dword, \
90            @@tgty:dword, \
91            @@type:dword \
92            RETURNS eax
93
94        ; Check whether the target field is "allowed" for
95        ; the selected vehicle or rock raider
96        call getField, [@@tgtx], [@@tgty]
97        mov al, [byte ptr eax]
98        and eax, 0FFh
99
100        add eax, offset actionTable
101        mov eax, [eax]
102        and eax, [@@type]               ; TODO: for now, rock raider is hard coded
103        jnz @canGoToTarget
104
105        mov eax, 0
106        ret
107@canGoToTarget:
108
109        call cleanData
110        mov eax, [@@type]
111        mov [currentType], eax
112
113        mov eax, [@@srcx]
114        mov [currentOpen.x], al
115        mov eax, [@@srcy]
116        mov [currentOpen.y], al
117
118        call distance, [@@srcx], [@@srcy], [@@tgtx], [@@tgty]
119        ; eax <- distance
120        call addOpen, [@@srcx], [@@srcy], eax, 0
121
122@openListNotEmpty:
123        call popOpen
124        cmp eax, 0
125        je @openListEmpty
126
127        call addToMap
128
129        call addClosed
130
131        mov eax, [@@tgtx]
132        cmp [currentOpen.x], al
133        jne @nextOpen
134        mov eax, [@@tgty]
135        cmp [currentOpen.y], al
136        jne @nextOpen
137
138        jmp @routeFound
139
140        @nextOpen:
141        call addNeighbours, [@@tgtx], [@@tgty]
142
143        jmp @openListNotEmpty
144
145@openListEmpty:
146        mov eax, 0
147        ret
148
149@routeFound:
150        mov eax, 1
151        ret
152ENDP findPath
153
154PROC addToMap
155        USES eax, ecx
156
157        call getLevelWidth
158        xor ecx, ecx
159        mov cl, [currentOpen.y]
160        imul eax, ecx
161        mov cl, [currentOpen.x]
162        add eax, ecx
163        imul eax, SIZE TField
164        add eax, offset backtraceGraph
165
166        mov ecx, [currentOpen.distance]
167        cmp [(TField ptr eax).distance], ecx
168        jbe @dontAdd
169
170        mov [(TField ptr eax).distance], ecx
171        mov cl, [currentOpen.fromx]
172        mov [(TField ptr eax).x], cl
173        mov cl, [currentOpen.fromy]
174        mov [(TField ptr eax).y], cl
175
176@dontAdd:
177        ret
178ENDP addToMap
179
180; Is closed checks whether the field considered is "closed" for being added to the open list.
181; So, it also checks whether we can go on the selected field.
182PROC isClosed
183        USES ebx, ecx, edx
184        ARG @@x:dword, \
185            @@y:dword RETURNS eax
186
187        ; Check bounds first:
188
189        call getLevelWidth
190        cmp [@@x], eax
191        ja notWithinBounds ; ja considers -1 > 10
192
193        call getLevelHeight
194        cmp [@@y], eax
195        ja notWithinBounds
196
197        ; Check whether this field is "allowed" for
198        ; the selected vehicle or rock raider
199        call getField, [@@x], [@@y]
200        mov al, [byte ptr eax]
201        and eax, 0FFh
202
203        add eax, offset actionTable
204        mov eax, [eax]
205        and eax, [currentType]               ; TODO: for now, rock raider is hard coded
206        jnz @canGoHere
207
208
209        inc eax ; mov eax, 1
210        ret
211
212@canGoHere:
213
214        ; Getting here means the field is okay to walk/fly/whatever on
215
216        xor ecx, ecx
217        mov cx, [closedlistSize]
218        cmp cx, 0 ; If empty, return 0
219        jne @closedNotEmpty
220
221        mov eax, 0
222        ret
223
224@closedNotEmpty:
225        mov ebx, offset closedlist
226
227@loopClosed:
228        mov edx, [@@x]
229        cmp [(TField ptr ebx).x], dl
230        jne @nextClosed
231        mov edx, [@@y]
232        cmp [(TField ptr ebx).y], dl
233        jne @nextClosed
234
235        ; If reached here, yep, contained in closed list
236        mov eax, 1
237        ret
238
239    @nextClosed:
240        add ebx, SIZE TField
241        dec ecx
242        jnz @loopClosed
243
244        mov eax, 0
245        ret
246
247notWithinBounds:
248        mov eax, 1
249        ret
250ENDP isClosed
251
252PROC addNeighbours
253        USES eax, ebx, ecx, edx
254        ARG @@tgtx:dword, \
255            @@tgty:dword
256        ; Push all neighbours of currentOpen on openList
257
258        xor ebx, ebx
259        xor ecx, ecx
260
261        mov bl, [currentOpen.x]
262        mov cl, [currentOpen.y]
263        mov edx, [currentOpen.distance]
264        inc edx ; Next distance is one more.
265
266        ; Up
267        dec ecx
268        call isClosed, ebx, ecx
269        cmp eax, 0
270        jne @noUp
271        call distance, ebx, ecx, [@@tgtx], [@@tgty]
272        add eax, edx
273        call addOpen, ebx, ecx, eax, edx
274        @noUp:
275        inc ecx
276
277        ; Right
278        inc ebx
279        call isClosed, ebx, ecx
280        cmp eax, 0
281        jne @noRight
282        call distance, ebx, ecx, [@@tgtx], [@@tgty]
283        add eax, edx
284        call addOpen, ebx, ecx, eax, edx
285        @noRight:
286        dec ebx
287
288        ; Left
289        dec ebx
290        call isClosed, ebx, ecx
291        cmp eax, 0
292        jne @noLeft
293        call distance, ebx, ecx, [@@tgtx], [@@tgty]
294        add eax, edx
295        call addOpen, ebx, ecx, eax, edx
296        @noLeft:
297        inc ebx
298
299        ; Down
300        inc ecx
301        call isClosed, ebx, ecx
302        cmp eax, 0
303        jne @noDown
304        call distance, ebx, ecx, [@@tgtx], [@@tgty]
305        add eax, edx
306        call addOpen, ebx, ecx, eax, edx
307        @noDown:
308        dec ecx
309
310        ret
311ENDP addNeighbours
312
313PROC popOpen
314        ARG RETURNS eax
315        USES ebx, ecx, edx, esi, edi
316        ; eax contains the smallest current heuristic
317        ; ebx contains the index of that field
318
319        cmp [openlistSize], 0           ; If empty, return 0
320        jne @goForth
321
322        mov eax, 0
323        ret
324
325@goForth:
326
327        mov eax, 0FFFFFFFFh             ; Longest distance possible in 32 bits.
328        xor ebx, ebx
329        xor ecx, ecx                    ; ecx contains the current index
330
331@searchFurther:
332        mov edx, ecx
333        imul edx, SIZE TPriorityField
334        cmp [(TPriorityField ptr (openlist + edx)).heuristic], eax
335        ja @notBetter
336        ; Better guess found, put right values in eax and ebx
337        mov eax, [(TPriorityField ptr (openlist + edx)).heuristic]
338        mov ebx, ecx
339
340@notBetter:
341
342        inc ecx
343        cmp cx, [openlistSize]
344        jne @searchFurther
345
346        ; By now, we have found the right item to pop from the priorityqueue.
347
348        ; Move the correct item in currentOpen
349        mov ecx, SIZE TPriorityField
350        mov esi, ebx
351        imul esi, ecx
352        add esi, offset openlist
353
354        mov edi, offset currentOpen
355        rep movsb
356
357        ; Now make the remove the thing from the vector
358
359        xor ecx, ecx
360        mov cx, [openlistSize]
361        sub ecx, ebx
362        dec ecx
363        imul ecx, SIZE TPriorityField
364        mov edi, esi
365        sub edi, SIZE TPriorityField
366        rep movsb
367
368        dec [openlistSize]
369        mov eax, 1
370        ret
371ENDP popOpen
372
373PROC addClosed
374        USES eax, ebx
375
376        xor ebx, ebx
377        xor eax, eax
378
379        mov bx, [closedlistSize]
380        imul ebx, SIZE TField
381        add ebx, offset closedlist ; ebx contains the target TField
382
383        mov al, [currentOpen.x]
384        mov [(TField ptr ebx).x], al
385        mov al, [currentOpen.y]
386        mov [(TField ptr ebx).y], al
387        mov eax, [currentOpen.distance]
388        mov [(TField ptr ebx).distance], eax
389
390        inc [closedlistSize]
391        cmp [closedlistSize], CLOSED_LIST_SIZE_MAX
392        jne @noProblemWithClosedVector
393
394        xor eax, eax
395        mov ax, [closedlistSize]
396        call crash, offset closedOutOfMemory, eax
397
398@noProblemWithClosedVector:
399        ret
400ENDP addClosed
401
402PROC addOpen
403        USES eax, ebx
404        ARG @@x:dword, \
405            @@y:dword, \
406            @@priority:dword, \
407            @@distance:dword
408
409        xor eax, eax
410        mov ax, [openlistSize]
411        imul eax, SIZE TPriorityField
412        add eax, offset openlist
413
414        mov ebx, [@@x]
415        mov [(TPriorityField ptr eax).x], bl
416        mov ebx, [@@y]
417        mov [(TPriorityField ptr eax).y], bl
418
419        mov bl, [currentOpen.x]
420        mov [(TPriorityField ptr eax).fromx], bl
421        mov bl, [currentOpen.y]
422        mov [(TPriorityField ptr eax).fromy], bl
423
424        mov ebx, [@@priority]
425        mov [(TPriorityField ptr eax).heuristic], ebx
426        mov ebx, [@@distance]
427        mov [(TPriorityField ptr eax).distance], ebx
428
429        inc [openlistSize]
430        cmp [openlistSize], OPEN_LIST_SIZE_MAX
431        jne @noProblem
432
433        xor eax, eax
434        mov ax, [openlistSize]
435        call crash, offset openOutOfMemory, eax
436
437@noProblem:
438        ret
439ENDP
440
441PROC distance
442        USES ebx
443        ARG @@srcx:dword, \
444            @@srcy:dword, \
445            @@tgtx:dword, \
446            @@tgty:dword \
447        RETURNS eax
448
449        mov eax, [@@srcx]
450        sub eax, [@@tgtx]
451
452        jns @noSignChangex
453        neg eax
454
455        @noSignChangex:
456
457        mov ebx, [@@srcy]
458        sub ebx, [@@tgty]
459
460        jns @noSignChangey
461        neg ebx
462
463        @noSignChangey:
464        add eax, ebx
465        ret
466ENDP distance
467
468PROC cleanData
469        USES eax, ecx
470        mov [openlistSize], 0
471        mov [closedlistSize], 0
472
473        mov [currentOpen.x], -1
474        mov [currentOpen.y], -1
475        mov [currentOpen.distance], 0
476
477        call getLevelWidth
478        mov ecx, eax
479        call getLevelHeight
480        imul ecx, eax
481
482        mov eax, offset backtraceGraph
483@fieldIter:
484        mov [(TField ptr eax).distance], 0ffffffffh ; Set to approximately +inf
485        mov [(TField ptr eax).x], 0
486        mov [(TField ptr eax).y], 0
487        add eax, SIZE TField
488        dec ecx
489        jnz @fieldIter
490
491        ret
492ENDP cleanData
493
494DATASEG
495
496openOutOfMemory   db "Out of openlistSize memory. Hi dev: Please increase$"
497closedOutOfMemory db "Out of closedlistSize memory. Hi dev: Please increase$"
498
499; power | discover | walking | sailing | flying
500actionTable db  00001101b, \ ;EMPTY
501                00001101b, \ ;RUBBLE
502                00000000b, \ ;GRAVEL
503                00000000b, \ ;LOOSE ROCK
504                00000000b, \ ;HARD ROCK
505                00000000b, \ ;MASSIVE ROCK
506                00000000b, \ ;KRISTAL SOURCE
507                00000000b, \ ;OREROCK
508                00001011b, \ ;WATER
509                00001001b, \ ;LAVA
510                00001101b, \ ;SNAIL HOLE
511                00001101b, \ ;EROSION
512                00011101b, \ ;POWER PATH
513                00011101b, \ ;BUILDING POWER PATH
514                00011000b  \ ;BUILDING
515
516UDATASEG
517
518currentType      dd ?
519currentOpen      TPriorityField ?
520
521openlist         TPriorityField OPEN_LIST_SIZE_MAX dup(?)
522openlistSize     dw ?
523closedlist       TField CLOSED_LIST_SIZE_MAX       dup(?)
524closedlistSize   dw ?
525backtraceGraph   TField MAX_LEVEL_SIZE             dup(?)
526
527END
528