Tutorial 3: Unity A-Star Path Finding Iterative Intelligence
-
Author: Brian A. Ree
Files/Resources for this Tutorial
Unity Project (2017.3.0f3)
Unity AI Game Programming - Second Edition1: Introduction and Tutorial Goals
Hello and welcome to our fourth little Unity tutorial. This tutorial requires that you have that latest Unity software installed, at the time of this writing the current version is 2017.3.0f3. If you're new to Unity or you've been away for a while you might want to brush up your skills a little bit. Below are some links to get you up to speed.
- https://docs.unity3d.com/Manual/GettingStarted.html
- https://docs.unity3d.com/Manual/LearningtheInterface.html
- https://www.youtube.com/watch?v=pTLCMZ_qvTw
I recommend purchasing and reading Unity AI Game Programming - Second Edition, don't overlook this book, it's a great crash course into Unity AI and after having read it twice I think it's a solid title for those getting into the scripting side of Unity, specifically game AI. Most games require AI on some level and this book will get you started quickly. This toturial is based on the AStar chapter of this book but adjusted to run in an iterative way. In the previous tutorial we calculated a full path, start to goal, every update call. That's a lot of work to do, especially if you have a lot of enemies trying to calculate different paths. In this tutorial we'll handle slowing things down and making calculations in an iterative way, a little bit at a time. We'll also look at some scripting code, and move Kyle around when we've found the goal.
2: Getting Setup, Dive In
Ok so let's get the project we're working with and start learning. Before we get started let's run a little experiment on our AStar path finding code. Run the scene and make sure you can see the Scene window, the Game window just shows Robot Kyle for now, we'll animate him along our determined path in a future tutorial but for now let's look at the path. Make sure the iterative check box is unchecked in our 'AStarTestCodeStatic' GameObject and script. Select the 'End' GameObject from the Hierarchy window while the scene is running and move it somewhere else in within the Ground plane, notice the path updates automatically, that's because we have it set to recalculate every frame of the game. That's a lot of work to run each time interval. See the screen shots below.
Make sure the iterative check box is un-checked.
Move the 'End' GameObject while the scene is running and watch the path recalculate.
3: Iterative Test Drive
Now we'll check out the iterative method, this will actually show us what's happening in the brain of the AI algorithm. Find the 'AStarTestCodeStatic' GameObject and check the 'Find Path in Steps' option on the similarly named script. Set the 'Interval Time' to 0.25, 1 second is just too slow, now run the scene and make sure to look at your Scene window from the top down, no perspective view. Notice that jumpy green line? That's our little AI brain trying to find a path to the goal. Do you notice anything about how it behaves when there is an open space? It seems to try out a ton of different ways to cross that space although it hasn't necessarily found any obstacles that would make it change direction. Now stop the scene and set the 'Interval Time' to a few milliseconds. Let's try to slow it down and set our 'Interval Time' to 0.01, that's 1000 * 0.01 or 10 ms for each iteration of the path finding calculation. The important thing here is that each iteration of the path finding loop now runs every 10ms, instead of the entire loop in 10ms, so we've slowed things down greatly.
Notice that Kyle jumps to the position of the start cube, and the start cube disappears once we've found the goal. We've setup an event that fires when the goal is found and in response to that event we adjust Kyle's position to that of the start cube and deactivate it. I've provided some links below about C# Events, and the code that we use to handle the goal found event. Double click the 'AStarTestCodeStatic' file so that is opens in MonoDevelop. See if you can locate the 'GoalHasBeenFound' method.
- https://www.intertech.com/Blog/c-sharp-tutorial-understanding-c-events/
- https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/events/
private void GoalHasBeenFound(object sender, EventArgs e) { Utils.wr ("Found Target"); if (this.robotKyle != null) { Utils.wr ("Let's start Robot Kyle, place him at the start."); this.objStartCube.SetActive (false); this.robotKyle.transform.position = this.objStartCube.transform.position; } }
Handling the 'OnGoalFound' event, and making Kyle jump.
One more thing before we end this tutorial. I want to show you the 'Update' method call, where the iterative magic takes place. Double click the 'AStarTestCodeStatic' file so that is opens in MonoDevelop. See if you can locate the 'Update' method. The 'Update' method is part of the underlying Untiy code structure, specifically the MonoBehaviour class, but we won't go into that here. Notice in the code below how we branch into different method calls depending on whether or not the timing interval has triggered, that is the elapsed time is greater than our target interval time. This is one way of slowing things down, the other thing we're doing is based on the state of the 'FindPathInStep' method, which returns true or false. We either run the entire calculation or just one iteration of it. So take what you will from this tutorial it should have given you some idea about timing and how algorithms work, moving objects around, and finding a path.
void Update() { this.elapsedTime += Time.deltaTime; if (elapsedTime >= this.intervalTime) { this.elapsedTime = 0.0f; if (!this.FindPathInSteps ()) { this.FindPath (); } else { if(AStarAgentStatic.HasFoundGoal()) { this.FindPathInStepsPrep (); }else { this.FindPathInStepsIterate (); } } } }
The details of our 'Update' method.