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