Working on a simulated ecosystem, it was necessary to create a Search Behavior for our animals. They would use this behavior if they ever needed something, but had no memory of seeing it elsewhere (eg. I am hungry but have no memories of seeing food). Executing this behavior generates a spiral pattern out from the animal, starting at a random angle. The points in this pattern are then shuffled randomly, to create a field of points instead of a line. The reason I chose a spiral pattern for this, is simply because of how the majority of points will land closer to the animal than if we had chosen – say – a perfect circle with random distances. Which lends bias to it exploring a bit closer to home, rather than running off immediately.

• Download Search Behavior Unity package

Here is a result from one of the tests:

The red lines illustrate the order of the points. This list can be given to the animal’s “move” behavior, which cycles through it and feeds it to the Navmesh Agent controlling the animal’s movements. The bar across the middle is just to illustrate how it will not put points in a place inaccessible to the animal.

Theory:

Before I get ahead of myself, let’s take a look at how I designed the algorithm. As always, there’s a bit of math involved, but nothing you shouldn’t be able to Google in a minute or look up on Khan Academy.

When the AI agent doesn’t know where to go, it needs to be able to search through an area. I developed a solution which creates a “birds eye view” tracker, which draws a pattern on the ground that the AI agent can then follow. But just drawing a circle or a spiral isn’t enough, so here are the steps that the algorithm goes through:

1. AI agent instantiates a tracker object, passing a handful of “search parameters” into it, which dictate how the pattern will be shaped
2. The tracker translates to a location above the AI agent, from where it will calculate a spiral pattern using Sine and Cosine waves, storing the individual points to a list. Points are made via raycasting, which is configured to only collide with the “Ground” layer (ignoring trees and other environmental objects)
3. Each time the tracker checks a new point, it attempts to calculate a NavMeshPath from the previous point, so see if it the animal will be able to get to it. If not, the location is ignored.
4. Once the list of points has been compiled, their order is randomized. This is done to prevent the AI agents from running in clear spiral patterns (or smearing up against walls and hillsides)
5. Finally the list is returned so that a different algorithm can take over

The search parameters are as follows:

Search height:

The height from which the birds eye view tracker will look down onto the landscape – set relative to the AI agent.

Search speed:

The distance by which the points will be set from another. A multiplier used on the sine and cosine waves to cover more ground, without tweaking the base value of the waves.

Interval increase:

How much the sine and cosine waves should increment each step (used in base calculation and as a multiplier to produce the spiral effect) – first step starts at zero.

Search duration:

How many steps the algorithm should execute. More steps = more points on the list.

When the result is finished, the list of points passed to the AI agent is rendered in the level editor for preview. Here are a few examples with their individual settings described:

---

---

---

As evident from these samples, higher speeds and greater intervals leads to more erratic patterns. Additionally, at low intervals there is a clear problem with the algorithm: It always starts on the same values and so the spiral curve of the sine and cosine waves will always arch out right-up-left-down-right-up-etc. To accommodate for this problem, adding (not multiplying) a random number between -3 and 3 to the base calculation will offset the spiral.

If the duration is reduced and the speed and interval values are increased, much more erratic patterns can be created at a lower memory cost:

One key issue with my approach, which I’d like to address before I move on, is that the birds-eye view type tracking, makes it hard to navigate environments with multiple floors. If you want the algorithm to do so, you should create a way to filter the raycasts, otherwise you will always end up on the top floor, as that is the first “Ground” object which the raycast collides with (I use Unity’s layer system to differentiate).

Code:

Before we go any further, make sure you downloaded the Unity package file and loaded it into a project. Here is the link again:

• Download Search Behavior Unity package

If you want to mess around with it, make sure you can see both the Game and Scene view – as the red lines only render in the Scene view, but the game only listens for button-presses on the spacebar when the Game view is active. The beforementioned parameters can be found by selecting the “Animal” object in the scene editor, and looking for the Animal Script component in the Inspector.

The code consists of two separate classes and an extension of an existing type:

1 – SearchScript:

Houses all of the calculations – everything from the incremental sine/cosine curves to the pathfinding verification and raycasting.

2 – IListExtensions:

Extends the functionality of the IList datatype. Used to implement the Fisher-Yates shuffle algorithm for randomly sorting a list with equal distribution.

3 – AnimalScript:

A prototype class which only exists to instantiate the tracker object housing the SearchScript class, then receive and draw the results. It has been created separately because the AI agents in the final build will run separately from the SearchScript class as well.

NB: Some functions have been omitted from this documentation, as they only serve to illustrate the more basic principles of sine/cosine wave addition. The difference between these test functions and the ones used, is that the test functions use DeltaTime to increment the waveforms, and are thusly executed in the Update function over time, instead of computing the path all at once.

1. SearchScript:

The powerhouse of the prototype, this class is where all of the calculations and path verification happens. The purpose of the SearchScript class is simply to find a number of points in the environment, which the AI agent can reach from its current position, then return a list of these points in a random order.

1.0 Fields:

The fields contained in this class are not actually initialized within it, but do instead receive their values from the AI agent (the AnimalScript class in this prototype). Some of the fields were already elaborated on in the introduction, but for the sake of completion, they will all be documented equally here:

public float searchHeight

Dictates the height of the tracker, relative to the AI agent. The range of the raycast is equal to this height multiplied by 2.

public float searchSpeed

A multiplier added at the end of the sine- and cosine-wave calculations. This increases the distance between points without affecting the base calculation. Increasing this value will make the points move further away from the AI agent at a higher rate.

public float intervalIncrease

The value by which the base sine- and cosine-wave calculations increase. This is the base value and will affect the angle of the spiral.

float intervalCounter

The total base value used in the sine- and cosine-wave calculations. This is the variable which increments by the value of intervalIncrease.

public float searchDuration

The number of points which the search algorithm will attempt to generate.

float randomOffset

A random float between -3 and 3. This is used to offset the initial angle of the spiral, to prevent noticeable bias (eg. the AI agents always moving in certain ways that are noticeable to the player).

public GameObject agent

A reference to the AI agent which instantiated the tracker object. This reference is established by the agent itself and should always be considered initialized when working within the SearchScript class.

IList<Vector3> path

A list of the valid coordinates found by the algorithm

NavmeshPath testPath

The path which is used to verify the physical connectivity between the previous valid point and the one currently being evaluated.

1.1 void Awake():

The Awake function contains a few initialization statements necessary to prevent null reference errors later in the program. This includes finding the value of randomOffset and initializing the testPath variable (as memory needs to be reserved for it, or it can’t be used for pathfinding).

1.2 void CalculateSearch(float _x, float _z)

This function calls several other functions to determine if the location at the given _x,_z coordinates is navigable. If it is, this function adds the point to the path list. Additionally, a check is made to see if it is the first point added, to ensure that the position of the agent itself does not become listed.

1.3 bool VerifyPath(Vector3 _vectorStart, Vector3 _vectorEnd)

This function makes use of Unity’s pathfinding algorithm in order to verify whether the two Vector3 coordinates are navigable in the navmesh. The function will return true if that is the case, and false if the path can’t be computed – even partially.

1.4 float GetTerrainHeight(Vector3 _fromLocation, float _fromHeight)

This function returns the Y-coordinate of the terrain at the given Vector3 coordinate _fromLocation, by raycasting down at the height of _fromHeight. The raycast is configured to only detect collisions with objects on the “Ground” layer, ignoring all other objects. The distance of the raycast is equal to double the searchHeight variable.

1.5 void ExecuteLogicOnce()

This function houses the path shaping algorithm, which is where the sine- and cosine-waveforms are used to draw an outward spiral pattern from the AI agent’s location. With each coordinate generated by this algorithm, a call to the CalculateSearch function is made, which then verifies and adds the point if it is navigable from the previous point.

1.6 public IList<Vector3> ReturnPath()

This function is called by the AI agent, which in turn runs the ExecuteLogicOnce function. The path is then shuffled with the Fisher-Yates shuffle algorithm before being returned to the AI agent.

2. IListExtensions

Extends the functionality of the IList datatype. This was deemed necessary because of the lack of randomization options in the original IList and List datatypes

2.1 public static void Shuffle<T>(this IList<T> ts)

This member function extends the functionality of the IList class, to implement the Fisher-Yates shuffling algorithm. The reason this algorithm was chosen is due to its unbiased distribution in picking random elements on the list.

3. AnimalScript

A placeholder for the actual AI agent script. It spawns the tracker, collects the information the tracker generates and then visualizes the result in the scene editor.

3.0 Fields

These fields mirror those found in the SearchScript class, as they are simply passed on to the tracker upon initialization. The reason they are found here is because it makes more sense to define the AI agent’s pathing parameters, directly on the AI agent instead of in the tracker prefab.

The two things worthy of note are the path and trackerReference variables:

IList<Vector3> path

The IList which receives the result generated by the SearchScript:

SearchScript trackerReference

A reference to the SearchScript attached to the tracker. This is necessary for passing the search parameters to it.

3.1 Update()

The Update function listens for a keypress on the spacebar, as the cue for initializing the tracker object. This is purely done for testing reasons and will be replaced by an automated call in the final version. Additionally, a check is made to see if there are any coordinates in the current path variable of the AI agent, in which case a debug statement will render this path in the scene editor.

3.2 SpawnTracker()

This function initializes the tracker object prefab from the Resources folder of the Unity project. This prefab is an empty gameobject with the SearchScript script attached to it. When the tracker object has been initialized, a reference to its instance of the SearchScript is made, followed by the initialization of its search parameter variables. The tracker is then moved to ensure that it is right on top of the AI agent, before its ReturnPath function is called. Finally the tracker object is destroyed once it has performed its function.