A Star Parkour

What is A Star Parkour

A Star Parkour is a prototype that is meant to achieve a smooth and realistic movement in all axis for an AI character, in this case a humanoid. In the case of a lot of pathfinding systems that already exist like Unity's build in NavMesh system, they do not have realistic jumping, climbing ledges, falling, sliding animation, interaction with the environment.

How does it work

The Project is made of with a few systems working together:

• 3D Grid
• Heap Sorting
• Async Pathfinding
• In Engine Node Rendering (For Debuging and Analisys)

• How the Agent is using root motion and animation blending for accurate in world representation and awareness.

3D Grid

The Grid is calculated by using nested "FOR" loops which are cycling over every single node for the whole grid. For each node there are two checks being done. OvarlapSphere and a downwards shooting raycast.

The "OverlapSphere" checks if the node is inside of a obstacle and the raycast check if there is a ground below the node. If the node does not have ground under it and is not inside of a obsticle than it would count that node as an empty or in other worlds an Air Node. If this check shows that there is an obstacle present it will add a penalty for moving close to the obstacle.

This penalty is mainly used to create a more natural pathing behaviour. It would be more natural because otherwise the agent will walk directly next to obstacles as it would count them as the most optimal path. However if humans are told to treverse the same path most of them would choose to stay in the middle of two obstacles or at least a couple meters away. After the 3D nested "FOR" loops completes a blur function for the penalties is run to make the natural pathing effect I just discussed.

The bluring is quite simple for every vertical level of the grid it calculates a horizontal pass and a depth pass for the whole grid. Firstly the horizontal pass is done and the depth pass uses the horizontal pass array to expand and make a smooth rounded decreasing penalies the further the node is from the obstacle.

Heap Sorting

As we are using one million nodes (at least in my example) for the pathfinding the system needs a fast and efficient way of sorting and process the nodes by their f-cost (f-cost = h-cost + g-cost). The Heap sorting algorithm is a very efficient way of getting these nodes processed.

The Heap is a very effective sorting algorithm because it works with very simple rules and formulas. Every node in the heap has two children which must be with a bigger value than the parent node. As every item branches out into two other it generates sections inside of the List/Array. These sections are the exact thing that helps with sorting and searching for items. Whenever an item is added to the end of the heap, it needs to be sorted. The main value, in this case the f-cost, is compared with the parent item's f-cost and if it is smaller than the item we are sorting than the items are swapped. But how do we know which node is the parent node? This is where the very simple formulas come into the sorting algorithm.

• Parent = (n-1)/2
• Left Child = 2n+1
• Right Child = 2n+2

The "n" is the position/index of the item in the List/Array.

To find the parent index of a node is always going to be the ("child index" - 1)/2. So for example lets use index 11: 11-1 = 10/2 = 5. The node at index 5 is the parent of index 11, but we also know that every node has two children. For the node on index 12 the parent would be also 5 because of the way how integers (whole numbers) devision works. 12-1 = 11/2 = 5.5 Because it is an integer devision it will automatically be rounded down to 5.

So if the node on index 5 is the parent of nodes 11 and 12 how do we find that in reverse? If we are searching for the first or also often reffered as the "Left" child than we can use the formula 2 * "child index" + 1. So it would come out as 2*5 = 10+1 = 11. And if we are searching for the second or "Right" child the formula would be: 2 * "child index" + 2. For example 2*5 = 10+2 = 12.

As we need to constantly be removing the first item from the heap, How are heap sorting algorithms filling that empty first slot? To fill the first slot in the very efficient manner the last node in the List/Array is swapped with the first. However now the heap is not sorted. To sort it the parent is compared with the two children. The smaller one of the two is taken and swapped with the parent. This exact loop is repeated until there are no more children smaller than the parent. This is a very efficient way of sorting it because we do not even interact with any items from the other half of the heap and the deeper the sorting continues the more of the branches are ignored which saves increacingly more time as the List/Array gets bigger. The Big O notation for this sorting algorithm is "O(n log (n))".

The code for the heap can be found from the Download button, which leads to the repository, and Assets\Scripts\Heap.cs or click here.

Async Pathfinding

The basics of the pathfinding are quite simple.

Two arrays:

• Available nodes queued for processing (openSet)
• Processed nodes (closedSet)

Variables:

• Node Parent (parent)
• Is the Node in air (isAir)
• if the Node is only slidable through (isOneUnitHeight)
• if the Node is overall walkable (walkable)
• the current jumping distance (jumpHeight)

The openSet is filled with the acessible nodes from the current location. Each one is being checked for the desirable property at the time of executing each current node and neighbour nodes. Some cases, for example:

• The agent can only move trough the air nodes when jumping and/or falling
• The agent can only move horizontally in the air for the first few nodes because of the jumping force/root animation
• The agent is only allowed to slide trough tunnels when they are shorter than a number specified

All of these rules need to be translated to the pathfinding algorithm. Also as the agent cannot just start walking on air we can ignore adding certain neighbours to the openSet. This makes the immediate nodes accessible, to the agent and therefore the pathfinding, only nodes on the same height and one unit below are reachable.

The controll over what nodes are continuously being chosen for the path are stored in a Node to Node system. That system is the parent variable. It contain whichever node is the preceding node for reaching the current node. As every node, with an exeption of the starting node, will have a parent at the time of the pathfinding completion the path can be retraced and stored only after the pathfinging is complete.

How to test the project

The project was made with Unity 2021.3.4f1 version.

The preferable Unity version to test the project out in is 2021.3.4f1. However, the project should work fine with any newer versions as well, but this is not guaranteed.

Open up the project using Unity and open the scene located: Assets > Scenes > Game.unity

To test the project and its functionality you can just press play and observe how the AI's find a path and traverse the terrain to reach that path.

How to test different routes

To test different routes either by starting at a different point and/or ending at a different point. The target and/or the AI (Seeker) can be moved around.

How to position the AI (Seeker)

The seeker has to be on the ground and standing on a surface.

Preferably it should be placed so the coordinates on the X and Z values have a .5 in the number. This in the large majority of cases is not required for this version of the pathfinding system. However, if any difficulties arise it is best to position the AI (Seeker) properly.

How to position the Target

The target is the pink cube in the scene and it is also named "Target" in the Hierarchy.

The best way to position the Target is on the ground, touching the floor with it's bottom face but keeping the positioning to be .5 on every axis. For the X and Z coordinates this is not required, but it is strongly recommended for the Y axis.

Inspect the Grid and See the Path

Warning: Drawing the Grid is a very Heavy operation for a system. On a less powerful machine the project may crash Unity and/or lock up a system. Please be aware that because this is a prototype of a huge project, small things like drawing the grid would not be optimized as they are a quality of life functions and they are not used inside of a build game.

Grid

To be able to inspect the Grid that the system has build:

• Navigate to the Hierarchy > Game Manager > Grid (C# Script Component)

  • Display Grid Gizmos

  • Display Only Ground Gizmos

• Play the project and Pause (Pause is not required)

Display Grid Gismos draws all of the nodes in the grid. If the default settings, that are not changed, are tried to be drawn it will draw 1,000,000 nodes. The default size for the grid is 100 X 100 X 100.

Display Only Ground Gizmos does exactly what the name suggests. It only draws the nodes that have a surface underneath them which are able to be walked on by the seeker.

The differently coloured nodes are colour coded:

• Obstacle are coloured red

• Air Nodes (Empty) are coloured cyan

• Terrain Difficulty: Easy > Hard (Gradient) coloured White > Black

• Slidable are coloured lime

Path

To be able to inspect the calculated path from the Seeker to the Target:

• Navigate to the Hierarchy > Select the desired "Seeker" Game Object > Unit (C# Script Component)
• Tick Display Path Gizmos

This will show the path for that Seeker. This can be done for as many seekers as desired at once.

The path will be drawn in Black Squares. The also will be blue perpendicular lines that represent the turning boundaries for each node.

How to create new Scene

To make a new scene and test out everything in the project from the beginning:

• Make a new scene

• Navigate to Prefabs > EASY SETUP - UNPACK ME.prefab

• Drag the prefab in the project

• Unpack the prefab and remove all children from it

To Create terrain the ProBuilder package can be used.

For the best result please make sure that the nodes are fully positioned on the surface. This is not required but the navigation will not be perfect.

Important: Make sure any Mesh Colliders are set to Convex

Not Easily Customizable

Most of the variables that can be changed in the inspector are can be changed to affect the parthfinding without making the traversing impossible. But there are few things about the project that cannot be fully customized yet.

Things that are connected to the root motion animations are not changeable:

• Jump height (Game Manager > Pathfinding (C# Script Component) > Jump height)

• Jump height (Seeker > Physics AI Controller (C# Script Component) > Stats > Jump Height)

• Check Raycast (Seeker > Physics AI Controller (C# Script Component) > Check Raycast)

• Sliding CC Height (Seeker > Physics AI Controller (C# Script Component) > Sliding CC Height)

• Sliding CC Center (Seeker > Physics AI Controller (C# Script Component) > Sliding CC Center)

• Not recommended to change anything on the Character Controller

All of these things were not a priority for this project as the aim was to bring the project as close to game ready as possible, rather than fully customizable in engine.

3rd year university student at Falmouth University (2022 / 2023)