Blog post #1 : Overview
BLOG POST #1
Hi,
I am planning to regularly post here information about the actual state of the development, and also about the details of the RTS system, to let you understand better what it really is. Let’s start with a basic overview!
Overview
Background
Beside the rendering limitations of GPU+CPU, controlling many units while running a strong AI results in significant CPU load too. Doing many pathfinding searches, and selecting the right behavior in this scale, while maintaining a relatively high and smooth FPS is not an easy job. Beside this high load, it is a general requirement in RTS games to support various sized units with very different movement capabilities, what can highly increase pathfinding related data requirements. Furthermore, game AI must be fed by a good database, what should be used with, and practically tightly connected to the pathfinder system.
Description
Finally, I found the available NavMesh and simple tile based systems not suitable for this purpose (even the time sliced ones), and after a long research and testing, I established my own “little” system, which is very close to what you can see in Company of Heroes: a tile and cluster based two level hierarchical pathfinding, supporting more (by default 4) unit capabilities, and different unit sizes by using so called clearance maps. It means you can have e.g. infantry, cavalry, and siege units on ground plus ships on water, and in all capability categories the pathfinder supports 1x1, 3x3 or larger unit sizes (measured in tiles). What makes it hierarchical: **tiles are used for short range unit pathfinding, clusters are used for long range group pathfinding. **
This method has the following benefits:
- a significant decrease in search times beside producing optimal paths,
- paths can be** dynamically updated with low performance cost**, resulting in fast response to environment and enemy troop position changes,
- allows detailed environment evaluation, supporting advanced AI behavior, and enabling to set player units and groups to auto mode, by defining their task without micro-managing them continuously.
It is also essential to **handle the ever-changing environment **effectively runtime, like rising and destructing buildings, so the RTS map database is divided into static, stationary, and dynamic sections to manage it fast enough.
To have a good visual debugging system is another must, and widely used with more options, some of them are available through editor checkboxes, but most of them only by C++ defines and preprocessor directives, to have an optimized game code finally. Currently it is solved by UE4 standard DrawDebugBox(), DrawDebugPoint(), and DrawDebugLine() functions, but a faster, shader based debug view option is planned in near future using dynamic textures for landscape, terrain models, and buildings.
A final cluster arrangement (used by the long range pathfinder) can look like this, with a basic debugging visualization showing tile correspondence to clusters:
http://s26.postimg.org/6bylqroeh/RTSMap_Clusters.png
At high slope regions they are subdivided into smaller ones for more optimal pathfinding, what can be also checked by a simpler, less performance eater debugging view (cluster middle tiles are also represented):
http://s26.postimg.org/nb7k60zm1/RTSMap_Cluster_Under_Mouse.png
**Processing the level
**
Of course, the pathfinder and AI system should understand the game level geometry. This is done by the map decomposition system, which is done simply by an actor that you can drag into the game level, set its size given in tiles, and define tile and default cluster size. Just hit generate, and it will create the pathfinder maps in the following sequence:
Static part:
- create basic tile and cluster database, clusters (small areas) with a uniform distribution and shape,
- measure the surface of landscape and terrain models, set tile properties based on slope,
- set cluster properties based on included tiles, subdivide them into more specific ones if needed, evaluate special areas like hill-side, hilltop, summit, deep water, shallow etc.
Stationary part:
- detect instanced static mesh components and actors (small obstacles),
- detect large obstacle and building actors, create new clusters if needed, set their properties if a database available (otherwise set these areas impassable)
The above described map decomposition process can be generated in more ways:
- design-time for pre-made maps (requires more disk space, but fast on game start),
- on startup for random maps (slower map loading time),
- combined: make the slower map surface detection (static part) and evaluation on design time, and do the fast actor processing (stationary part) on game start (useful when only building and vegetation arrangement differs),
Moreover, all the three method can be used also for levels consisting of more sub-levels, loaded in mosaic arrangement or by world composition (WIP).
The final result is the stationary clearance map (used by the short range tile pathfinder):
http://s26.postimg.org/ewwivonyh/RTSMap_Stationary_Clearance.png
Special objects
This custom RTS system utilizes some special objects, usually inherited from ARTSEntity abstract actor class:
- small obstacles: little objects should be avoided by units, can be destroyable or used for resource gathering, cannot be owned,
- large obstacles: similar to small obstacles, but they have their own cluster, resulting in better pathfinding,
- buildings: like large obstacles, but can be owned, and additionally they can contain tile and cluster data of their floors, i.e. they can be used to make a siege game with towers, gates, and defenive walls (currently csv files store the tile and cluster data (surprisingly easy to create it with Excel or OpenOffice), but it is planned to make a building editor level or blueprint,
- units: can be owned, controllable builder/gatherer/fighter actors, normally with a skeletal mesh or static mesh component, capable to do short range tile pathfinding to the assigned desired target tile, executing and optimized movement,
- groups: can be owned, can contain large number of units and organize them into different formations, automatically order units where to move and what to do based on group order received from player or AI; capable to do long range cluster pathfinding, but also does short range tile pathfinding in complex environments e.g. in bottleneck situations or labyrinth like regions to have a snake like shape,
And there are many other smaller or larger, but definitely important classes and structs handling formations, reading in formation data files, tile pathfinding, cluster pathfinding, reading building data files, animation sets etc. They will be detailed when editor functionalities are introduced in a later post.
**Planned or WIP Features
**
- container buildings (town center, mines, defensive towers),
- carrier units (ships, vehicles, siege towers),
- save/load system (based on the custom ID system),
- main menu
- advanced player system (supporting more civilization tech trees),
- multithreaded tile and cluster pathfinders,
- multithreaded static map decomposition,
- movement prediction (better collision avoidance in crowded areas),
- more realistic vehicle pathfinding and movement, calculating with turn radius (based on Marco Pinter’s article and demo),
- hexagonal or octagonal base clusters shape beside the existing rectangular ones,
- influence maps and potential fields for game AI
Thanks for reading!