[SOLVED] AStar not selecting best path with tilemaps; need diagonal movement = cartesian movement

Question

I've built a small tilemap, each tile is 64px by 64px.
I've built an AStar, with each point connected to it's neighbor, including it's diagonal neighbor.
Bidirection movement between points is enabled.
I have set weights for each point.

Here's my default tilemap:
- Weights are shown
- "x" is my character

I want to move my character 2 tiles down, here's the "best path" AStar detects:

Here's the path it should take because the weight is cheaper
- e.g. above AStar path is: 4+3=7; this path is: 3+3=6

--
The AStar works well everywhere else, and I've narrowed down this issue to only when a better path involves diagonal movement. From there, I'm deducing that AStar must be saying that going from the x -> 3 tile is longer (pixels/offset) than going from the x -> 4 tile. Therefore AStar chooses the later even though the weight is more expensive.

Does this conclusion seem correct? If yes, How do I adjust the AStar to go strictly off weights and not distances (pixels/offset) so I can get the desire path of: x -> 3 -> 3 show above?

Answer 1

If you want to ignore euclidean distance and use only connections it is trivial:

extends AStar

func _compute_cost(_from_id, _to_id):
    return 1.0


func _estimate_cost(_from_id, _to_id):
    return 1.0

Those functions are called for points that have a connection between them.

Here's a code that uses above subclass:

extends Node

var astar = preload("res://NoneuclideanAStar.gd").new()


const pointsToWeight := {
    Vector3(0,0,0) : 5, Vector3(1,0,0) : 1, Vector3(2,0,0) : 3,

    Vector3(0,1,0) : 3, Vector3(1,1,0) : 4, Vector3(2,1,0) : 4,

    Vector3(0,2,0) : 3, Vector3(1,2,0) : 3, Vector3(2,2,0) : 4,
}

const connections := [
    [00,10], [10,20], [01,11], [11,21], [02,12], [12,22],   # horizontally
    [00,01], [01,02], [10,11], [11,12], [20,21], [21,22],   # vertically
    [10,01], [10,21], [01,12], [21,12], #diagonally
 ]


func _ready():
    for point in pointsToWeight.keys():
        var id = point.x * 10 + point.y
        astar.add_point( id, point, pointsToWeight[point] )

    for conn in connections:
        astar.connect_points(conn[0], conn[1])

    var path = astar.get_point_path(10, 12)
    print(path)

It prints

[(1, 0, 0), (0, 1, 0), (1, 2, 0)]

Comments

The extending of AStar to ignore euclidean distance worked perfectly. I had presumed incorrectly from the docs that _compute_cost and _estimate_cost dealt with the distance & weight when computing the cost between two points. Your answer confirmed that it only deals with the distance.
hllfazer is the man! Thank you!