diff options
author | Maganty Rushyendra <mrushyendra@yahoo.com.sg> | 2021-01-05 18:03:16 +0800 |
---|---|---|
committer | Maganty Rushyendra <mrushyendra@yahoo.com.sg> | 2021-01-05 19:51:38 +0800 |
commit | f6634648ce730d4ae2582ec5fbe825738f2a4438 (patch) | |
tree | 8b50123eb4715bb226871780431f233731b3a479 /doc | |
parent | edccc0bbdffe3175e41358e4d85bcd50b6f04d8e (diff) |
Explain A Star pathfinding algorithm cost calcuation
Diffstat (limited to 'doc')
-rw-r--r-- | doc/classes/AStar.xml | 6 | ||||
-rw-r--r-- | doc/classes/AStar2D.xml | 5 |
2 files changed, 7 insertions, 4 deletions
diff --git a/doc/classes/AStar.xml b/doc/classes/AStar.xml index 0cd7d3dc25..bfdc66623d 100644 --- a/doc/classes/AStar.xml +++ b/doc/classes/AStar.xml @@ -33,6 +33,7 @@ [/csharp] [/codeblocks] [method _estimate_cost] should return a lower bound of the distance, i.e. [code]_estimate_cost(u, v) <= _compute_cost(u, v)[/code]. This serves as a hint to the algorithm because the custom [code]_compute_cost[/code] might be computation-heavy. If this is not the case, make [method _estimate_cost] return the same value as [method _compute_cost] to provide the algorithm with the most accurate information. + If the default [method _estimate_cost] and [method _compute_cost] methods are used, or if the supplied [method _estimate_cost] method returns a lower bound of the cost, then the paths returned by A* will be the lowest cost paths. Here, the cost of a path equals to the sum of the [method _compute_cost] results of all segments in the path multiplied by the [code]weight_scale[/code]s of the end points of the respective segments. If the default methods are used and the [code]weight_scale[/code]s of all points are set to [code]1.0[/code], then this equals to the sum of Euclidean distances of all segments in the path. </description> <tutorials> </tutorials> @@ -71,7 +72,8 @@ <argument index="2" name="weight_scale" type="float" default="1.0"> </argument> <description> - Adds a new point at the given position with the given identifier. The algorithm prefers points with lower [code]weight_scale[/code] to form a path. The [code]id[/code] must be 0 or larger, and the [code]weight_scale[/code] must be 1 or larger. + Adds a new point at the given position with the given identifier. The [code]id[/code] must be 0 or larger, and the [code]weight_scale[/code] must be 1 or larger. + The [code]weight_scale[/code] is multiplied by the result of [method _compute_cost] when determining the overall cost of traveling across a segment from a neighboring point to this point. Thus, all else being equal, the algorithm prefers points with lower [code]weight_scale[/code]s to form a path. [codeblocks] [gdscript] var astar = AStar.new() @@ -380,7 +382,7 @@ <argument index="1" name="weight_scale" type="float"> </argument> <description> - Sets the [code]weight_scale[/code] for the point with the given [code]id[/code]. + Sets the [code]weight_scale[/code] for the point with the given [code]id[/code]. The [code]weight_scale[/code] is multiplied by the result of [method _compute_cost] when determining the overall cost of traveling across a segment from a neighboring point to this point. </description> </method> </methods> diff --git a/doc/classes/AStar2D.xml b/doc/classes/AStar2D.xml index 1540d8dacc..2a51678209 100644 --- a/doc/classes/AStar2D.xml +++ b/doc/classes/AStar2D.xml @@ -43,7 +43,8 @@ <argument index="2" name="weight_scale" type="float" default="1.0"> </argument> <description> - Adds a new point at the given position with the given identifier. The algorithm prefers points with lower [code]weight_scale[/code] to form a path. The [code]id[/code] must be 0 or larger, and the [code]weight_scale[/code] must be 1 or larger. + Adds a new point at the given position with the given identifier. The [code]id[/code] must be 0 or larger, and the [code]weight_scale[/code] must be 1 or larger. + The [code]weight_scale[/code] is multiplied by the result of [method _compute_cost] when determining the overall cost of traveling across a segment from a neighboring point to this point. Thus, all else being equal, the algorithm prefers points with lower [code]weight_scale[/code]s to form a path. [codeblocks] [gdscript] var astar = AStar2D.new() @@ -350,7 +351,7 @@ <argument index="1" name="weight_scale" type="float"> </argument> <description> - Sets the [code]weight_scale[/code] for the point with the given [code]id[/code]. + Sets the [code]weight_scale[/code] for the point with the given [code]id[/code]. The [code]weight_scale[/code] is multiplied by the result of [method _compute_cost] when determining the overall cost of traveling across a segment from a neighboring point to this point. </description> </method> </methods> |