Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Docs: Update AStar3D examples #98978

Open
wants to merge 1 commit into
base: master
Choose a base branch
from

Conversation

tetrapod00
Copy link
Contributor

@tetrapod00 tetrapod00 commented Nov 8, 2024

Closes godotengine/godot-docs#10230

The examples for custom distance calculations were comparing the IDs of the points, which doesn't really make sense. I updated the examples to use Manhattan distance as an example of non-Euclidean distance. class_name/[GlobalClass] is used here because MyAStar3D needs to be referenced from another class to be used.

Also changed _estimate_cost() to simply use the actual cost. The current example was not very instructive, since it was more expensive than calculating the real cost. This change I'm not 100% sure about.

Alternate names for Manhattan distance are "Taxicab distance" or "city block distance". Godot already uses "Manhattan distance" in a few places:

<constant name="DISTANCE_MANHATTAN" value="2" enum="CellularDistanceFunction">

<constant name="HEURISTIC_MANHATTAN" value="1" enum="Heuristic">
The [url=https://en.wikipedia.org/wiki/Taxicab_geometry]Manhattan heuristic[/url] to be used for the pathfinding using the following formula:

@tetrapod00 tetrapod00 requested a review from a team as a code owner November 8, 2024 23:39
@AThousandShips AThousandShips added this to the 4.x milestone Nov 9, 2024
@Mickeon Mickeon requested a review from a team November 10, 2024 16:51
doc/classes/AStar3D.xml Outdated Show resolved Hide resolved
func _compute_cost(u, v):
var u_pos = get_point_position(u)
var v_pos = get_point_position(v)
return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can't this just be...?

Suggested change
return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)
return abs(u_pos - v_pos)

or, also:

Suggested change
return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)
return (u_pos - v_pos).abs()

Potentially same for C# example.

Copy link
Contributor Author

@tetrapod00 tetrapod00 Nov 10, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't think that is valid code :). You're taking the absolute value of the difference of two vectors and returning it from a function that returns a float.

If you meant to suggest return (u_pos - v_pos).length() or similar, then that would be calculating the Euclidean distance. It's a fine example of using the API but it should also be the default implementation of A*, and is not an example of overriding these functions for Non-Euclidean purposes. My example finds Manhattan/Taxicab distance, in which the distance is the sum of the difference of each cartesian coordinate.

I can see the reasoning for using Euclidean distance as the example, since it's simpler. Would just need to change some of the previous description.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

In that case this could be shortened to:

Suggested change
return abs(u_pos.x - v_pos.x) + abs(u_pos.y - v_pos.y) + abs(u_pos.z - v_pos.z)
var absolute = (u_pos - v_pos).abs()
return absolute.x + absolute.y + absolute.z

But no, it somehow feels more complex than it actually is. My concern is mainly about the length of a single line.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Line length is even more of a problem in the C# example because C# names are more verbose. Despite that, I think these make more sense as single lines

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Needs a damn good name for the variable, or just a or vec as last resort.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think the C# example is reasonably idiomatic for the docs already:

  • The Mathf namespace is usually inline, most examples don't do using Mathf;.
  • toPosition and fromPosition seem idiomatic. toPos and fromPos might be fine too, but the docs seem to prefer spelling out the whole name.

I guess I could split into the two lines like your suggestion just for the sake of making the line length shorter. IDK, the line already seems as concise as it can be given how verbose C# is. I don't see an obvious improvement here.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I shortened toPosition and fromPosition to toPoint and fromPoint.

Copy link
Contributor

@Mickeon Mickeon Nov 11, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Note that you changed the names only for C#. If that's the intention, it's okay, but the examples need to be consistent.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think it's okay in this case. We are getting the values from get_point_position()/GetPointPosition(). So either "point" or "position" are reasonable names. u_pos is an idiomatic GDScript name (short for u_position), and toPoint is an idiomatic C# name. Note that the parameters for _compute_cost() are u and v for GDScript but fromID and toID for C#, so there is already some difference in naming built into Godot already.

I could change u_pos to u_point but I don't think that serves anyone, it's longer for no reason. And I'd like to avoid toPos and fromPos because the current C# examples in other classes tend to spell out the full name, and it's more instructive to use the full name.

doc/classes/AStar3D.xml Show resolved Hide resolved
Copy link
Contributor

@Mickeon Mickeon left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Assuming accuracy this is completely fine. Navigation team still needs to look.

@Mickeon Mickeon modified the milestones: 4.x, 4.4 Nov 13, 2024
@Mickeon Mickeon added the cherrypick:4.3 Considered for cherry-picking into a future 4.3.x release label Nov 13, 2024
@tetrapod00
Copy link
Contributor Author

For the context of navigation reviewers: I tested out this example in GDScript by extending AStar3D, adding a few points, and manually calling _compute_cost() and verifying that it returned the right values (in this case, Manhattan distance rather than Euclidean). However, I did not set up a complex test case, and I only tested the C# example to verify it compiled.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
cherrypick:4.3 Considered for cherry-picking into a future 4.3.x release documentation enhancement
Projects
None yet
Development

Successfully merging this pull request may close these issues.

AStar3D example code for _compute_cost() and _estimate_cost() nonsensical
3 participants