I'm seeking feedback on my pathfinding algorithm concept. The idea is not to find the absolute shortest or cheapest path, but instead to prioritize straight-line movement as the preferred option. The algorithm starts with a line of sight check for traversability. For example, if there's a wall between the start and end points, the algorithm will initially follow a straight line until it hits the wall. It then navigates along the wall until it finds a corner. At that point, it performs two more line of sight checks: one from the starting point to the corner and another from the corner to the destination. If both paths are clear, I consider it a valid route. If not, the algorithm recursively explores paths from the source to the corner and then from the corner to the destination. The goal is to determine a single valid path, while simultaneously cancelling any longer paths that are still being evaluated. There are some important edge cases to consider, such as the algorithm safely navigating around corners and dealing with scenarios where the starting point is completely surrounded. I'd love to know if you think this algorithm is sound or if something similar already exists.
5 Answers
Clarifying how you define "corners" and "walls" in your algorithm is crucial. Your implementation details could heavily influence performance and accuracy. I’d suggest examining similar algorithms, like the one referenced in an A* search animation, which outlines a trade-off between computation time and optimality.
Your concept is reminiscent of visibility graph pathfinding. You might want to check out that method since it involves precomputing the visibility graph beforehand which could streamline your calculations. It typically consists of identifying visible vertices of obstacles from both the source and target points and then using a pathfinding algorithm like Dijkstra or A* on that graph. It aligns closer to what you're proposing, but with more precomputation involved.
Your description seems to echo elements of Soukup's algorithm from 1978, which was designed for efficient maze navigation. If you're interested, I can help you track down the paper—it could provide insights that align well with your work.
You're certainly on the right track with your idea! It’s similar to "Jump Point Search" in that it aims to optimize how paths are found without exhaustive calculations through every grid point. While your approach centers on sight checks first, both aim to reduce unnecessary computations by focusing on key path points.
A technique like A* might already cover some of your ground. It uses straight-line distances as a heuristic to navigate efficiently towards the destination. It could be a good idea to compare your approach with A* since it’s well-documented and can help you refine your algorithm further.
Related Questions
How To: Running Codex CLI on Windows with Azure OpenAI
Set Wordpress Featured Image Using Javascript
How To Fix PHP Random Being The Same
Why no WebP Support with Wordpress
Replace Wordpress Cron With Linux Cron
Customize Yoast Canonical URL Programmatically