Adding distance/cost to the connection rather than in point AStar.

[pegasusearl]

Describe the project you are working on:

Restaurant simulator where staff and customer will need pathfinding to walk from door, kitchen, seat and table. The game is about effective restaurant layout so abit more accurate pathfinding will be useful.

Describe the problem or limitation you are having in your project:

You can't set connection_cost (from point to point) manually. A point can have multiple connections that will have different distance so we can't just use weight_scale for it. weight_scale is setting cost at the point, not in the connection. In current astar, it's impossible to set connection_cost.

Usually I just ignore weight_scale or distance but for this project, I wish I could make better one.

Describe how this feature / enhancement will help you overcome this problem or limitation:

If we can manually set connection_cost. We won't need hacky workaround.

Show a mock up screenshots/video or a flow diagram explaining how your proposal will work:

Current

We can set weight_scale, but we can't manually set distance between points. Distance determined by weight_scale.

With customizable connection_cost

If we can manually set the distance between point, we can do this:

see the distance.

Circle with A B C is points. and the arrow is the connections.

Describe implementation detail for your proposal (in code), if possible:

Unfortunately, I don't know how to implement it in the engine. But this is how godot user can use it:

add_point ( int id, Vector3 position, float weight_scale=1.0 ) # add point stay the same just incase some user actually used weight_scale,
connect_points ( int id, int to_id, bool bidirectional=true, <float/int> cost=1 ) # just adding cost

total_costs = cost * weight_scale

# OR (EDITED in march 10th, 2020)
total_costs = cost * weight_scale_a *  weight_scale_b / 2
# as weight_scale_a is from source point and weight_scale_b is from destination point.

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

No. It can be workarounded but definitely not with just few lines of code.
What I can think of is adding an "inbetween node" for connections that had extra distance. Then everytime we call get_point_path() we will need to check if there is "inbetween node" then remove them. Of course that also means we will have list of which one is regular point and which one is inbetween.

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

To my subjective opinion, I don't undrestand why we have weight_scale instead of custom distance. Custom distance easily workaround weight_scale but weight_scale cannot fix different distances in the from or to the same points.
weight_scale had far fewer usecase than custom distance. Example are the pictures I shown above, diagonal movement and point to point movement. (that point to point movement can be used for world_map pathfinding. World map is set of areas in which distance between area to area is different)

Thank you for reading this far. It's alot of text.
I apologize for any unpleasant words. If there is any mistake/misunderstanding, I would like to hear it.

[logzero]

Yeah, having a point weight seems to be a bit of a weird choice, a memory usage optimization?

From a quick look at the code you'd have to move weight_scale from Point to Segment and patch up all the functions using it.

Or to remain backwards compatible, keep Point weight_scale and have additional Segment weight_scale.

[smix8]

Both should be available. Point cost / weight as well as connection cost / weight and the option to replace the geometry distance calculation between points with a custom distance value.

While all this is possible if you extend the AStar class and override the _compute_cost() and _estimate_cost() functions this is too much asked for such a commonly required navigation feature especially for beginners.