Text

Bounded-Search Pathfinders Based on Influence Maps Generated by Attractors and Repulsors

This article combines pathfinding and influence fields (or influence maps) in a way that the influence costs replace the traditional distance costs. By placing repulsors and attractors in the game world, we are mixing their influence fields into an overall game influence field, which determines the influence costs in finding a path between a start and a goal node. For that purpose, we introduce an automated method to place such attractors and repulsors, which builds upon the concept of thinning graph (and its dual). This thinning graph is a sort of medial axis of the set of passable tiles of the game map. As a result, we obtain bounded-search pathfinders that avoid obstacles (repulsors) and follows checkpoints (attractors) in an intuitive manner. Moreover, the well-known problem underlying the influence fields, called local extremum trap (i.e., an agent may enter into a place from where there is no escape away), is solved in an elegant way. Also, our influence-driven bounded-search pathfinders are comparable to other influence-based pathfinders in terms of memory expenditure and time performance.

Ketersediaan

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON GAMES; Vol.13 No.1 March 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 35 - 49

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

MOTION PLANNING
PATH PLANNING
SPATIAL REASONING
INFLUENCE MAPS
PATHFINDING

Info Detail Spesifik

DOI: 10.1109/TG.2019.2937780

Pernyataan Tanggungjawab

Gonçalo N. P. Amador, Abel J. P. Gomes

Versi lain/terkait

Lampiran Berkas

Komentar