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.

Sign up for GitHub

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

Jump to bottom

Add AStar2D/AStar3D methods to get the nearest segment point IDs and normal #11573

Open
RobertBColton opened this issue Jan 15, 2025 · 5 comments · May be fixed by godotengine/godot#101624
Open

Add AStar2D/AStar3D methods to get the nearest segment point IDs and normal #11573

RobertBColton opened this issue Jan 15, 2025 · 5 comments · May be fixed by godotengine/godot#101624
Labels
topic:navigation

Comments

@RobertBColton
Copy link

Describe the project you are working on

City builder where I want to snap building placement to the nearest segment of a path.

Describe the problem or limitation you are having in your project

I am using AStar3D classes to represent the path network that buildings are snapped to. I use get nearest segment a lot to place buildings and traverse the network with agents. The problem with that is that the API provides no way to get the point ids of the segment endpoints, which makes it not easy to get at things like the normal of the path segment.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

The two respective classes would return the point ids and the normal of the segment in a AStar3DPointInfo class.

https://docs.godotengine.org/en/stable/classes/class_astar3d.html#class-astar3d-method-get-closest-position-in-segment
https://docs.godotengine.org/en/stable/classes/class_astar2d.html#class-astar2d-method-get-closest-position-in-segment

This would be consistent with other graphing APIs do, such as PointGraph in Unity3D A* package.
https://arongranberg.com/astar/docs_dev/class_pathfinding_1_1_point_graph.php#a85deb430d8df256df2daa903722fa4c1

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Here is some pseudo code for how you might use the proposed API to snap building to a path:

var nearest_segment = path_network.get_closest_position_in_segment(mouse_position)
building_preview.position = nearest_segment.position + nearest_segment.tangent * building_preview.size()/2
building_preview.rotate_y(nearest_segment.normal.angle())

If this enhancement will not be used often, can it be worked around with a few lines of script?

It's extremely slow to do it in gdscript, but yes you can theoretically reimplement the API that already exists to pull it off.

Is there a reason why this should be core and not an add-on in the asset library?

It's a pretty useful feature in a lot of games with path finding. Plus the information is already there/implemented in Godot, it just needs to be returned.
@RobertBColton RobertBColton changed the title Feature: AStar2D/AStar3D Nearest Segment Point IDs Feature: AStar2D/AStar3D Nearest Segment Point IDs/Normal Jan 15, 2025
@Calinou Calinou changed the title Feature: AStar2D/AStar3D Nearest Segment Point IDs/Normal Add AStar2D/AStar3D methods to get the nearest segment point IDs and normal Jan 15, 2025
@ydeltastar
Copy link

Isn't it what AStar3D.get_closest_point does?

@RobertBColton
Copy link
Author

RobertBColton commented Jan 15, 2025 •
edited
Loading

It is not, here is a diagram to explain. I would want to get normal/tangent of nearest segment. Nearest point may not be on the nearest segment.

Image

@ydeltastar
Copy link

ydeltastar commented Jan 16, 2025 •
edited
Loading

Got it but the proposed code is a bit confusing. The A* class doesn't have a concept of tilt so it can't return a normal and a tangent, only the tangent (or vector direction to be precise).

Shouldn't it return the IDs of the endpoints instead? From it you can get and calculate everything else with the other methods. Changing return types is a breaking change and the current feature should be available as well so it needs to be a new method like PackedInt64Array get_nearest_segment_points(to_position: Vector3).

@RobertBColton
Copy link
Author

RobertBColton commented Jan 16, 2025 •
edited
Loading

The normal of a segment is the vector from the first segment point to the second when it is not bidirectional. The tangent is perpendicular to one side of the road. However, this is actually not enough for general use as we need to also take the dot product with the current mouse position to tell which side of the road we are on.

Regardless, I suggested an info class because in order to find the nearest segment you have to compare the projected distances like get_closest_position_in_segment already does. The nearest segment to a point is also the segment that holds a segment position closest to the same point. So may as well return all of the info since it's already computed and would be slower to do it all over again on the gdscript side.

Anyway, I just suggested that as a convenience, having the point ids is enough for me as I can just call Geometry2D on the gdscript side to get the interpolated position. I have a pull request in progress, I will follow up shortly.

@RobertBColton RobertBColton linked a pull request Jan 16, 2025 that will close this issue
Open
@RobertBColton
Copy link
Author

Here we are, I've opened my very first pr in Godot: godotengine/godot#101624

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
topic:navigation
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add AStar2D/AStar3D get_closest_segment with ids RobertBColton/godot
3 participants
@Calinou @RobertBColton @ydeltastar