IT Carlow Project Showcase: Games Development Year 4

Academic Year: 2020/2021

Student Name: Robin Meyler

Student Number: C00231699


Project Title: GPU Accelerated A* pathfinding with the Vulkan API


This project uses the low level graphics API called Vulkan which was created by the Kronos group (creators of OpenGL) to interface with the GPU.
Vulkan allows the unification of the graphics and compute pipelines to allow me to use a compute shader to execute A* on the GPU while also rendering in 3D.
Normal A* pathfinding using a distance heuristic was used but it was adapted to work inside a GLSL compute shader which involved tracking GPU invocation index and creating an in shader priority queue.
The execution time of the compute shader dispatch was recorded before dispatch and after the GPU goes idle indicating it has finished the work, this is possible with Vulkan's synchronization with fences and sempahores.
Execution time was gathered for grids of 50x50, 100x100, 250x250, 500x500 and 1000x1000 which contains nodes from 2,500 to 1,000,000 and variation obstacle instance rates but mostly at about 10%
The grid was setup using 3D cubes with MVP with a controllable and movable camera, static cubes used a batched instance rendering to allow 30,000+ cubes be drawn in less than a second
The result of the A* paths calculated on the GPU are they displayed with agent cubes as they pathfind to the goal
IMGUI was integrated with the project to have a interactable UI for parts of the program like AI speed and zoom.

This project aims to investigate and determine the viablitity of GPU accelerated game logic tasks and to gather the execution speed at various grid sizes and agent numbers to determine this.
The results were gathered in microseconds and converted to seconds to see what possible frame impact that could be seen by the compute shader.
The results shown below on the poster show that even at high grid numbers and agent numbers that the paths can be resolved very quickly.
This test was completes on an Nvidia RTX 3070 and while this would be considered a powerful card by today's standards, in the coming years I believe this will become a common practice of GPU acclerated games logic calculations.

Demonstration video with commentary:

UI demo:

Project Poster:

Source Code: Github