I need to visualize the area that can be reached from a point with a maximum path length / cost.
This is with a RecastGraph and minor performance hits are acceptable for this specific feature (it’s for the turn-based component of a game that switches between real-time & turn-based).
So far i found that i can get the reachable nodes within a certain distance using a ConstantPath and a properly adjusted weight limit. From that i can construct a mesh etc. for the visualization.
But that doesn’t give me the exact outer borders of the reachable area, especially not for bigger triangles in open areas (part of the area a triangle covers might be out of range). I guess i could identify which nodes from the ConstantPath have vertices that are not in range, find the points on the edges that are just in range, modify the triangle for that node …
… but that seems a little crude and expensive.
What would be the best way to do this?
And what do the costs/weights signify exactly in this case - cost/weight to reach some point on the triangle or to reach the nodes position?
This is quite tricky and I am actually not so sure how to solve it efficiently.
To get a really accurate cost to get to a point, the funnel algorithm needs to be applied to the path, and that is not possible to apply unless you know the exact end point.
After doodling a bit in photoshop, I realize that this is a really hard problem if you want to do it exactly. I sort of know how to do it… But it would require lots and lots of stuff (pathfinding is however not included, or ok, a simple version of it is required, but not a major part). It would also require boolean operations on polygons which requires other libraries.
Then of course, this is if you need a very precise border, otherwise you might be able to do a binary search over distance for each n degrees to find the maximum distance in that direction before the path distance is too high and construct a mesh from that. It would not be particularly precise, but if you smooth the border it would at least (hopefully) look good and have ok precision, and that might just be enough.
Ok, i missed following up on this for… two years already - sorry, was busy and did not have much time for side projects
Do you still have an opinion on how to do this for getting a relatively precise border?
I.e. it should not differ much from the actually reachable area as the result would be used to a) visualize the reachable area and b) constrain the possible movements.
I’m happy to try myself on this if i had an idea of what a somewhat efficient approach is and could be confident to get results that are not far off from the pathfinding results.
If you use a pretty high resolution grid graph you can just use a ConstantPath and get it that way. Check out the PathTypes example scene (it’s in the pro version only) and select the ConstantPath from the list to the left.
That would be straight-forward, but bad for memory foot-print & presumably performance (real-time movement is not restricted to a certain range).
But i can move the question elsewhere i guess as it’s not really a problem for this project, i was just reactivating this and saw that you mentioned that you have ideas on how to solve this.
