Recommendation for one grid, two connections used

General Grid graph
#1

Hi,

I make a isometric citybuilder.
I have a grid with settings 8 connections, it’s my world grid used for agent path and construction.
During construction, I can place buildings that follow a path ( ex : roads)
But roads need a path with 4 connections.
Agent can move in 8 directions however.

My grid is 1200*1200 so have 2 grids is a bit annoying.

  1. have you subjections ?
What I have

p2.PNG790×450 653 KB

[details=What I want ( done with 4 connections) but not ideal because of zigzag]

p1.PNG793×448 657 KB
[/details]

  1. Can I set heuristic from seeker or it’s just a global setting. Which heuristic do you recommend for an iso game and avoid zigzag ?
#2

Hi

Ah, so you are planning a path that you the construct a road along?
You can set the heuristic per path request.

ABPath path = ABPath.Construct(...);
path.heuristic = Heuristic.Manhattan;
seeker.StartPath(path, OnPathComplete);

You can however not set if the graph should use 4 or 8 connections per path. It is possible to introduce a switch for this relatively easily by modifying a few lines of the pathfinding core scripts. I can show you how if you want.

#3

Hi,

Ah, so you are planning a path that you the construct a road along?

Yes, the only way I found for have the shortest path and avoid buildings already build with traversalProvider.
Do you see problems to do like that ?

You can however not set if the graph should use 4 or 8 connections per path. It is possible to introduce a switch for this relatively easily by modifying a few lines of the pathfinding core scripts. I can show you how if you want.

No, I’m completely passed to 4 connections because I need 4 connections for LayerGridGraph :’( My agents will not have better path ( time perspective).

But now I have a little problem, when I set heuristic on Manhattan I have the same result that with euclidian.

p1.PNG789×447 54.6 KB

I want a result like your doc : https://www.arongranberg.com/astar/documentation/dev_4_1_8_94c97625_old/namespace_pathfinding.php#a35d651e776fc105830877a30b2c7da6a

Have you suggestions ?

Thks

#4

Hi

Is your graph rotated in some way?

#5

yes

p1.PNG695×359 21.2 KB

Also with Manhattan and scale to 1 research look like Dijkstra’s algo :

By the way, I can not use the checkbox is 2D because of that rotation. It apply 90 rotation only

#6

@aron_granberg any idea for my heuristic problem ?

Incorrect route calculation
#7

Hi

Ah. The Manhattan heuristic uses the world X, Y and Z coordinates, so it behaves slightly differently on rotated graphs (It’s hard to make it use local coordinates in the general case unfortunately, especially without performance losses).

In your case you might be able to use a variant of the heuristic that does what you want.

If you open the Path.cs script you can replace these lines

Int3 p2 = node.position;
h = (uint)((System.Math.Abs(hTarget.x-p2.x) + System.Math.Abs(hTarget.y-p2.y) + System.Math.Abs(hTarget.z-p2.z))*heuristicScale);

with these

var gg = AstarData.GetGraph(node) as GridGraph;
Int3 p2 = gg.transform.InverseTransform(node.position);
var target = gg.transform.InverseTransform(hTarget);
h = (uint)((System.Math.Abs(target.x-p2.x)*gg.nodeSize + System.Math.Abs(target.y-p2.y) + System.Math.Abs(target.z-p2.z)*gg.nodeSize)*heuristicScale);

That will make the heuristic work in graph-local space, at some cost to performance.

It still has a rotation field though. If you set that to 45 (or -45) degrees it should give you an equivalent rotation.

image.png767×630 166 KB

#8

Thanks for your tricks.
But that not working well :cry:

#9

Hi

Is your A* Inspector -> Settings -> Heuristic set to Manhattan?

#10

Hi :slight_smile:

yes and I even set it in path

var p = _seeker.StartPath(MainManager.Instance.ScreenManager.SquareToPositionCentered(_startPosition), MainManager.Instance.ScreenManager.SquareToPositionCentered(_endPosition), PathfindingFoundPath, 1 << 0);
p.traversalProvider = this;
p.heuristic = Heuristic.Manhattan;

#11

Hm… Might have something to do with floating point errors. Try this instead

h = (uint)((System.Math.Abs(target.x-p2.x)*gg.nodeSize*0.99f + System.Math.Abs(target.y-p2.y) + System.Math.Abs(target.z-p2.z)*gg.nodeSize)*heuristicScale);
1 Like
#12

That works, Thanks !

1 Like