Hierarchical processing and caching of path solutions

摘要

Technologies are disclosed herein for providing a pathfinding service for processing and caching of path data for a grid. The pathfinding service is configured to initiate computing instances to process the path data, and to determine if an acceptable path exists through the grid. The pathfinding service may cache results for sub-portions of the grid as an overlying hierarchical representation. Thereafter, the cached results can be used to quickly determine acceptable paths for the entire grid. Additionally, the cached results may be updated when underlying information related to the sub-portions have been altered or invalidated.

主权项

1. A computer system to process a grid representing a map of a virtual space, comprising:
a processing unit; and a memory storing computer-executable instructions that, when executed by the processor, cause the processor to execute a pathfinding service configured to:
process the grid to identify a plurality of grid portions associated therewith,represent at least one grid portion as a hierarchical representation of underlying grid sub-portions, the hierarchical representation containing grid sub-portions not shared with other hierarchical representations corresponding to other grid portions, the hierarchical representation further containing a start position, an end position, and a cost,cache at least one solution for a path through the hierarchical representation of the at least one grid portion to simplify route calculations for the grid that include the at least one grid portion,receive, from a remote client computer system, position data for a route calculation through the grid,determine that a cached solution of a portion of the route calculation is available, wherein the portion of the route calculation includes the at least one grid portion,based on the cached solution, determine new position data for the route calculation, andreturn the new position data for rendering on the client computer system.