Overview

For my final year dissertation, after loving the level 5 AI module I wanted to explore how an agent navigates a scene in more depth, my level 5 AI used JPS pathfinding which just like A* works on a static environment. Thus, the most optimal path can be found for that snapshot but if the world changes the path might not be viable anymore. In doing some preliminary 2research for this project I came across this ‘AI has changed but the games industry considered the problem of pathfinding solved, rather than spending time to create a new solution the focus is to optimise and build upon A*’ (Bourg & Seamann, 2004) but as my understanding of A* was that it must be recalculated if the path changes is what cemented this topic as my dissertation.

Grade: First

Download My Dissertation Here: Download

GitHub Repo

Video of Chess AI

Reading a Map

This project was not just a deep dive into the world of pathfinding but also challenged me to question what I thought I already knew. The biggest takeaway was that the environment the algorithm is searching is just a s important maybe more so than the algorithm selected. Take figure 1 for instance, it depicts the search A* takes but as is begins its search at the start it immediately gets lost in the dead end leading to the right. Whereas D* Lite which begins the search from the goal to the start didn’t get lost for as long. Timings can be seen in figure 2.

Video of Zombies searching for the player with gunshots alerting the zombies

Results

The timings, presented here, highlights the change from A* being the best rated to worst based on the environment it needs to navigate. Taking a large amount of time to search a non-negotiable path.