I am working on path finding algorithm (using A*) for cross country movement (not for road movement) on map using grid based approach. Algorithm supports path calculation considering slope of terrain.

This algorithm is based on A* grid approach and it expands more in case of long distance with obstacle and highly dense non uniform cost weighted region. I have optimized heuristic and type of data structure of my open and close list and applied many other techniques. But as I said it is taking long time as it is working on grid. I can't increase the resolution of the grid from certain limit as area is having dense non uniform cost.

I Googled about the issue and found that if I can use navigation mesh instead of grid then it will be faster. I came across this paper which proposed a solution of using a Triangulated Irregular Network (TIN) for finding the shortest path. I am currently studying this approach.

Is there anyone who had already worked on the solution proposed in the paper for finding shortest path using TIN model. Will it be useful for my application?

Is there any other technique you think will be useful for my algorithm?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.