Omnimaga

Calculator Community => TI Calculators => ASM => Topic started by: ZippyDee on December 02, 2013, 04:47:39 pm

Title: [ASM] Help!! Diagonal backtracking through fixed-mem BFS pathfinding search?
Post by: ZippyDee on December 02, 2013, 04:47:39 pm

After many months, Hello! I am back with a question!

I have written an implementation of a Breadth First Search algorithm that doesn't use queues or stacks to search for the goal node, and instead uses fixed buffers! I have the search written, and now I'm writing the backtracking part of it to find a path from the goal back to the start node.

THE ALGORITHM:
The implementation uses three bit-mapped 128 byte buffers to represent a 32x32 map. These buffers are contiguous in RAM.
(listed in order)
b_tilemap: each bit represents whether a tile is walkable or not. 0 = empty, 1 = wall.
b_closed: each bit represents whether this node has been visited or not by the search algorithm
b_nodes: each bit represents the value assigned to the node when it was visited. This value is used for backtracking, and this is why the algorithm is interesting!


When the routine starts, the bit of the starting node in b_closed is set. Each iteration of the search passes over the entire buffer. Every bit in the b_closed buffer is "expanded" into each of the 4 adjacent bits that are not walls in b_tilemap. Any newly expanded bits that were not already set in the b_closed buffer are assigned a value of either 1 or 0 in the b_nodes buffer. This value is the same for every new bit expanded during the iteration. After each pass, the bit of the goal node is tested in b_closed. If it is set, we know the goal node has been visited, so we can now backtrack from here to the start by following our b_nodes values!

The assigned b_nodes value follows the pattern 0, 1, 1, 0, 0, 1, 1, 0, etc, changing each iteration to the next value in the pattern. This is the key to this algorithm. At any given index in this pattern, the previous and next indices always have different values. With a reference of the current value and either the next value or the previous value in the pattern, the third value can always be determined.

You can walk a path by walking to adjacent nodes that match the next value in the pattern.

Obviously from the starting node every possible route follows this pattern, because it all expanded from that point. However, if we follow the pattern in the reverse direction from where we ended, it will always lead us from the goal back to the start. There may be multiple paths, but, if so, all paths will be the same length, so it doesn't matter which path is taken.

The backtracked path is the only part of this algorithm that uses variable memory, because we obviously can't know how long the path is until we've found it!


I HOPE THAT ALL MAKES SENSE... O.O If not, I would love to clarify.

//EDIT: PICTURES!
(http://i.imgur.com/AXQksuD.gif)
Here you can see that it expands every possible node each pass. The value assigned follows the pattern I described. Once the goal is found, you can follow the pattern in reverse to find your way back.

That was the path I chose to follow, but any of these paths would be valid, because they all follow the pattern:
(http://i.imgur.com/GB8PdkD.png)(http://i.imgur.com/7SutSIR.png)(http://i.imgur.com/FGCkaXg.png)(http://i.imgur.com/hBRt0nL.png)(http://i.imgur.com/6ODlCia.png)(http://i.imgur.com/XQHWq49.png)
Note that they are all the exact same length. So technically the set of valid tiles to move to is:
(http://i.imgur.com/prK9fkO.png)

THE PROBLEM:
This algorithm is designed to do a search in 4 directions only, however I realized that backtracking correctly can produce an 8-directional path, which I would greatly prefer. Note that any time it has multiple possible paths, all options will produce the same length of 4-directional path, so any time you can move diagonally is ALWAYS an improvement. The algorithm should always try to move in a straight line, unless it has the option to move diagonally (and is not moving diagonally in a different direction already, of course). This creates the most efficient paths with 8-directional movement and accounts for the possibility that changing direction has a cost (such as enemies having to turn to face a new direction before moving that way).

The way I thought of to implement diagonal movement is to compare the "options" from the previous node in the path with the "options of the current one. For example, let's say at node A you can move either right or down, so you choose to move right and add that node to the backtracked path. Now at node B you can move either right, down, or up. Well if you compare with the valid directions at A, you can see that down was valid for node A, too! That means the node diagonally down-right from A is valid and not blocked by any walls or corners! So instead of adding a new node to the backtracked path, we just change the last node we added to be right-down from A, instead of just right.

//EDIT: The returned path can be quite small if represented by a series of directions 0-7. The layout I have for this is 0=right, going counter-clockwise around the directions (1=up-right, 2=up, 3=up-left, etc). It's easy to expand any format of directions like that into an X and Y offset using a couple of LUTs.

Does that make sense as well? I hope so, because the question is...

How do you do that efficiently? All of it. What's the most efficient way to check the 4-directional surrounding bits recursively like that? Am I missing a more efficient way to check diagonal pathing? I just can't come up with a way to write this backtracking that I feel is very efficient.

Thanks so much for any input! I'll clarify anything that is confusing if need be!

-Taw

Title: Re: [ASM] Help!! Diagonal backtracking through fixed-mem BFS pathfinding search?
Post by: chickendude on December 03, 2013, 09:49:07 am

I'm trying to follow but i'm not entirely sure i get it. Rather than using full bytes you're storing 8 entries per byte, no? I'm not sure how you plan to store the direction (0-7), using nibbles/a full byte would take up a lot more room.

The implementation uses three bit-mapped 128 byte buffers to represent a 32x32 map. These buffers are contiguous in RAM.
(listed in order)
b_tilemap: each bit represents whether a tile is walkable or not. 0 = empty, 1 = wall.
b_closed: each bit represents whether this node has been visited or not by the search algorithm

Quote

b_nodes: each bit represents the value assigned to the node when it was visited. This value is used for backtracking, and this is why the algorithm is interesting!

This is also the part i don't quite get. How do you determine which value to give it?

Quote

When the routine starts, the bit of the starting node in b_closed is set. Each iteration of the search passes over the entire buffer. Every bit in the b_closed buffer is "expanded" into each of the 4 adjacent bits that are not walls in b_tilemap.

So you essentially mark the starting location as closed, then what? Is everything (the four adjacent bits/tiles) marked as "visited"? I'm not sure how you keep track of where active paths are.

Quote

Any newly expanded bits that were not already set in the b_closed buffer are assigned a value of either 1 or 0 in the b_nodes buffer. This value is the same for every new bit expanded during the iteration. After each pass, the bit of the goal node is tested in b_closed. If it is set, we know the goal node has been visited, so we can now backtrack from here to the start by following our b_nodes values!

How do you determine whether it's a 1 or a 0?

Quote

The assigned b_nodes value follows the pattern 0, 1, 1, 0, 0, 1, 1, 0, etc, changing each iteration to the next value in the pattern. This is the key to this algorithm. At any given index in this pattern, the previous and next indices always have different values. With a reference of the current value and either the next value or the previous value in the pattern, the third value can always be determined

It sounds interesting, but i think an example would be really helpful to see what exactly's going on :D

For diagonal moves, would it not work just expanding the initial search to the 8 surrounding tiles (and checking the 8 surrounding tiles when tracing back)?

Title: Re: [ASM] Help!! Diagonal backtracking through fixed-mem BFS pathfinding search?
Post by: ZippyDee on December 03, 2013, 08:46:04 pm

The 01100110011 pattern is the value assigned to the bit in b_nodes.

You mark the starting location as closed. Then EVERYTHING that is closed so far is expanded into the surrounding nodes that aren't closed yet. Each of those are then marked as closed and given the current pattern value.

Each pass over the buffer the value is either a 1 or a 0. Every bit expanded during that pass is assigned the same value. The value then changes for the next pass to the next value in the pattern.

This doesn't work for diagonal movement because of the pattern. That pattern only works for 4-directional movement. There may be multiple paths found to the goal, but all of them will have the same length, so it doesn't matter which one you choose.

I'll make some pictures to illustrate the concept.


PICTURES:
(http://i.imgur.com/AXQksuD.gif)
Here you can see that it expands every possible node each pass. The value assigned follows the pattern I described. Once the goal is found, you can follow the pattern in reverse to find your way back.

That was the path I chose to follow, but any of these paths would be valid, because they all follow the pattern:
(http://i.imgur.com/GB8PdkD.png)(http://i.imgur.com/7SutSIR.png)(http://i.imgur.com/FGCkaXg.png)(http://i.imgur.com/hBRt0nL.png)(http://i.imgur.com/6ODlCia.png)(http://i.imgur.com/XQHWq49.png)
Note that they are all the exact same length. So technically the set of valid tiles to move to is:
(http://i.imgur.com/prK9fkO.png)

EDIT: I put the pictures in the first post as well

Title: Re: [ASM] Help!! Diagonal backtracking through fixed-mem BFS pathfinding search?
Post by: chickendude on December 04, 2013, 03:54:20 pm

Ok, i think i get it now. Thanks :) I just wrote a little program (see the screenshots). But i haven't switched over to using bits, i've got it all set up using one byte per tile per array (using bits has to be a pain, have you written it already?). I also couldn't think of a way to avoid checking bytes that were closed multiple times, so i changed their value to 2 once i processed them. I also ran into an issue with adding values to the closed array and processing them in the same iteration, so i ended up running through the the array first and storing the values (well, pushing them onto the stack) that i needed to process and then processing them afterwards.

Ok... so now that i've actually figured out (mostly) what it is you're talking about, what exactly is giving you trouble? Writing the backtracking portion? Or is that ok, just working with bits is complicating things?

Spoiler For source:

Code: [Select]

WIDTH = 15
HEIGHT = 8
SIZE = WIDTH*HEIGHT
TILE = 0
CLOSED = SIZE
NODES = 2*SIZE

b_tilemap:
.db 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
.db 1,0,0,0,0,0,0,1,0,0,0,0,1,0,1
.db 1,0,0,0,1,0,0,1,0,0,0,0,0,0,1
.db 1,0,0,0,0,0,0,0,0,0,1,0,0,0,1
.db 1,0,1,1,0,0,1,1,0,0,1,0,1,1,1
.db 1,0,0,1,1,0,0,1,0,0,1,0,1,3,1
.db 1,2,0,0,0,0,0,1,1,0,1,0,0,0,1
.db 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
b_closed:
.fill SIZE,0
b_nodes:
.fill SIZE,0

end:
bcall(_ClrLCDFull)
di
ld hl,b_tilemap
;x + y
ld de,1+(6*WIDTH)
ld bc,13+(5*WIDTH)
add hl,de ;starting position in map
start:
ld de,CLOSED
add hl,de ;b_closed
ld (hl),1 ;starting position marked as ready to check
add hl,de ;b_nodes
ld (hl),0 ;first node starts off at 0
ld hl,b_closed
add hl,bc
ld (hl),$FF
ld bc,SIZE
ex af,af'
ld a,%00110011
ex af,af'
ld hl,b_closed
search_outer:
push hl
push bc
ex af,af'
push af
call disp_frame
pop af
ex af,af'
pop bc
pop hl
di
ld de,0
search_loop:
ld a,(hl)
dec a
jr nz,$+4
push hl
inc e
inc hl
dec bc
ld a,c
or b
jr nz,search_loop ;check if bc = 0, repeat if no

retrieve_tiles:
ld a,e
or a
jr z,+_
pop hl
push de
call expand_tile
pop de
dec e
jr nz,retrieve_tiles
_ ld hl,b_closed ;reset search values
ld bc,SIZE
ex af,af'
rrca ;rotate to next part of pattern
ex af,af'
jr search_outer

expand_tile:
;search_right
inc (hl) ;set to 2 = closed
inc hl
ld a,(hl)
inc a
cp 2
call c,check_tile
search_left:
dec hl
dec hl
ld a,(hl)
inc a
cp 2
call c,check_tile
search_down:
inc hl
ld de,WIDTH
add hl,de
ld a,(hl)
inc a
cp 2
call c,check_tile
search_up:
ld de,-WIDTH*2
add hl,de
ld a,(hl)
inc a
cp 2
ret nc
check_tile:
ld de,CLOSED
or a
sbc hl,de ;hl points to -b_tilemap-
ld a,(hl)
or a ;check if current tile = 0
add hl,de ;doesn't affect z, -b_closed-
jr nz,$+4
ld (hl),1 ;1 = expand during next iteration
cp 3
jr nz,$+4
ld (hl),'X'-'0'
add hl,de ;hl points to -b_node-
ex af,af'
ld b,a
and %1
ld (hl),a ;load the current pattern
ld a,b
ex af,af'
sbc hl,de ;restore hl
ret

disp_frame:
bcall(_HomeUp)
display_smc = $+1
ld hl,b_tilemap
ld bc,WIDTH*256+HEIGHT
d_loop:
push hl
ld de,-b_tilemap
add hl,de
ld de,-SIZE
add hl,de
jr c,$-1
or a
sbc hl,de
ld de,b_tilemap
add hl,de
ld a,(hl)
cp 1
pop hl
ld a,(hl)
jr nz,$+4
ld a,$E0-'0'
add a,'0'
bcall(_PutC)
inc hl
djnz d_loop
ld de,(curRow)
inc e
ld d,0
ld (curRow),de
ld b,WIDTH
dec c
jr nz,d_loop
_ call pause
ld a,b
dec a
ld de,SIZE
rra
rra
jr c,+_
ld hl,(display_smc)
sbc hl,de
ld (display_smc),hl
jr disp_frame
_ rra
ret c
ld hl,(display_smc)
add hl,de
ld (display_smc),hl
jr disp_frame

pause:
call release_keys
pause_loop:
xor a
call read_keys
inc a
jr z,pause_loop
ld b,a
release_keys:
xor a
call read_keys
inc a
jr nz,release_keys
ret

;direct input
read_keys:
out (1),a ;
push af ;short delay
pop af
in a,(1)
ret

Title: Re: [ASM] Help!! Diagonal backtracking through fixed-mem BFS pathfinding search?
Post by: ZippyDee on December 04, 2013, 05:49:28 pm

Yeah, I've already written it with bits. I'm having trouble with the backtracking, specifically an efficient way to implement it with diagonals. I'll try to make some animated pictures to illustrate the method I have in mind.

Title: Re: [ASM] Help!! Diagonal backtracking through fixed-mem BFS pathfinding search?
Post by: chickendude on December 05, 2013, 12:29:22 pm

Ok, i'm having some computer issues but i'll think about it (as well as converting my code to bits  :banghead:) while i try to fix things up. To follow back, you can just compare the bits to where you left off, for example if you've rotated to %10011001, you need to look for a 1, then two 0's, then two 1's, etc. I'll need to look at some more patterns but i believe you can move diagonally following a %10101010 pattern. You'd just rotate the pattern twice, since it's essentially two moves packed in one.

EDIT: So for diagonal movement, instead of checking bit 0 of the pattern, check bit 1. If bit 1 is correct, you can move diagonally.

Title: Re: [ASM] Help!! Diagonal backtracking through fixed-mem BFS pathfinding search?
Post by: ZippyDee on December 05, 2013, 01:30:51 pm

No, it doesn't work that way, chickendude.
Think of it this way:

You have tiles ABCD in a square
   AB
   CD
You are at tile A and you want to figure out if you can move diagonally to D, which is not a wall. You check if D is bit 1 of the pattern. It is. (woo!) So you move to D.
But wait.... What about B and C? If B and C are walls, you've now walked through a wall...We can't be having that now, can we? If either B or C are walls, you can't move diagonally to D. They BOTH need to be valid in order to move.


My solution to that is to look at the valid adjacent tiles and keep that data in a byte somewhere when you move to the next tile. Let's say you're at A and you check your surrounding tiles and get Down and Right as valid directions. Your data is formatted something like %0000ULDR so you end up with %00000011 as your adjacent data for this tile.
So now you choose one of those two directions to move. Doesn't matter which. Let's say right. So you AND your data with %11111110 to reset the bit for right, and you move to that tile.

Now you're at B and you check valid directions and you end up with something like %00001011 (Up, Down, and Right). Now AND that with the byte you stored from your previous tile (which is now %00000010) and you have %00000010 as a result. That means you could have moved Down before, but you didn't, and you still can move down now. You know now that you can move diagonally to D without any issues because both B and C must be free. After moving to that diagonal tile be sure set the saved data to %00000000 so there aren't any issues!


That's the solution I've come up with so far. I think it should work if I can write it like that!