Multi-Target Search in Euclidean Space with Ray Shooting
DOI:
https://doi.org/10.1609/socs.v12i1.18575Keywords:
Search In Goal-directed Problem SolvingAbstract
The shortest path problem (SPP) asks us to find a minimum length path between two points, usually on a graph. In a Euclidean environment the points are in a 2D plane and here the path must avoid a set of polygonal obstacles. Solution methods for this Euclidean SPP (ESPP) typically convert the continuous 2D map into a discretised representation, like a graph or navigation mesh. RayScan is a recent and fast ESPP algorithm which avoids the preprocessing step by using a combination of "ray shooting" and polygon scanning. In this paper we improve the performance of RayScan using spatial reasoning and ray caching techniques. We also extend the algorithm, from single-target search to a multi-target setting. Comparative game map experiments show a substantial speedup.Downloads
Published
2021-07-21
Issue
Section
Extended Abstracts