«
Changhao Li
Software Development
Group Pathfinding in a Real-Time Strategy Game
For my thesis , I wanted to study artificial intelligence ( AI ) and pathfinding . The main goal of my thesis was to keep entities in a coordinated and coherent manner as they are moving and to quickly find a path on a complex and massive map . To achieve this , I developed an approach that combines Flow Field and Hierarchical A * for AI pathfinding and implemented Flocking behavior for AI formation movement .
In my artifact , I used the Flocking behavior , including Alignment , Cohesion and Separation , to simulate a natural group movement . Each AI within a certain range can adhere to a group and move with same direction without collision with each other .
After that , I used heat map and Flow Field to guide AI following the vector that points down the gradient of the heat map until
they reach the target . The Flow Field can be shared among AI with a set of common destination .
Lastly , in order to decrease the computational effort while pathfinding on a large map ( such as a grid with 1000x1000 tiles ). I used a hierarchical concept of which the main idea is to divide and conquer , breaking down the large map into smaller clusters to plan a path among clusters with a low amount of CPU time . This is then followed by returning the abstract path and generating Flow Fields along it to present inexpensive and robust group pathfinding .
I spent around seven months researching and working on this project . I learned many AI techniques , and after investigation , it helped me to understand how the AI pathfinding works in commercial RTS games .
86 SOFTWARE DEVELOPMENT