Offline Grid-Based Coverage path planning for guards in games

• URL: http://arxiv.org/abs/2001.05462v1
• Date: Wed, 15 Jan 2020 18:28:27 GMT
• Title: Offline Grid-Based Coverage path planning for guards in games
• Authors: Wael Al Enezi, Clark Verbrugge
• Abstract summary: We introduce a novel algorithm for covering a 2D polygonal (with holes) area. Experimental analysis over several scenarios ranging from simple layouts to more complex maps used in actual games show good performance.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithmic approaches to exhaustive coverage have application in video games, enabling automatic game level exploration. Current designs use simple heuristics that frequently result in poor performance or exhibit unnatural behaviour. In this paper, we introduce a novel algorithm for covering a 2D polygonal (with holes) area. We assume prior knowledge of the map layout and use a grid-based world representation. Experimental analysis over several scenarios ranging from simple layouts to more complex maps used in actual games show good performance. This work serves as an initial step towards building a more efficient coverage path planning algorithm for non-player characters.

Related papers

• Evolutionary Tabletop Game Design: A Case Study in the Risk Game [0.1474723404975345]
  This work proposes an extension of the approach for tabletop games, evaluating the process by generating variants of Risk. We achieved this using a genetic algorithm to evolve the chosen parameters, as well as a rules-based agent to test the games. Results show the creation of new variations of the original game with smaller maps, resulting in shorter matches.
  arXiv  Detail & Related papers  (2023-10-30T20:53:26Z)
• PlotMap: Automated Layout Design for Building Game Worlds [4.74497343690049]
  We introduce an extra layer of plot facility layout design that is independent of the underlying map generation method in a world-building pipeline. We present two methods for solving these tasks automatically: an evolutionary computation based approach throughCMA-ES, and a Reinforcement Learning (RL) based approach. We develop a method of generating datasets of facility layout tasks, create a gym-like environment for experimenting with and evaluating different methods, and further analyze the two methods with comprehensive experiments.
  arXiv  Detail & Related papers  (2023-09-26T20:13:10Z)
• Efficient Ground Vehicle Path Following in Game AI [77.34726150561087]
  This paper presents an efficient path following solution for ground vehicles tailored to game AI. The proposed path follower is evaluated through a variety of test scenarios in a first-person shooter game. We achieved a 70% decrease in the total number of stuck events compared to an existing path following solution.
  arXiv  Detail & Related papers  (2023-07-07T04:20:07Z)
• CCPT: Automatic Gameplay Testing and Validation with Curiosity-Conditioned Proximal Trajectories [65.35714948506032]
  The Curiosity-Conditioned Proximal Trajectories (CCPT) method combines curiosity and imitation learning to train agents to explore. We show how CCPT can explore complex environments, discover gameplay issues and design oversights in the process, and recognize and highlight them directly to game designers.
  arXiv  Detail & Related papers  (2022-02-21T09:08:33Z)
• Spatial State-Action Features for General Games [5.849736173068868]
  We formulate a design and efficient implementation of spatial state-action features for general games. These are patterns that can be trained to incentivise or disincentivise actions based on whether or not they match variables of the state in a local area. We propose an efficient approach for evaluating active features for any given set of features.
  arXiv  Detail & Related papers  (2022-01-17T13:34:04Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Using Tabu Search Algorithm for Map Generation in the Terra Mystica Tabletop Game [60.71662712899962]
  Tabu Search (TS) metaheuristic improves simple local search algorithms by enabling the algorithm to escape local optima points. This paper investigates the performance of TS and considers the effects of the size of the Tabu list and the size of the neighbourhood for a procedural content generation.
  arXiv  Detail & Related papers  (2020-06-04T09:15:46Z)
• Map-Enhanced Ego-Lane Detection in the Missing Feature Scenarios [26.016292792373815]
  This paper exploits prior knowledge contained in digital maps, which has a strong capability to enhance the performance of detection algorithms. In this way, only a few lane features are needed to eliminate the position error between the road shape and the real lane. Experiments show that the proposed method can be applied to various scenarios and can run in real-time at a frequency of 20 Hz.
  arXiv  Detail & Related papers  (2020-04-02T16:06:48Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.