go support the original - https://scratch.mit.edu/users/Gelijkwat/ ˜”*°•.˜”*°• Mathematical Pathfinding Bot •°*”˜.•°*”˜ 1. Introduction -- How this project came into existance After over 4 hours of coding (if you don't the brainstorming under the shower) it's finally here! This was absolutely a nightmare to construct since I knew basically nothing about the art of pathfinding. So I had to come up with my own idea. There were a couple of ways that came to my had like for instance calculating the easiest reachable square closest to the goal. But in the end I chose for this method* *see Chapter 4* 2. User manual -- How to use the program Since it should be quite intuitive I'll keep it short here. When you press the green flag an editor should appear where you can setup the scenery for the alorithm to find the green square (the goal). These are all possible buttons: - Green = The goal, place first for optimal result - Dark red = An obstacle, this is what the algorithm will avoid, make sure there is always a possible path from the white square to the green one. - Red-white'ish button = Press this if you made a mistake and want to start over again - V-button = Press when ready, sit back, relax and let the algorithm do all the work. 3. Pathinding -- What is it exactly? According to wikipedia it is: 'The plotting, by a computer application, of the shortest route between two points' Which is quite accurate. Since I'm not an expert on programming I decided to keep it to a simple 8x7 pixel grid. If you're a human it might seem childishly simple to go from the white to the green square. But when you start to think in concrete code, things start to get a little bit messy in your head. 4. How it works -- Only read if you're a nerd... I call it 'family tree algorithm' which we will come to in a second, let me first explain you what 'parents' and 'children' in this program are. Every scene the program converts into a path starts at the very first square 1,1. Which is a 'child' (call them whatever you want). A white square, which will become a mother when it will be blocked on every side. In this case 1,1 will become a mother when she has placed a child on 2,1 and 1,2. It can't place one to it's left or under it because the border of the playing field restricts that. This process will go on and on till nearly all squares are mothers and all the reachable squares have been covered. And now the fun part, every covered quare will be given a name based on the name of it's mother. Which immediately will be it's path: so if the goal where to be on 3,3, it's name would be: 1,1 - 2,1 - 3,1 - 3,2 - 3,3. Problem solved! Anyways, that probably made zero sense to you since I'm terrible at explaining. Did you seriously read all of that? ;)
first remix! it was by https://scratch.mit.edu/users/Gelijkwat/ go support the original!
