GridGraph doesn't return optimal path

Beginner Questions
1

Hey,

I recently started using A* Pathfinding for a game prototype. The game requires dynamic generation and manipulation of graphs, so I’ve decided on using GridGraph due to speed/functionality constraints. I have got the generation and manipulation to a point that I am happy with, but I have been having some concerns when attempting to find paths on the GridGraph.

Even for paths between 2 completely unobstructed points, unless the path happens to lie completely and directly on a grid line, the resulting path doesn’t appear to be the optimal path. The following is a screenshot of an example of this (unfiltered for clarity):
https://dl.dropbox.com/u/44045318/unfiltered.png

When filtered (funnel in this case), it still provides a path I’m not completely happy with:
https://dl.dropbox.com/u/44045318/filtered.png

Is there any setting that I am overlooking to get this to return a straighter path? I’ve tried fiddling with the heuristic and with the StartEndModifier to no avail.
I’ve also tried generating a recast nav mesh, which provides much much better paths, but is obviously a lot slower to generate and doesn’t support the manipulation I require.

Thanks,
James

2

Hi

Grid graphs are being searched node by node, so you cannot expect a pathfinder to find a straight line. That must be done as a post processing step. The funnel modifier is good, but it fails so straight out some paths. To get that to work, I would recommend using the funnel modifier and the raycast simplifier (modifier) together. First the funnel modifier and then the raycast modifier to check if any shortcuts can be taken. This will not be optimal in every case, but in almost all cases it will be optimal or close to.

3

Works like a charm.

Thanks,
James

4

Great!

PS: Want to support the project? Write a nice review about it in the Asset Store or rate it. :slight_smile:

5

I’ve got some more issues with paths returned by my grid graph.

My major issue is that the path is partially going through obstacles. You can see what I’m talking about in this screenshot:
https://dl.dropbox.com/u/44045318/offgrid1.png

This can even result in positioning oneself within the obstacle:
https://dl.dropbox.com/u/44045318/offgrid2.png

My seeker’s StartEndModifier is set to ‘original’ for both start and end points and is using graph raycasting (this seems to fix up a lot of off grid issues, though not so much with smaller obstacles like in this example).
Modifiers in action are funnel and raycast (graph casts again) as previously discussed.

My goal with this is to get close enough to the obstacle to use it as cover. Also, I cannot decrease the cell size due to the size of my environments + my desire for quick graph generation.

Any advice on this will be welcomed,
James

6

My advice would be to increase either the collision check diameter in the grid graph settings or the erosion count (also in grid graph settings). Try both to see which one works best for you. This will ensure that the unit cannot get as close to obstacles.
You could also try using Thick Raycast in the raycast modifier.