This branch contains the implementation of the Windowed Hierarchical Cooperative A* (WHCA*): a multi-agent pathfinding algorithm, presented by David Silver in 2005 [1]. I chose to implement the algorithm in the OpenRA RTS game engine as a part of my master's thesis while studying at the University of Ljubljana, Faculty of Computer and Information Science.
To solve the multi-agent pathfinding (MAPF) problem, a collision-free path must to be found for every individual in a group of agents. Over the years several MAPF algorithms were developed by researchers who claim their approaches are suitable for real-time strategy games. However, there appears to be a disconnect between scientific research and practical game development. Algorithms are being presented and tested without considering the crucial properties of a complex game environment. To determine whether MAPF really is a good approach to the games’ pathfinding problem, we implemented Windowed Hierarchical Cooperative A* (WHCA*), a seminal MAPF algorithm, in an existing real-time strategy game engine. We then compared it to the single-agent pathfinding approach, which is used by most games in the industry. Our experimental results show that our WHCA* implementation greatly improves the path quality and agent movement, can prevent congestion and solve difficult scenarios that the single-agent approach cannot. This comes at a price, as WHCA*'s search times are found to be too long for our use case, where even a slight delay is noticeable to the players. Despite this, we think MAPF has potential in game development. Discoveries presented in this work can be helpful for future research and game development.
Link to the full thesis: https://repozitorij.uni-lj.si/IzpisGradiva.php?id=141866&lang=eng.
A short video comparing our implementation of WHCA* to the default single-agent Local Repair A* (LRA*) algorithm:
[1] SILVER, David. Cooperative pathfinding. In: Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment. 2005. p. 117-122.
Copyright 2020-2022 Ivan Antešić (ivan.v.antesic@gmail.com). Same as the whole OpenRA project, this source code is also free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. It is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. For more information, see COPYING
A Libre/Free Real Time Strategy game engine supporting early Westwood classics.
- Website: http://www.openra.net
- IRC: #openra on irc.freenode.net
- Repository: https://github.com/OpenRA/OpenRA
Please read the FAQ in our Wiki and report problems at http://bugs.openra.net.
Join the Forums for discussion.
Distributed mods include a reimagining of
- Command & Conquer: Red Alert
- Command & Conquer: Tiberian Dawn
- Dune 2000
EA has not endorsed and does not support this product.
Check our Playing the Game Guide to win multiplayer matches.
- Please read INSTALL.md and Compiling on how to set up an OpenRA development environment.
- See Hacking for a (now very outdated) overview of the engine.
- Read and follow our Code of Conduct.
- To get your patches merged, please adhere to the Contributing guidelines.
- We offer a Mapping Tutorial as you can change gameplay drastically with custom rules.
- For scripted mission have a look at the Lua API.
- If you want to share your maps with the community, upload them at the OpenRA Resource Center.
- Download a copy of the OpenRA Mod SDK to start your own mod.
- Check the Modding Guide to create your own classic RTS.
- There exists an auto-generated Trait documentation to get started with yaml files.
- Some hints on how to create new OpenRA compatible Pixelart.
- Upload total conversions at our ModDB profile.
- Sponsor a mirror server if you have some bandwidth to spare.
- You can immediately set up a Dedicated Game Server.
Copyright 2007-2020 The OpenRA Developers (see AUTHORS) This file is part of OpenRA, which is free software. It is made available to you under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. For more information, see COPYING.