Caching for pathfinding computation
US5978730A · kind A · utility
Assignees
Inventors
Key dates
| Filing date | Feb 20, 1997 |
| Grant date | Nov 2, 1999 |
| Priority date | — |
| Expiry date | Feb 20, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG01C21/3446
- WIPO fieldMeasurement
- WIPO sectorInstruments
Abstract
A system for computing a path in an electronic map (or other network) starts a pathfinding exploration in the background while the system is waiting for a request to find a path. The system automatically chooses an origin. The system's memory can be divided such that a portion of memory acts as a cache. The data for the nodes in the electronic map are loaded into the cache when needed. The system terminates the pathfinding process when a predetermined condition occurs; for example, a predetermined percentage of the cache is filled. When the system terminates the pathfinding process, the system can start a new pathfinding process from a new origin. Thus, when a user requests a path to be found, the pathfinding process begins with data already loaded in the cache.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.