Multi-Target Search in Euclidean Space with Ray Shooting

Authors

  • Ryan Hechenberger Faculty of Information Technology, Monash University, Australia
  • Daniel D. Harabor Faculty of Information Technology, Monash University, Australia
  • Muhammad Aamir Cheema Faculty of Information Technology, Monash University, Australia
  • Peter J. Stuckey Faculty of Information Technology, Monash University, Australia
  • Pierre Le Bodic Faculty of Information Technology, Monash University, Australia

Keywords:

Search In Goal-directed Problem Solving

Abstract

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