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... If not, I would love to clarify.

//EDIT: PICTURES!

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:

Note that they are all the exact same length. So technically the set of valid tiles to move to is:


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

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:

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:

Note that they are all the exact same length. So technically the set of valid tiles to move to is:


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

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.

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!