For more information, see Pathfinding on Wikipedia.
Pathfinding is the ability for an artificial intelligence system to work out the proper path around obstacles to reach a destination point. For example, in Scratch, a sprite may be required to go around walls to reach a point, as in a maze. In the famous arcade game Pac-Man, the ghosts use pathfinding to make their way towards their target, Pac-Man. Pathfinding complexity can increase as more circumstances need to be analyzed.
History
Prior to the development of modern day 3D video games, pathfinding was more simplistic with the 2D environment, such as Scratch. Over time, pathfinding algorithms became more complex, intelligent, and multidimensional. As the power of CPUs has increased, computer hardware has gained more resources to calculate larger, more complex paths. Some pathfinding uses a grid-like system with "ortho" movement whereas others may use diagonals and curves. One game that is notable for its pathfinding is Roller Coaster Tycoon from 1999, which managed to handle thousands of guests and their paths on up to a 256 x by 256 y grid, along with the vertical dimension.[citation needed]
Creating a Grid-Based Quickest Pathfinder in Scratch
This example will use a 10 by 10 grid. Adapting to a different-sized grid is simple. Each box in the grid system needs to be identified in some way. A two-value system is used for this, with a box having an "x" value to represent it's position on the horizontal axis, and a "y" value to represent its position on the vertical axis. Adding a third dimension would require an additional "z" value and tweaks to the scripts.
Note: | For this tutorial a box of "x" position "n1" and "y" position "n2" will be represented as "(n1,n2)". |
The origin of the grid is considered to be the box at location (0,0). The origin can be anywhere, but depending on its location some very minor adjustments to the scripts must be made for it to function consistently. For this tutorial, assume the box in the top-left of the grid is (1,1), and the box in the bottom-right is (10,10), as shown in Figure 2.
Finding the quickest path between two points first necessitates knowing the grid coordinates of the two points. Many lists must also be used for the artificial intelligence to keep track of its progress and to map out what grid boxes are walls that the path cannot pass through or open for travelling. A list called "layout" can be created for this representation.
This requires some mathematics because a 2D grid is being transposed into a 1D list. To make it easier on the project creator, a custom block should be created to determine a grid box's list index based on its "x" and "y" coordinates. The simplest method is read the grid as if it is a book, starting from the top-left, reading rightward, and moving down one line at the right end. An example of this in a smaller grid can be seen in Figure 3.
A custom block that takes a box from Figure 2 and determines the list value as represented in Figure 3 is shown below:
define list position (gridx) (gridy) (minx) (maxx) (miny) (maxy) set [listpos v] to [0] //if off the grid it will remain as 0 if <<<(gridx) > ((minx) - (1))> and < (gridx) < ((maxx) + (1))>> and <<(gridy) > ((miny) - (1))> and <(gridy) < ((maxy) + (1))>>> then //if within the boundaries set [listpos v] to ((((gridy) * (10)) - (10)) + (gridx))
The type of box is either passable or impassable, represented by the colors black and white in this tutorial. In the "layout" list, white is represented by "1", and black is represented by "2".
The artificial intelligence uses a counting system to determine the proper pathway. It works in circles by checking the boxes bordering the endpoints. It then goes to each of those boxes and checks the boxes all bordering them. A counter is used every time, so on the second round of "circling", the number "2" is assigned to the boxes, and so forth. Boxes may be checked multiple times since every box is surrounded by more than one box; the boxes will only be overwritten with a lower value, never a higher one. Ultimately, the final pathway follows the lowest values. This will all be explained in more detail for a thorough understanding.
Step 1: Determine Counter Values with Revolution Method
The end point begins with a counter value of "0". All white boxes surrounding the end point will then obtain a value of "1". Then, the boxes around those boxes will obtain a value of "2" except for the boxes that already had a value below 2; so the boxes that obtained the value "1" cannot be overwritten as "2". The following script will take a list called "all_counters" and map out the numbers by representing the grid in a 1D format.
define reset data (endx) (endy) delete all of [all_counters v] delete all of [x to check v] delete all of [y to check v] delete all of [assoc counters v] add (endx) to [x to check v] add (endy) to [y to check v] add [0] to [assoc counters v] repeat (100) //10x10 grid add [100] to [all_counters v] //can be 10000 even - needs to be high end define setcounter (gridx) (gridy) list position (gridx) (gridy) (1) (10) (1) (10) //x and y grids go from 1 to 10 if <<(gridx) = (startx)> and <(gridy) = (starty)>> then set [match v] to [true] else if <(item (listpos) of [layout v]) = [1]> then //if a white box if<((current counter) + (1)) < (item (listpos) of [all_counters v])> then //if lower counter add (gridx) to [x to check v] //check this box next add (gridy) to [y to check v] add ((current counter) + (1)) to [assoc counters v] //easier than looking it up in "all_counters" list replace item (listpos) of [all_counters v] with ((current count) + (1)) end end end define set counters (startx) (starty) (endx) (endy) set [match v] to [false] //if destination reached set [i v] to (0) reset data (10) (10) //numbers used for example list position (endx) (endy) (1) (10) (1) (10) replace item (listpos) of [all_counters v] with [0] //starting box is 0 repeat until <<(match) = [true]> or <(i) > (length of [x to check v])>> change [i v] by (1) set [current x v] to (item (i) of [x to check v]) set [current y v] to (item (i) of [y to check v]) set [current counter v] to (item (i) of [assoc counters v]) setcounter ((current x) - (1)) (current y) //box to left setcounter ((current x) + (1)) (current y) //box to right setcounter (current x) ((current y) + (1)) //box above setcounter (current x) ((current y) - (1)) //box below end define list position (gridx) (gridy) (minx) (maxx) (miny) (maxy) ...
Running the "set counters" custom block will complete the first phase of the pathfinding process. This essentially will map out a counter-based arrangement of values on the grid that the artificial intelligence will use to make its pathway. Not every grid will be a 10x10 grid as in the example above, however. If the grid system uses a different origin and coordinate plane than in Figure 2, the "list position" custom block will need to be adjusted so the "listpos" variable points to the proper list index.
Likewise, if the grid size increases or decreases, the parameter inputs into the "list position" custom block will need to be changed accordingly. For example, if the column of rightmost boxes has an x position of 24, the "maxx" parameter will need to be changed to "24" when the custom block is used. A larger grid will also need a higher initial counter value. This can be easily accomplished by changing the "100" in the list block in the "reset data" custom block to any arbitrarily large value.
The "assoc counters" list is not entirely necessary in the above scripts. It is simply there to make the pathfinder more efficient by having the counter values of boxes in the near premises stored in a shorter list rather than the "all_counters" list. If removed, the "list position" custom block would need to be called within the "set counters" custom block, after which the "current counter" variable would be set to the "listpos" item of the "all_counters" list.
Step 2: Trace Out Shortest Pathway
The "counter" system created in Step 1 is used to determine the quickest path. The counter system started at the endpoint, but the path determination contrarily begins at the start point. It will look at the four adjacent boxes (it detects if an adjacent box is off the grid), determine which box has the lowest counter, and set that box as the next one to move to. It will repeat this process until the end point is reached.
If this is attempted from the end point to the start point it may not work. It can result in the pathfinder getting trapped in a dead-end. In the process, if two or more adjacent boxes share the same counter value, any one can be moved to. The "all_counters" list stores the definite counter value of every single grid box and is analyzed for this process.
Two lists are used to store the final pathway. These can be called "pathx" and "pathy", which store the coordinates of the grid pathway. The first item in the list is the starting point, and the last item will end up as the end point. For the pathway between the start and end, a custom block can be made to help the artificial intelligence decide which bordering block is the next best move, using the counter system from Part 1.
define decide (gridx) (gridy) (outcome) list position (gridx) (gridy) (1) (10) (1) (10) if <not <(listpos) = [0]>> then //if a valid grid box set [this_counter v] to (item (listpos) of [all_counters v]) //get the counter value if <(this_counter) < (low)> then //if it's lower than the lowest so far set [low v] to (this_counter) //make it the new low set [which_direction v] to (outcome) //make it set to move that way end end define list position (gridx) (gridy) (minx) (maxx) (miny) (maxy) ...
Another custom block called "route" can be created. It will utilize the "decide" custom block to prevent repetitive scripts. Breaking apart scripts into custom blocks makes managing a complex programming problem simpler.
define route (startx) (starty) (endx) (endy) delete all of [pathx v] delete all of [pathy v] if <(match) = [true]> then set [match v] to [false] set [current x v] to (startx) set [current y v] to (starty) repeat until <(match) = [true]> add (current x) to [pathx v] add (current y) to [pathy v] set [which_direction v] to [none] set [low v] to [100] //must be larger for larger grids decide ((current x) + (1)) (current y) (1) //box to the right decide ((current x) - (1)) (current y) (2) decide (current x) ((current y) + (1)) (3) decide (current x) ((current y) - (1)) (4) //box below if <(which_direction) = [1]> then change [current x v] by (1) end if <(which_direction) = [2]> then change [current x v] by (-1) end if <(which_direction) = [3]> then change [current y v] by (1) end if <(which_direction) = [4]> then change [current y v] by (-1) end if <<(current x) = (endx)> and <(current y) = (endy)>> then //if at the end add (current x) to [pathx v] add (current y) to [pathy v] set [match v] to [true] //finish end end end define decide (gridx) (gridy) (outcome) ...
Step 3: Wrapping it all Together
One final custom block can be created to provide the project creator with a single-block method of finding the quickest path between two points. It will utilize the "set counters" and "route" custom blocks from Steps 1 and 2 respectively.
define find path from (startx) (starty) to (endx) (endy) on grid (minx) (maxx) (miny) (maxy) set counters (startx) (starty) (endx) (endy) route (startx) (starty) (endx) (endy) define set counters (startx) (starty) (endx) (endy) ... define route (startx) (starty) (endx) (endy) ...
While not used above, the minimum and maximum parameters for the grid can be incorporated in some way to create a more universal custom block that can work with any sized grid; they are added for convenience. Once the path is generated into the "pathx" and "pathy" lists, the path can be traced out, travelled gradually, or traversed in any desired manner with other scripts not included in this tutorial.
Note: | To ensure that the path is found as quickly as possible, it is advised under the "options" menu in the custom block creation window to check the "run without screen refresh" box for all the custom blocks. |