shortest walk - path points off grid

I have been working on very large floor plates, generating shortest walks for 80-180 spaces. The calc times are in the 3-4 minute range and we have many iterations and schemes to analyze. So, adding too much complexity is to be avoided if possible.

I can't include the actual work but the attached files spell out the issue I am having.

The paths (as the crow flies) are from center to center of every space on a given set of layers. These spaces and other voids must be avoided in the final walks.

The problem comes when the shortest walk component finds the nearest point on the grid and starts the walk from there. see the path highlighted below.

It would be fantastic if the SW component would consider the nearest several points on the grid before calculating the walk.

My only thought will be to draw additional grid lines from the center points to the nearest 15-20 grid points. But nearest point or containment calcs are costly when dealing with so many spaces...

Does anyone else have a similar issue? If so, how did you solve it?