All-angle pathfinding algorithm?
I have a small problem with finding a decent pathfinding algorithm. Dijkstras is super. Unfortunately it can only find paths that go along the edges of a graph. In other words, only a limited amount of angles.
I have an example: If you want to find the closes way between two points in a plane, the air distance will be the closest if the plane has no obstacles and lets you move with the same speed everywhere. Say that instead of a simple plane, you have a square grid, where every square lets you move over it in a unique speed. If you where only allowed to move in the directions north, south, east and west, maybe as well north-west, north-east, south-west and south-east, the problem of finding the fastest path could be easily solved with Dijkstras algorithm. But if you are allowed to move in any angle, for example 30 or 40 degrees, allowing you to take a short cut over the edge of a square, the problem gets much more difficult. Is there some way to use Dijkstras anyway? How would you solve the problem? Any suggestion is welcome.