Tamer Sioufi
System - Anomaly Highlights
Spatial Partitioning
Considering System - Anomaly is a prototype set in space, I needed a way to create 3D space movement. There are a few industry standard ways to do so. We can divide the map into voxels, or grids and partition it that way, we could use a bounding volume hierarchy which uses a tree-like structure.
​
For my project, I decided to go with the spatial hashing grid method, which involved subdividing the playable level into a fine grid cells, to which we can use as the basis for refined movement, pathfinding and obstacle avoidance systems.
The Grid Manager
I began by creating a grid manager. The grid manager would serve as the basis for my spatial partitioning system. The grid manager serves as the single source of truth for the grid cells. It would keep track of these cells, the map bounds, and general level information regarding the map extents and the grid extents.
It tracks whether the grid cells are occupied or unoccupied. It also holds some of the functions that will be used for pathfinding as well as spatial queries, which I’ll discuss later.
​
The grid manager initially computes the maps bounds, as well as the grid origin and total number of cells. This is based on a few variables, such as the map size, and the cell sizes. Both of which are editable.
After computing the grid bounds, the grid manager begins computing all grid cells. The grid cells are stored in a flat 1D array which allows for more efficient memory usage. The grid cells each hold their respective world locations, as well as whether they are blocked, and if so, to what extent. They also store their cell neighbours.
​
These are useful for a variety of functions, such as registering blocked states for obstacle avoidance and cell neighbours for faster pathfinding times.
​
If we look at the below image of a cube with it's vertices highlighted, it illustrates how the neighbouring cells work. Each cell (assuming it's not on the edge of the grid bounds) has 26 neighbouring cells. A cube has 26 neighbours because it has; 6 faces, 8 corners and 12 edges. Each has a neighbour that we must calculate the index of and assign.​
So for example, if we have around 5,000 grid cells and each cell has 26 neighbours (not including edge cases where some cells will have less due to being at the edge of the grid bounds). 26 * 5,000 = 130,000 calculations. This far exceeds Unreal Engine's loop limit and would return an infinite loop. To avoid this I used a process called batch processing. During the loading and initialisation phase the grid manager will process the cell neighbours in batches via a timer, spreading calculations out across frames.
This process is called batch processing and helps maintain frame rates while computing and avoids crashes.
Once completed the grid manager lets the game state know it has completed it's loading and is setup for it's processes in game.
​
Below is a representation of the grid cells in engine.
Once the grid manager is initialised, other objects and actors in the scene can report their position to the grid manager. This allows each cell to keep track of if it's blocked and to what extent.
​
For example when the player calls in reinforcements, the ships calculate their position and send it to the grid manager, which registers this position to all relevant grid cells. This is the basis for the obstacle avoidance and pathfinding system.
Optimisations
Due to this prototype being a blueprints prototype using Unreal Engine's native visual scripting language, blueprints, optimisation is required. Blueprints have a rough 7ms latency between nodes and thus for advanced systems like this making sure the grid and pathfinding are efficient for many units is vital.
​
For the pathfinding system (which I will cover in more detail on the next page), the grid needs to be able to find the fastest path to a location. To do this I am using the industry standard A* algorithm, which involves searching the most promising cell neighbours first. This slows down the more cells there are however, and if I reduce the number of cells then that leads to lower accuracy in both the pathfinding as well as obstacle avoidance and partitioning. So I went for an alternative solution. I created a sector hierarchy.
​
The sectors encompass the regular grid cells, each grid cell is assigned to a sector. The sectors would handle the high level path from the start to target location, and the grid cells would deal with the low level paths. Due to the sectors being much larger than the grid cells, when a group of units are selected and instructed to move to a far point on the map, a sector to sector pathfinding function is called once for all selected units in the sector. This is much faster since there are few sectors that are needed to encompass the map and the sector to sector pathfinding is only done once for all units within the sector. This serves as the 'high level path' and units will run the low level A* search within each sector, drastically reducing the number of calculations.
The red boxes you see above are the sectors. As you can see they are far fewer and encompass a large area, massively improving performance.
