Open Collections

Saller, Teresa

Efficient pathfinding on grid-based maps is a crucial aspect of many video games. Multiple algorithms have been developed to solve this problem. The DBA* algorithm leverages a database of pre-computed paths to speed up pathfinding and is both memory- and time-efficient. However, its efficiency is limited to static maps. In this work, we present a case-based system for updating the pre-computed information used in DBA* to adapt the algorithm after the occurrence of map changes. This allows us to apply DBA* to dynamically changing maps, while guaranteeing the same suboptimality as on static maps. With this new system, DBA* can compute paths faster than A* search even while performing two map updates for every path search.

Text

University of British Columbia. COSC 449

Vancouver : University of British Columbia Library

10.14288/1.0442124

Science, Irving K. Barber Faculty of (Okanagan); Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)

Undergraduate

DSpace