Pathfinding

Описание	Поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который означает определение компьютерной программой наилучшего, оптимального маршрута между двумя точками.
Область знаний	Информатика, Робототехника, Искусственный интеллект
Область использования (ISTE)	Computational Thinker
Возрастная категория	11
Поясняющее видео
Близкие рецепту понятия	Искусственный интеллект, Искусственный игровой интеллект
Среды и средства для приготовления рецепта:	Scratch, Snap!, C++, Lua

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

Park goers make their way around obstacles in a classic video game. 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 256x256 x and y grid, along with the vertical dimension.

Creating a Grid-Based Quickest Pathfinder in Scratch

This example will use a 10x10 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.

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.

See Also

• Pathfinding on Wikipedia