couldn't sleep last night. ended up writing a pathing algorithm in my head for a block jam type game. how to initially determine the path each block would take to the exit, and then how to update it per each change
here it is written out:
the board is defined on a grid so you want each tile on the grid to know if it has a path to the exit, and if so how long that path is and which direction it needs to go
(a tile also knows if it is a wall, in which case there is no path and this will not change, and if there is a block inside it, in which case there may be a path, but adjacent blocks cannot path through it)
the exit is the bottom of the grid, so you start by going along the bottom row of tiles. if it's a wall piece, no path obviously cause it's a wall. otherwise, path of length one, straight down.
any tile that you set a path on, you're gonna want to check the tiles around it to see if they connect to that path. Technically, since you're going across the row left to right, you're already about to check the tile to the right, so you don't need to check it again. But you definitely need to check the tile above it, and probably the tile to the left. might not need the left one, but it's easier to check it than to check if you need to check it
so for each of those bottom tiles touching the exit, you take the tile above and the tile to the left, and you stick them in the checking queue.
Once you finish the bottom row, start working on the checking queue. For each tile in the queue, check the four tiles touching it. You're looking for the shortest path to the exit. A path through a tile will be of length that tile's path length plus one. So, check all four, see which is the shortest, set length and direction accordingly. If an adjacent tile is Unknown (path has not been evaluated yet), treat it the same as if it is Blocked. no pathing through it.
If the tile you are looking at gets Updated during this check, add all adjacent tiles to the checking queue
this way, when the queue is emptied, all tiles will point in the direction of the shortest possible path to the exit.
is this faster/more efficient than a branching method? no idea. maybe I will code them out and do some tests later. See how many tests each one does.
That's just the initial pathing, though. you also have to update it every time a block gets removed.
For that, when a block is removed, add the adjacent tiles to the checking queue. this'll unlock previously blocked off areas, and do a shortcut check at the same time.
