Flood fill Pathfinding

Instructions

This project is not a maze solver, it's a real pathfinder and I just choosen to show it in a maze, it can be used in any grid based project WARNING ! A lot of text just under ! (read if you wanna understand / use the project) (please use turbowarp it’s faster) https://turbowarp.org/1292849674?fps=240&stuck This project is a pathfinding algorithm and a maze generator (made by myself) https://scratch.mit.edu/projects/1292716565/ The pathfinding algorithm used is based on the flood fill algorithm, the flood fill algorithm is originally an algorithm used to fill certain area with a value, it's mostly used in drawing apps like paint, photoshop, gimp... (for more details see in Notes and Credits) The way I used the Flood fill algorithm for Pathfinding is based on an Acerola video (link in N&C), how does it works ? Well it's simple : where the Flood fill algorithm only add tiles to the pile, we will bind a value, let's call it V with every tile, the first tile, the origin, start at 0, and we will increase V every time. So, that part was only the setup, it's the part that take the longer because we have to loop through almost every tile. Now we can pick our destination tile, set it as the current tile, look at it's V and store it in a variable, then we will repeat while the current tile isn't the starting tile : ° look at every neighbor tiles ° set the neighbor tile with the lowest V as the current tile Now with that algorithm, the pathfinding algorithm is completed. It is important to note that the Flood fill Pathfinding algorithm we just made isn't efficient AT ALL if our starting tile is changing because we would have to redo all the inefficient first part of the process. Where that algorithm shine is for having a fix starting tile and having to generate the path for every target tile in range. But our algorithm as so is still improvable, so what can we improve ? Well, there are a lot of improvements we can do in scratch because some blocks takes way longer to compute than other, like the ”item# of” or “touching () ?” block. But this is not what we are going to improve here, we can do something else that is way faster : every time we wanna generate the optimal path between two points we have to cross every tiles on the path and do extra work, but if we look at our result we can see that multiple path share the same path at a certain point, so what we can do is just store the result of a pathfind in a list and every time we generate a new path, we look if we are crossing one of the stored results. I don’t think I was pretty clear so here is an example : you are lost in a forest and you try to come back to the city, and you find a big road with sign placed by other people pointing toward the city. Well we are these people and we already found the way back town, so why don’t you place marks for the next one to say “hey ! Here is how you can get back home”