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?

asked Nov 27, 2019 in Engine
edited Nov 30, 2019

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

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
]

for point in pointsToWeight.keys():
var id = point.x * 10 + point.y

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)]
``````
answered Nov 27, 2019 by (2,154 points)
selected Nov 27, 2019 by eod

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!