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

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By eod

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?

2
:bust_in_silhouette: Reply From: hilfazer

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)]

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!

eod | 2019-11-27 18:39

1 Like