Tamer Sioufi
System - Anomaly Highlights
Pathfinding
After laying the foundation with the grid manager, the next step was to create the pathfinding system that could make use of the spatial partitioning system.
​
The best practise would be to follow a pathfinding algorithm, and adapt it as needed. After doing some research on different algorithms I ended up settling on the A* pathfinding algorithm. It is one of the most widely used algorithms due to its speed and reliability.
​
I created and modified the A* algorithm to suit the project, creating a performant, fast and highly accurate pathfinding system. I optimised it with the hierarchical sectors and there is no tangible performance drop when multiple units move.
​
To protect the integrity of my work I won't show the modified A* search function. If you would like more information on that, please get in touch.
The A* Algorithm
​The A* algorithm is a an algorithm that prioritises searching the 'most promising' cells sequentially adding each evaluated cell to a 'closed list' until it reaches the target cell or determines no valid path exists. Its considered an 'informed' search algorithm, meaning it uses a heuristic table to help estimate the distance from a cell to the target cell.
If you start at cell (A) the algorithm will look at all of the connected cells to cell (A) and search the one with the lowest cost f (n). This cost is determined by adding two metrics, the first metric is the distance from the current cell to this connected cell we are checking, g(n). The secondary metric is the heuristic, the heuristic is the estimated distance from the connected cell to the goal cell, h(n). So the formula is as follows:
​
g(n) + h(n) = f(n)
​
Using this formula we search the most promising connected cell continuously until we get to the goal cell.
The above image is taken from an early test video of my implementation of the A* search
After creating and setting up the grid manager I started creating the A* search function. The function will return all grid cells for the unit to traverse. A separate function is called to turn these grid points into 3D vector points which is then passed to the movement component which handles moving the unit through a custom data driven component.
I modified the A* formula to avoid blocked cells, this was the basis to obstacle avoidance, as sectors register themselves to the grid and moving units will find the shortest path to the goal around the blocked tiles.
Above is an example of obstacle avoidance, you can see the green boxes showing how it avoids the space debris
Optimisations
On the spatial partitioning page I discussed how I added a hierarchical sector system, to optimise the grid and pathfinding. I leveraged this for group movement, where one high level pathfinding search is run and that is passed to all selected units, who handle the low level A* search.
Before this optimisation the fps drops for a large group of units would be 5-10, after this optimisation, there is no clear performance drop even with multiple units moving at once.
