527 lines
13 KiB
TASM
527 lines
13 KiB
TASM
;----------------------------------------------------------------------------;
|
|
; Does A* pathfinding for rockraiders and vehicles
|
|
;
|
|
; Copyright 2015 Ruben De Smet
|
|
;
|
|
; Redistribution and use in source and binary forms, with or without
|
|
; modification, are permitted provided that the following conditions are
|
|
; met:
|
|
;
|
|
; (1) Redistributions of source code must retain the above copyright
|
|
; notice, this list of conditions and the following disclaimer.
|
|
;
|
|
; (2) Redistributions in binary form must reproduce the above copyright
|
|
; notice, this list of conditions and the following disclaimer in
|
|
; the documentation and/or other materials provided with the
|
|
; distribution.
|
|
;
|
|
; (3) The name of the author may not be used to
|
|
; endorse or promote products derived from this software without
|
|
; specific prior written permission.
|
|
;
|
|
; THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
|
; IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
|
; WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
|
; DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
|
|
; INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
|
; (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
|
; SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
|
; HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
|
; STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
|
|
; IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
|
|
; POSSIBILITY OF SUCH DAMAGE.
|
|
;
|
|
;----------------------------------------------------------------------------;
|
|
|
|
IDEAL
|
|
P386
|
|
MODEL FLAT, C
|
|
ASSUME cs:_TEXT,ds:FLAT,es:FLAT,fs:FLAT,gs:FLAT
|
|
|
|
INCLUDE "ASTAR.INC"
|
|
INCLUDE "READLVL.INC"
|
|
INCLUDE "DEBUG.INC"
|
|
|
|
STRUC TPriorityField
|
|
heuristic dd ?
|
|
distance dd ?
|
|
x db ?
|
|
y db ?
|
|
fromx db ?
|
|
fromy db ?
|
|
ENDS
|
|
|
|
STRUC TField
|
|
distance dd ?
|
|
x db ?
|
|
y db ?
|
|
ENDS
|
|
|
|
CODESEG
|
|
|
|
PROC getPath
|
|
USES ecx
|
|
ARG @@tgtx:dword, \
|
|
@@tgty:dword \
|
|
RETURNS eax, ebx ; eax contains x, ebx contains y
|
|
|
|
call getLevelWidth
|
|
imul eax, [@@tgty]
|
|
add eax, [@@tgtx]
|
|
imul eax, SIZE TField
|
|
add eax, offset backtraceGraph
|
|
mov ecx, eax
|
|
|
|
xor eax, eax
|
|
xor ebx, ebx
|
|
|
|
mov al, [(TField ptr ecx).x]
|
|
mov bl, [(TField ptr ecx).y]
|
|
|
|
ret
|
|
ENDP getPath
|
|
|
|
PROC findPath
|
|
; eax will contain a 1 when a path has been found
|
|
; 0 otherwise.
|
|
ARG @@srcx:dword, \
|
|
@@srcy:dword, \
|
|
@@tgtx:dword, \
|
|
@@tgty:dword, \
|
|
@@type:dword \
|
|
RETURNS eax
|
|
|
|
; Check whether the target field is "allowed" for
|
|
; the selected vehicle or rock raider
|
|
call getField, [@@tgtx], [@@tgty]
|
|
mov al, [byte ptr eax]
|
|
and eax, 0FFh
|
|
|
|
add eax, offset actionTable
|
|
mov eax, [eax]
|
|
and eax, [@@type] ; TODO: for now, rock raider is hard coded
|
|
jnz @canGoToTarget
|
|
|
|
mov eax, 0
|
|
ret
|
|
@canGoToTarget:
|
|
|
|
call cleanData
|
|
mov eax, [@@type]
|
|
mov [currentType], eax
|
|
|
|
mov eax, [@@srcx]
|
|
mov [currentOpen.x], al
|
|
mov eax, [@@srcy]
|
|
mov [currentOpen.y], al
|
|
|
|
call distance, [@@srcx], [@@srcy], [@@tgtx], [@@tgty]
|
|
; eax <- distance
|
|
call addOpen, [@@srcx], [@@srcy], eax, 0
|
|
|
|
@openListNotEmpty:
|
|
call popOpen
|
|
cmp eax, 0
|
|
je @openListEmpty
|
|
|
|
call addToMap
|
|
|
|
call addClosed
|
|
|
|
mov eax, [@@tgtx]
|
|
cmp [currentOpen.x], al
|
|
jne @nextOpen
|
|
mov eax, [@@tgty]
|
|
cmp [currentOpen.y], al
|
|
jne @nextOpen
|
|
|
|
jmp @routeFound
|
|
|
|
@nextOpen:
|
|
call addNeighbours, [@@tgtx], [@@tgty]
|
|
|
|
jmp @openListNotEmpty
|
|
|
|
@openListEmpty:
|
|
mov eax, 0
|
|
ret
|
|
|
|
@routeFound:
|
|
mov eax, 1
|
|
ret
|
|
ENDP findPath
|
|
|
|
PROC addToMap
|
|
USES eax, ecx
|
|
|
|
call getLevelWidth
|
|
xor ecx, ecx
|
|
mov cl, [currentOpen.y]
|
|
imul eax, ecx
|
|
mov cl, [currentOpen.x]
|
|
add eax, ecx
|
|
imul eax, SIZE TField
|
|
add eax, offset backtraceGraph
|
|
|
|
mov ecx, [currentOpen.distance]
|
|
cmp [(TField ptr eax).distance], ecx
|
|
jbe @dontAdd
|
|
|
|
mov [(TField ptr eax).distance], ecx
|
|
mov cl, [currentOpen.fromx]
|
|
mov [(TField ptr eax).x], cl
|
|
mov cl, [currentOpen.fromy]
|
|
mov [(TField ptr eax).y], cl
|
|
|
|
@dontAdd:
|
|
ret
|
|
ENDP addToMap
|
|
|
|
; Is closed checks whether the field considered is "closed" for being added to the open list.
|
|
; So, it also checks whether we can go on the selected field.
|
|
PROC isClosed
|
|
USES ebx, ecx, edx
|
|
ARG @@x:dword, \
|
|
@@y:dword RETURNS eax
|
|
|
|
; Check bounds first:
|
|
|
|
call getLevelWidth
|
|
cmp [@@x], eax
|
|
ja notWithinBounds ; ja considers -1 > 10
|
|
|
|
call getLevelHeight
|
|
cmp [@@y], eax
|
|
ja notWithinBounds
|
|
|
|
; Check whether this field is "allowed" for
|
|
; the selected vehicle or rock raider
|
|
call getField, [@@x], [@@y]
|
|
mov al, [byte ptr eax]
|
|
and eax, 0FFh
|
|
|
|
add eax, offset actionTable
|
|
mov eax, [eax]
|
|
and eax, [currentType] ; TODO: for now, rock raider is hard coded
|
|
jnz @canGoHere
|
|
|
|
|
|
inc eax ; mov eax, 1
|
|
ret
|
|
|
|
@canGoHere:
|
|
|
|
; Getting here means the field is okay to walk/fly/whatever on
|
|
|
|
xor ecx, ecx
|
|
mov cx, [closedlistSize]
|
|
cmp cx, 0 ; If empty, return 0
|
|
jne @closedNotEmpty
|
|
|
|
mov eax, 0
|
|
ret
|
|
|
|
@closedNotEmpty:
|
|
mov ebx, offset closedlist
|
|
|
|
@loopClosed:
|
|
mov edx, [@@x]
|
|
cmp [(TField ptr ebx).x], dl
|
|
jne @nextClosed
|
|
mov edx, [@@y]
|
|
cmp [(TField ptr ebx).y], dl
|
|
jne @nextClosed
|
|
|
|
; If reached here, yep, contained in closed list
|
|
mov eax, 1
|
|
ret
|
|
|
|
@nextClosed:
|
|
add ebx, SIZE TField
|
|
dec ecx
|
|
jnz @loopClosed
|
|
|
|
mov eax, 0
|
|
ret
|
|
|
|
notWithinBounds:
|
|
mov eax, 1
|
|
ret
|
|
ENDP isClosed
|
|
|
|
PROC addNeighbours
|
|
USES eax, ebx, ecx, edx
|
|
ARG @@tgtx:dword, \
|
|
@@tgty:dword
|
|
; Push all neighbours of currentOpen on openList
|
|
|
|
xor ebx, ebx
|
|
xor ecx, ecx
|
|
|
|
mov bl, [currentOpen.x]
|
|
mov cl, [currentOpen.y]
|
|
mov edx, [currentOpen.distance]
|
|
inc edx ; Next distance is one more.
|
|
|
|
; Up
|
|
dec ecx
|
|
call isClosed, ebx, ecx
|
|
cmp eax, 0
|
|
jne @noUp
|
|
call distance, ebx, ecx, [@@tgtx], [@@tgty]
|
|
add eax, edx
|
|
call addOpen, ebx, ecx, eax, edx
|
|
@noUp:
|
|
inc ecx
|
|
|
|
; Right
|
|
inc ebx
|
|
call isClosed, ebx, ecx
|
|
cmp eax, 0
|
|
jne @noRight
|
|
call distance, ebx, ecx, [@@tgtx], [@@tgty]
|
|
add eax, edx
|
|
call addOpen, ebx, ecx, eax, edx
|
|
@noRight:
|
|
dec ebx
|
|
|
|
; Left
|
|
dec ebx
|
|
call isClosed, ebx, ecx
|
|
cmp eax, 0
|
|
jne @noLeft
|
|
call distance, ebx, ecx, [@@tgtx], [@@tgty]
|
|
add eax, edx
|
|
call addOpen, ebx, ecx, eax, edx
|
|
@noLeft:
|
|
inc ebx
|
|
|
|
; Down
|
|
inc ecx
|
|
call isClosed, ebx, ecx
|
|
cmp eax, 0
|
|
jne @noDown
|
|
call distance, ebx, ecx, [@@tgtx], [@@tgty]
|
|
add eax, edx
|
|
call addOpen, ebx, ecx, eax, edx
|
|
@noDown:
|
|
dec ecx
|
|
|
|
ret
|
|
ENDP addNeighbours
|
|
|
|
PROC popOpen
|
|
ARG RETURNS eax
|
|
USES ebx, ecx, edx, esi, edi
|
|
; eax contains the smallest current heuristic
|
|
; ebx contains the index of that field
|
|
|
|
cmp [openlistSize], 0 ; If empty, return 0
|
|
jne @goForth
|
|
|
|
mov eax, 0
|
|
ret
|
|
|
|
@goForth:
|
|
|
|
mov eax, 0FFFFFFFFh ; Longest distance possible in 32 bits.
|
|
xor ebx, ebx
|
|
xor ecx, ecx ; ecx contains the current index
|
|
|
|
@searchFurther:
|
|
mov edx, ecx
|
|
imul edx, SIZE TPriorityField
|
|
cmp [(TPriorityField ptr (openlist + edx)).heuristic], eax
|
|
ja @notBetter
|
|
; Better guess found, put right values in eax and ebx
|
|
mov eax, [(TPriorityField ptr (openlist + edx)).heuristic]
|
|
mov ebx, ecx
|
|
|
|
@notBetter:
|
|
|
|
inc ecx
|
|
cmp cx, [openlistSize]
|
|
jne @searchFurther
|
|
|
|
; By now, we have found the right item to pop from the priorityqueue.
|
|
|
|
; Move the correct item in currentOpen
|
|
mov ecx, SIZE TPriorityField
|
|
mov esi, ebx
|
|
imul esi, ecx
|
|
add esi, offset openlist
|
|
|
|
mov edi, offset currentOpen
|
|
rep movsb
|
|
|
|
; Now make the remove the thing from the vector
|
|
|
|
xor ecx, ecx
|
|
mov cx, [openlistSize]
|
|
sub ecx, ebx
|
|
dec ecx
|
|
imul ecx, SIZE TPriorityField
|
|
mov edi, esi
|
|
sub edi, SIZE TPriorityField
|
|
rep movsb
|
|
|
|
dec [openlistSize]
|
|
mov eax, 1
|
|
ret
|
|
ENDP popOpen
|
|
|
|
PROC addClosed
|
|
USES eax, ebx
|
|
|
|
xor ebx, ebx
|
|
xor eax, eax
|
|
|
|
mov bx, [closedlistSize]
|
|
imul ebx, SIZE TField
|
|
add ebx, offset closedlist ; ebx contains the target TField
|
|
|
|
mov al, [currentOpen.x]
|
|
mov [(TField ptr ebx).x], al
|
|
mov al, [currentOpen.y]
|
|
mov [(TField ptr ebx).y], al
|
|
mov eax, [currentOpen.distance]
|
|
mov [(TField ptr ebx).distance], eax
|
|
|
|
inc [closedlistSize]
|
|
cmp [closedlistSize], CLOSED_LIST_SIZE_MAX
|
|
jne @noProblemWithClosedVector
|
|
|
|
xor eax, eax
|
|
mov ax, [closedlistSize]
|
|
call crash, offset closedOutOfMemory, eax
|
|
|
|
@noProblemWithClosedVector:
|
|
ret
|
|
ENDP addClosed
|
|
|
|
PROC addOpen
|
|
USES eax, ebx
|
|
ARG @@x:dword, \
|
|
@@y:dword, \
|
|
@@priority:dword, \
|
|
@@distance:dword
|
|
|
|
xor eax, eax
|
|
mov ax, [openlistSize]
|
|
imul eax, SIZE TPriorityField
|
|
add eax, offset openlist
|
|
|
|
mov ebx, [@@x]
|
|
mov [(TPriorityField ptr eax).x], bl
|
|
mov ebx, [@@y]
|
|
mov [(TPriorityField ptr eax).y], bl
|
|
|
|
mov bl, [currentOpen.x]
|
|
mov [(TPriorityField ptr eax).fromx], bl
|
|
mov bl, [currentOpen.y]
|
|
mov [(TPriorityField ptr eax).fromy], bl
|
|
|
|
mov ebx, [@@priority]
|
|
mov [(TPriorityField ptr eax).heuristic], ebx
|
|
mov ebx, [@@distance]
|
|
mov [(TPriorityField ptr eax).distance], ebx
|
|
|
|
inc [openlistSize]
|
|
cmp [openlistSize], OPEN_LIST_SIZE_MAX
|
|
jne @noProblem
|
|
|
|
xor eax, eax
|
|
mov ax, [openlistSize]
|
|
call crash, offset openOutOfMemory, eax
|
|
|
|
@noProblem:
|
|
ret
|
|
ENDP
|
|
|
|
PROC distance
|
|
USES ebx
|
|
ARG @@srcx:dword, \
|
|
@@srcy:dword, \
|
|
@@tgtx:dword, \
|
|
@@tgty:dword \
|
|
RETURNS eax
|
|
|
|
mov eax, [@@srcx]
|
|
sub eax, [@@tgtx]
|
|
|
|
jns @noSignChangex
|
|
neg eax
|
|
|
|
@noSignChangex:
|
|
|
|
mov ebx, [@@srcy]
|
|
sub ebx, [@@tgty]
|
|
|
|
jns @noSignChangey
|
|
neg ebx
|
|
|
|
@noSignChangey:
|
|
add eax, ebx
|
|
ret
|
|
ENDP distance
|
|
|
|
PROC cleanData
|
|
USES eax, ecx
|
|
mov [openlistSize], 0
|
|
mov [closedlistSize], 0
|
|
|
|
mov [currentOpen.x], -1
|
|
mov [currentOpen.y], -1
|
|
mov [currentOpen.distance], 0
|
|
|
|
call getLevelWidth
|
|
mov ecx, eax
|
|
call getLevelHeight
|
|
imul ecx, eax
|
|
|
|
mov eax, offset backtraceGraph
|
|
@fieldIter:
|
|
mov [(TField ptr eax).distance], 0ffffffffh ; Set to approximately +inf
|
|
mov [(TField ptr eax).x], 0
|
|
mov [(TField ptr eax).y], 0
|
|
add eax, SIZE TField
|
|
dec ecx
|
|
jnz @fieldIter
|
|
|
|
ret
|
|
ENDP cleanData
|
|
|
|
DATASEG
|
|
|
|
openOutOfMemory db "Out of openlistSize memory. Hi dev: Please increase$"
|
|
closedOutOfMemory db "Out of closedlistSize memory. Hi dev: Please increase$"
|
|
|
|
; power | discover | walking | sailing | flying
|
|
actionTable db 00001101b, \ ;EMPTY
|
|
00001101b, \ ;RUBBLE
|
|
00000000b, \ ;GRAVEL
|
|
00000000b, \ ;LOOSE ROCK
|
|
00000000b, \ ;HARD ROCK
|
|
00000000b, \ ;MASSIVE ROCK
|
|
00000000b, \ ;KRISTAL SOURCE
|
|
00000000b, \ ;OREROCK
|
|
00001011b, \ ;WATER
|
|
00001001b, \ ;LAVA
|
|
00001101b, \ ;SNAIL HOLE
|
|
00001101b, \ ;EROSION
|
|
00011101b, \ ;POWER PATH
|
|
00011101b, \ ;BUILDING POWER PATH
|
|
00011000b \ ;BUILDING
|
|
|
|
UDATASEG
|
|
|
|
currentType dd ?
|
|
currentOpen TPriorityField ?
|
|
|
|
openlist TPriorityField OPEN_LIST_SIZE_MAX dup(?)
|
|
openlistSize dw ?
|
|
closedlist TField CLOSED_LIST_SIZE_MAX dup(?)
|
|
closedlistSize dw ?
|
|
backtraceGraph TField MAX_LEVEL_SIZE dup(?)
|
|
|
|
END
|