Which Graph Type Should I Use For This Problem?


I’m making a golf game where the gamer designs a grid based golf course and AI must find a way of playing a hole from tee to the hole. A really crude example of a hole they could play:

The AI client should prefer to hit the ball to the light green areas and generally ignore the dark green areas. The dark green areas could also be water and therefore are absolutely not on the path to the hole. The client should not take the blue line path ever.

My first attempt at this was to use a grid graph with different weights for the grid cells depending on the surface and this largely works using basic A* path finding. It breaks down in some situations where cutting across the dark green is still a lower cost.

The serious problem arises when the dark green area in the picture is water and therefore totally unnavigable. The result i want is a path along only the cells with a red dot, so have it do normal path finding on the light green but island-hop across the expanses in between.

I noticed point graph and tried this but it only returns a path with 4 nodes in the above example, one for each “island” and this is not granular enough. If there are no physical obstacles in the way then all of the light green tiles are point nodes and they all connect to eachother which means very few nodes are needed. If i make the max distance between the nodes the same distance as to adjacent tiles then the connections never hop the islands ofcourse.

What it feels like i need is either:

  1. a way of linking islands of gridgraphs
  2. a way of making sure that pointgraph nodes don’t “cross eachother” or “pass over one another” so that the connections hop islands but don’t shortcut too much.

I hope this makes sense, do you have any suggestions for how to achieve this?



Hmm, I don’t think this package is a great fit for this problem.
I think something more special cased for golf would work better. It has to know how and where the golf ball can be hit and things like that.