Overview

This is the project which I am working on for my Final Year Project. I will be researching and comparing different methods used in the past for Vertical/3D Pathfinding in video games. Algorithms such as Dijkstra's, A* and navigation mesh are popular for simple pathfinding where the agent can walk across a walkable terrain and are used very often when developing a game - however, they do not account for complex locomotion types such as jumping, grapple hook traversal, climbing etc. The aim of my project is to investigate algorithms that can handle these locomotion types. Then, one or more of these algorithms will be selected and implemented into a test framework to visualise and capture results. If there is no viable algorithm found at the end of my research, the research and knowledge gained from this project will be used to create an algorithm which I will design myself to propose a satisfactory solution to Vertical/3D Pathfinding in video games.

My Goal for this project

By the end of the project, I should have an implementation of a game character who can use more than one type of movement to reach their given destination through the use of a vertical pathfinding algorithm conducted form my research. I aim for this to become a tool which could be implemented into any game - which would allow the developers to create an agent who can path find and traverse any map efficiently, by just entering in some key parameters for their given character. This would incredibly speed up the development process for levels and AI characters, as designers wouldn’t need to worry about placing navigation mesh links in each place of the map where the player can jump, and developers would not have to worry about programming the AI’s movement – the agent will automatically path find to any destination you give it.

My project prototype:

So far, I have managed to implement the code for a tool which generates custom Nav Mesh Jump Areas on a Navigation Mesh in Unreal Engine. The jump areas define areas which the character can jump to get to another platform. These areas are generated based on parameters which the user enters for their given character, such as max jump height, max jump distance, character height and radius etc. The character is then able to pathfind to a set destination with the use of a sequence of jumps.

Demo Video: