Cover-based Pathfinding

Project Update 1.2

Cover has now been implemented and can be easily added to the scene using the coverpoint prefab. It is represented as a white wired box in the editor as you can see below:

I've also been doing a few modifications to the code, optimizing it so that the pathfinding doesn't get called as often (I had accidentally set it to be called every time the mouse button was pressed instead of released), added a new button to the pathfinding inspector and created a new script which allows the user to drag the actor and enemies (red boxes) around the level.

With my framework nearly finished, I started experimenting with taking cover into account in the pathfinding algorithm. I started with a really basic technique which adds a cost to all waypoints which are not considered as cover. The red line shows the shortest path while the green line shows the path that favours cover.

The technique is not entirely accurate but it can easily be fine-tuned to fit in with the current level by adding or removing weight on the non-cover waypoints.

Project Update 1.1

I've finally implemented the A* algorithm into my pathfinder script, so my actor can now move from one waypoint to another while avoiding obstacles. Here's a small video demonstrating it:

Customising The Inspector

I had a hard time finding information on how to create a custom inspector in the unity editor, so I’m going to start by sharing a few links that helped me a lot.

First of all, Unity has a bit of documentation on the editor and how to extend it. Those two links are full of useful information and should definitely be read.

However, for my project, I wanted to be able to add a button to my inspector and wasn't able to gather enough information from Unity's documentation to do so. I figured out how to do this by reading this great article which explained quite a few ways to use and customise the editor.

Once you know what to do, creating a custom editor is quite simple really. Below is the script I used to override my pathfinder inspector. Hopefully the comments should explain everything that needs explaining.

My pathfinder inspector now shows a button which links all waypoints together in editor mode, allowing the user to check the path coverage without having to run the application.

Project Update 1.0

This is the first of a series of updates that will be posted as the project moves along. I’ve done quite a bit of work so I won’t go into too much detail.

First of all, I’ve been familiarizing myself with Unity by following a pretty cool tutorial which you can find here: platformer tutorial. This allowed me to get used to the interface as well as learn how Unity uses components and scripts.

Once I was familiar with the editor and scripts, I started working on the actual project. The first thing I did was implement a basic framework for my project which consisted of a floor, a few obstacles (green objects), a basic camera to view the scene and an actor (orange block) that could move to a given position.

The next step was to start implementing pathfinding functionalities. I started by creating a waypoint script which allows the user to place waypoints on the scene in editor mode and then created a pathfinder script that linked those waypoints together. In order to have those working in editor mode, I had to end up writting a custom inspector for the pathfinder (you can find more information about this on another post I wrote).

I am now working on implemenating the A* algorithm into the pathfinder as well as creating a path script who will be used by the actor to get from one place to another.

Unity

About Unity

Unity is a free game development tool which allows you to easily create 3D games for different platforms. It is made up of an editor allowing you to easily change your game contents through a visual interface and an engine allowing you to execute the actual game. It is component based and supports different scripting languages as well as C#.

Why use it?

There are several reasons I chose Unity for my project. The first one of them is that I wanted to be able to show off my results visually without having to spend too much time implementing a graphical interface. Unity allows me to do so in 3D with no extra coding needed. The second reason is that I had never actually used the Unity engine before and I wanted to expand my knowledge and skills. Since Unity doesn't have a high learning curve and I already knew C# (one of the languages used for scripting in Unity) it seemed like a good idea to use it as part of my project. Finally, when I started my project, Unity didn't have pathfinding integrated into yet (unlike other engines such as Unreal Development Kit) which allowed me to create the pathfinding from scratch. However, the next release of Unity (version 3.5) will handle automatic navigation mesh generation and pathfinding. The beta version is already released and available for testing.

Pathfinding in Unity

As I previously mentioned, the version of Unity I am currently using (3.42) doesn't have pathfinding integrated into it. However, some users have provided packages and scripts implementing pathfinding for other users to use in their own projects.

AngryAnt's path project is available on Unity's assets store and is free to use as well as extensively documented. It allows the user to create waypoints and link them together in the editor using the Navigation inspector which is something that I definitely want to implement in my own project.

Arongranberg's A* Pathfinding Project is also available on the asset store and consists of two versions, one of them free. The project is more extensive than AngryAnt's as it also includes automatic navmesh generation, handling of many different graph types, use of path modifiers and support of different heuristics.

UnifyWiki (the wiki for unity related scripts, shaders and tutorials not included in the Unity package) also has a few examples of pathfinding scripts, including AStarHelper and WaypointMaster. Those scripts are pretty simple and while they provide an understanding of pathfinding, they do not however provide in-editor functionalities like the packages mentioned above.

Project Specification

Working Title

Cover-based pathfinding

Overview

The objective of this project is to develop a pathfinding algorithm derived from A Star that will take into account cover points. The algorithm will be demonstrated on the 3d game engine Unity.

Problem

Most of today’s FPS-like games now implement a cover system accessible for both the AI and player. In order for the AI to look as “intelligent” and human-like as possible, it should take full advantage of the given cover system when navigating the game environment. This means that instead of always taking the shortest route to its goal, an AI agent should be able to take the shortest route with the most cover points providing it with protection in order to reach its goal.

Research

In order to develop the AI navigation system, I will research different types of environment representations and pathfinding algorithms as well as their implementations.

The research on environment representation will mainly focus on grids, pathNodes and Navmeshes. It will look at each technique’s pros and cons in order to select the one most suitable for the project. Environment representation isn’t the focus of this project and therefore it will not be automatically generated but manually inserted by the user.

The pathfinding research is going to be more expansive as it will explore different pathfinding algorithms and ways to expand them, trajectory smoothing and multiple heuristic constraints.

Methodology

I will use evolutionary prototyping for my methodology. My project will be divided into phases focusing on different aspects of the problem, which will be prototyped one after the other, each one building on top of the previous version. The first phase will focus on implementing environment representation, the second will use it to implement pathfinding and the third will allow for user input to change runtime variables.

For each phase, I will first identify the basic requirements for the prototype and then develop it. Once done, I will test the prototype and depending on whether or not it meets the requirements set, change the specifications and prototype. If I am satisfied with my prototype, I will keep as a base for the next prototype.

Objectives

Personal objectives include:

learning how to use and program for Unity
gaining a better knowledge of environment discretization
learning about and implementing pathfinding algorithms

Project objectives include:

getting AI characters to follow a given path
implementing heuristic pathfinding taking cover points into account
allowing user input to change AI position and destination