Pathfinding for Square Grids (diagonals shorter than straight lines)

General Grid graph
#1

I’ve been using the TBS example as a base for my game (2D using a grid shaped graph) – and I’m loving how it works. However, it doesn’t quite seem right to me that the diagonals are shorter than the horizontal/vertical distances. For example, if an ability’s range/players movement is 4 – the horizontal range is 4 but the diagonal is only 2 nodes.

I’m using the code below to generate a path. Is there a simple way to change this for it to make a square around the player instead a circle?

public static ConstantPath Construct (Vector3 start, int maxGScore, OnPathDelegate callback = null) {
var p = PathPool.GetPath();

		p.Setup(start, maxGScore, callback);
		return p;
	}

Thanks,
Ty

Pathfinding_Distances
Pathfinding_Distances936×765 44.8 KB

#2

Hi

if you want this you can set uniformEdgeCosts to true. I think that if you set the grid graph to use the Advanced shape mode, then this will be an option.

You can also use PathUtilities.BFS which completely ignores edge costs.

#3

Thanks for the response!

I can’t seem to find uniformEdgeCosts-- is it in the inspector in the grid graph tab? I’m using version 4.2.15

#4

Since I cannot find uniformEdgeCosts in the inspector (image attached), is there a way to set it to true in a script?

If not-- how would one go about implementing PathUtilities.BFS? Would it be after the start path() function or in the traversal provider?

Thanks!
Ty

pathfinding_inspector
pathfinding_inspector499×1120 77.4 KB

#5

Hmm. I checked the code. I think I must have misremembered. It is not possible to set this unless you are using a hexagonal graph.

I think your best option is the BFS.
BFS is completely separate from the path.

You can use it like

var seed = AstarPath.active.GetNearest(transform.position, NNConstraint.Default).node;
var nodes = PathUtilities.BFS(seed, 10);
foreach(var node in nodes) {
	Debug.DrawRay((Vector3)node.position, Vector3.up, Color.red, 10);
}
#6

I’ve added this piece of code right before generating a path in the movement script (image below). It still comes out with the diagonals shorter than the horizontals.

Do you have any suggestions on where to place this code?

Pathfinding Issue_2
Pathfinding Issue_2991×810 46.7 KB

Pathfinding Issue_2Code
Pathfinding Issue_2Code955×679 67.5 KB

#7

Do you have your grid graph configured to use 4 neighbours instead of 8?

#8

I do! That solved the square gizmo problem-- but ConstantPath and the traversalProvider aren’t using the new set of nodes though. Is there a way to take the nodes that use the BFS and make ConstantPath.Construct use them?

Also, I had the grid graph using 4 neighbors instead of 8 because I don’t want them to be able to cut in between players incase they are being trapped by them (image below)-- but I suppose adding more enemies and making sure there aren’t gaps in barricades can help and make things simple!

Pathfinding_4
Pathfinding_8

#9

When using BFS you would not use a ConstantPath at all. The BFS replaces the ConstantPath.
The output from a constant path is a list of nodes, and the output from the BFS is a list of nodes, they do very similar things.