Heuristic process for finding the shortest path between two points

摘要

The process involves performing a test to verify whether a current node (500) is in direct vision with a destination node (501) or whether obstacles (502, 503) e.g. mountains, are opposed to each other. By-pass points around the obstacles preventing direct visibility are determined. One of the points is selected. A heuristic shortest path between the current node and the selected by-pass point and between the by-pass points and the destination node is searched, where the obstacles are represented by convex envelopes (504, 505). An independent claim is also included for a navigation device for searching a shortest path between two points.