What type of graph should I use for my project?

I used the grid graph for the second version of my game because Aron told me it was the best for undulating terrain. I told him my game was free movement not node based, and he said it does not matter, but in practice it makes a difference.

  1. If troops do not start at the corner of a node they will walk to it to get started.
  2. I work with GetRemainingPath and the buffer to set up formations. The buffer always tends to an even node corner even if it is not the shortest path around obstacles. This is a problem because I am calculating the path of other soldiers at every point in the buffer and unnecessary points of inflection mean more calculations.
  3. The calculations that would really smooth my formations generate the exception “Axis-aligned connection not found”. This error seems to occur more often when passing a small test hill even though grid graph was recommended for undulating terrain.

I have already concluded I need a different graph. The first version of my game used the Recast graph, it had problems with hills but I never used FollowerEntity on that project so it might work. There are also 3 graphs I have never tried. So, I was hoping to hear from someone who really knows graphs.