Grid graph ignoring AddConnection cost

Beginner Questions
#1

Hello,

I got a problem with setting up cost for neighbouring nodes. AddConnection doesn’t seem to work?.

Using grid graph with 2d project. I checked the documentation and it doesn’t seem like i need to set up anything special for it to work.

All nodes are walkable (as see on the first screenshot with tiles and i tried disabling them (make them unwalkable as shown in the code snippet) so i can be sure i am touching the “right” tiles.

StartCoroutine(ExampleCoroutine(5, 2, 1000)); // this is the one with the arrow on the picture
StartCoroutine(ExampleCoroutine(5, 3, 1)); // this is the one above the arrow where i would like agent to go

I made a test by trying to walk unit from tile with the arrow to the one right of it (and if there was a cost it would have to go around on the top one? (i have 4 directions grid graph)

Thank you. Please tell if I can provide any other info.

image

image
image732×337 14.2 KB

EDIT: some additional info, i use (Node size : 1) so setting a cost of like 1000 should be way more than enough for my use case.

#2

i have decided to rework my project into PointGraph, as I have concluded GridGraph ignores connection cost fully and might not be what i need (was reading some previous threads etc to get to this conclusion)

Thank you anyhow. Will bother if stuck again but got a bit better grasp of it all now :slight_smile:

#3

Hi

Grid graphs store connections to neighbouring nodes in the grid in special way. They all share for example the diagonal connection costs to save memory and improve performance.
This means that AddConnection will indeed add a connection to the other node. However it will not replace the internal grid connection (which is stored in a bitpacked field). So the pathfinding algorithm will have the option of two different connections, and it will naturally choose the cheaper one.

If you want to replace a grid connection you can disable the grid connection and then add your custom connection.
Use

node1.SetConnectionInternal(direction, false);
node2.SetConnectionInternal(oppositeDirection, false);

where the direction is mapped to X and Z coordinates as:

         Z
         |
         |

      6  2  5
       \ | /
 --  3 - X - 1  ----- X
       / | \
      7  0  4

         |
         |
#4

oh, will try this out. If i understood correctly if i clear all the connections (which are added by default) and then add a new connection which has a cost of lets say 10, it should work as I intended.

Will stash my changes and try this now. Awsome.

#5

Yes, that will work.

Note however that the A* algorithm relies on not only edge costs, but also on something called the heuristic which is used to estimate the remaining cost of the path. For the algorithm to work the actual cost of the path must be equal or higher to what the heuristic calculates. This is called an “admissible heuristic”. The heuristic is by default the world space distance multiplied by 1000 (this is also the default cost between nodes). So a connection cost of 10 is (unless you have a really tiny graph) too small, and the A* algorithm may not produce the optimal path because the heuristic will no longer be admissible.
You can disable the heuristic by changing A* Inspector -> Settings -> Heuristic. But note that this will reduce the A* algorithm to Dijkstra’s algorithm, which is a lot slower. See https://arongranberg.com/astar/docs/pathfinding.html#Heuristic

#6

just tested and this seems to work flawlessly. Would have never got it out on my own tho.

My world space distance is exactly 1 (i set it up to make my life easier, the distance between each tile is 1) so this should work with no problems in my case.

Thank you!!

#7

Nice that it works!

Just to clarify, this means the default connection cost (and heuristic for a distance of 1) is 1000.

1 Like