Spatial Distance Heuristics for Multidimensional Graph-Based Pathfinding

Overview

The least-cost graph traversal algorithm A* has diverse applications from video game pathfinding to accessibility programs for the visually impaired. While there is substantial research concerning its use in two spatial dimensions, this study investigation focuses on higher dimensionality. A* works by iterating through elements in a graph in an order based on the known distance from the start and the estimated distance to the goal, based on a heuristic function. This approach can efficiently find the path of least cost from the initial to final node, but its efficiency and accuracy depend on the distance heuristic itself. In this study, several were tested using randomized computer simulation and evaluated based on the scaling of performance over increasing dimensionality. The study provides recommendations for A* implementation in higher dimensions and analysis and research methodology for further research.

Competition history

• ISEF 2016 Category not listed · Entry SOFT008

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.