Pathfinding - История изменений

Patarakin в 11:51, 26 марта 2023

2023-03-26T11:51:19Z

← Предыдущая версия		Версия от 14:51, 26 марта 2023
Строка 7:		Строка 7:
	\|Environment=Scratch, Snap!, C++, Lua		\|Environment=Scratch, Snap!, C++, Lua
	}}		}}
	'''Pathfinding''' is the ability for an [[Artificial Intelligence\|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.		'''Pathfinding''' is the ability for an [[Artificial Intelligence\|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 ==		== History ==
	Park goers make their way around obstacles in a classic video game.		Park goers make their way around obstacles in a classic video game.
	Prior to the development of modern day ~~[[Three-Dimensional Projects\|~~3D video games]], pathfinding was more simplistic with the 2D environment, such as Scratch. Over time, pathfinding [[algorithm]]s became more complex, intelligent, and multidimensional. As the power of ~~[[Computer Science#Processors\|~~CPUs]] has increased, ~~[[Computer Science#Hardware\|~~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.~~{{cn\|date=July 2017}}~~		Prior to the development of modern day 3D video games, pathfinding was more simplistic with the 2D environment, such as Scratch. Over time, pathfinding [[algorithm]]s 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 ==		== Creating a Grid-Based Quickest Pathfinder in Scratch ==

Patarakin в 14:35, 19 февраля 2023

2023-02-19T14:35:41Z

← Предыдущая версия		Версия от 17:35, 19 февраля 2023
Строка 1:		Строка 1:
	{{Scripting Tutorials		{{Scripting Tutorials
	\|Description=~~Как найти кратчайшее расстояние~~ между точками		\|Description=Поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который означает определение компьютерной программой наилучшего, оптимального маршрута между двумя точками.
	\|Field_of_knowledge=Информатика		\|Field_of_knowledge=Информатика, Робототехника, Искусственный интеллект
			\|FieldActivity=Computational Thinker
	\|Возрастная категория=11		\|Возрастная категория=11
			\|similar_concepts=Искусственный интеллект, Искусственный игровой интеллект
			\|Environment=Scratch, Snap!, C++, Lua
	}}		}}
	'''Pathfinding''' is the ability for an [[Artificial Intelligence\|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.		'''Pathfinding''' is the ability for an [[Artificial Intelligence\|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.

Patarakin: /* Step 2: Trace Out Shortest Pathway */

2022-08-29T09:50:58Z

Step 2: Trace Out Shortest Pathway

← Предыдущая версия		Версия от 12:50, 29 августа 2022
Строка 97:		Строка 97:
	=== Step 2: Trace Out Shortest Pathway ===		=== Step 2: Trace Out Shortest Pathway ===

	~~[[File:Pathfinding Process.png\|thumb\|'''Figure 4''': An example scenario of the counter values and shortest possible path between two points using this article's method.]]~~
	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.		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.

Patarakin: /* Creating a Grid-Based Quickest Pathfinder in Scratch */

2022-08-29T09:50:22Z

Creating a Grid-Based Quickest Pathfinder in Scratch

← Предыдущая версия		Версия от 12:50, 29 августа 2022
Строка 15:		Строка 15:


	~~[[File:PathfindingGrid.png\|left\|thumb\|'''Figure 2''': A numerical representation of a grid system. In this particular grid the origin is off the grid in the top-left.]]~~
	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'''.		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'''.

Строка 180:		Строка 179:

	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.		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 ==		== See Also ==

Patarakin в 09:50, 29 августа 2022

2022-08-29T09:50:05Z

← Предыдущая версия		Версия от 12:50, 29 августа 2022
Строка 1:		Строка 1:
	{{~~April Fools}}~~		{{Scripting Tutorials
	~~[[File:Pathfinding.jpg~~\|~~thumb~~\|~~'''Figure 1''': A very basic pathfinding algorithm is used to find the shortest path between the two dots in this grid system.]]~~		\|Description=Как найти кратчайшее расстояние между точками
			\|Field_of_knowledge=Информатика
			\|Возрастная категория=11
			}}
	'''Pathfinding''' is the ability for an [[Artificial Intelligence\|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.		'''Pathfinding''' is the ability for an [[Artificial Intelligence\|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 ==		== History ==
	~~[[File:Paths Video Games.jpg\|thumb\|~~Park goers make their way around obstacles in a classic video game.]]		Park goers make their way around obstacles in a classic video game.
	Prior to the development of modern day [[Three-Dimensional Projects\|3D video games]], pathfinding was more simplistic with the 2D environment, such as Scratch. Over time, pathfinding [[algorithm]]s became more complex, intelligent, and multidimensional. As the power of [[Computer Science#Processors\|CPUs]] has increased, [[Computer Science#Hardware\|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.{{cn\|date=July 2017}}		Prior to the development of modern day [[Three-Dimensional Projects\|3D video games]], pathfinding was more simplistic with the 2D environment, such as Scratch. Over time, pathfinding [[algorithm]]s became more complex, intelligent, and multidimensional. As the power of [[Computer Science#Processors\|CPUs]] has increased, [[Computer Science#Hardware\|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.{{cn\|date=July 2017}}

Строка 11:		Строка 14:
	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 [[script]]s.		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 [[script]]s.

	~~{{note\|For this tutorial a box of "x" position "n1" and "y" position "n2" will be represented as "(n1,n2)".}}~~

	[[File:PathfindingGrid.png\|left\|thumb\|'''Figure 2''': A numerical representation of a grid system. In this particular grid the origin is off the grid in the top-left.]]		[[File:PathfindingGrid.png\|left\|thumb\|'''Figure 2''': A numerical representation of a grid system. In this particular grid the origin is off the grid in the top-left.]]
Строка 20:		Строка 22:
	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 Blocks\|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'''.		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 Blocks\|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'''.

	~~[[File:2DTransposed1D.jpg\|200px\|thumb\|'''Figure 3''': A 2D grid being transposed into a 1D list. Black boxes have the value "2" and white boxes "1".]]~~

	A custom block that takes a box from '''Figure 2''' and determines the list value as represented in '''Figure 3''' is shown below:		A custom block that takes a box from '''Figure 2''' and determines the list value as represented in '''Figure 3''' is shown below:
Строка 180:		Строка 181:
	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.		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.}}

	== See Also ==		== See Also ==
Строка 186:		Строка 186:
	* [[Wikipedia:Pathfinding\|Pathfinding]] on Wikipedia		* [[Wikipedia:Pathfinding\|Pathfinding]] on Wikipedia

	~~[[Category:Computer Science]]~~[[Category:Scripting Tutorials]]		[[Category:Scripting Tutorials]]

Patarakin: 1 версия импортирована

2022-07-21T08:33:17Z

1 версия импортирована

← Предыдущая версия		Версия от 11:33, 21 июля 2022
(нет различий)

scratch>Jvvg в 21:35, 6 июня 2022

2022-06-06T21:35:57Z

Новая страница

{{April Fools}}
[[File:Pathfinding.jpg|thumb|'''Figure 1''': A very basic pathfinding algorithm is used to find the shortest path between the two dots in this grid system.]]
'''Pathfinding''' is the ability for an [[Artificial Intelligence|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 ==
[[File:Paths Video Games.jpg|thumb|Park goers make their way around obstacles in a classic video game.]]
Prior to the development of modern day [[Three-Dimensional Projects|3D video games]], pathfinding was more simplistic with the 2D environment, such as Scratch. Over time, pathfinding [[algorithm]]s became more complex, intelligent, and multidimensional. As the power of [[Computer Science#Processors|CPUs]] has increased, [[Computer Science#Hardware|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.{{cn|date=July 2017}}

== 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 [[script]]s.

{{note|For this tutorial a box of "x" position "n1" and "y" position "n2" will be represented as "(n1,n2)".}}

[[File:PathfindingGrid.png|left|thumb|'''Figure 2''': A numerical representation of a grid system. In this particular grid the origin is off the grid in the top-left.]]
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 [[list]]s 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 Blocks|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'''.

[[File:2DTransposed1D.jpg|200px|thumb|'''Figure 3''': A 2D grid being transposed into a 1D list. Black boxes have the value "2" and white boxes "1".]]

A custom block that takes a box from '''Figure 2''' and determines the list value as represented in '''Figure 3''' is shown below:

<scratchblocks>
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))
</scratchblocks>

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.

<scratchblocks>
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)
...
</scratchblocks>

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 ===

[[File:Pathfinding Process.png|thumb|'''Figure 4''': An example scenario of the counter values and shortest possible path between two points using this article's method.]]
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.

<scratchblocks>
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)
...
</scratchblocks>

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.

<scratchblocks>
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)
...
</scratchblocks>

=== 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.

<scratchblocks>
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)
...
</scratchblocks>

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.}}

== See Also ==

* [[Wikipedia:Pathfinding|Pathfinding]] on Wikipedia

[[Category:Computer Science]][[Category:Scripting Tutorials]]