Category: AI

Updating A* to Move Units in 3D for Elevations (Cont.)

digm520admin / / A*, AI, ArchitectureAIProject, Pathfinding, Programming
March 12, 2020

Updating A*

Adding 3D Movement (Elevations)

A* Current System and Notes

Now the A* system can deal with moving units along the y-axis according to the terrain, but it is still off with the advanced path smoothing functionality since this only cares about points where the unit is turning according to the xz-plane. To keep the system more simplified for now, I am looking to roll back some of the more advanced functionality from the Sebastian Lague tutorial I followed to incorporate the y-axis movement into a more simplified pathing system.

I want to ignore the SimplifyPath method for now (which narrows down the full list of nodes for a path down to only those which turn the agent, and only uses these as waypoints), which also causes problems if I have path smoothing as well. This is another reason to remove path smoothing temporarily.

A* Update

I wanted to keep the advanced path smoothing options available in the project, while looking to use the simplified version for now (with updates to continue having the y-axis movement). To do this, I identified which scripts dealt with path smoothing specifically which led me to the chain of these scripts:

  • PathFindingHeap
  • Unit
  • PathRequestManager

Since those were the scripts that dealt with applying path smoothing, I looked for versions of the project I saved as stepping stones of the tutorial that were before path smoothing (around episode 8 of the tutorials). From these projects, I grabbed their respective versions of these scripts to copy into this working project. To keep them as unique but separate options, I appended “Simple” to these versions of the scripts.

With these scripts, I could build out a scene (named SimpleTest) for the purposes of testing the y-axis movement with this simpler movement logic. While it is less aesthetically pleasing, it is in a way more accurate and representative of the core information the system is working with, so I wanted to get back to this state to have a better idea of what I was working with. This new scene has PathFindingHeapSimple and PathRequestManagerSimple on its A* gameobject, and each of the Seekers use the UnitSimple script instead.

With all of these in place to effectively remove path smoothing for now, I could effectively remove the SimplifyPath method from PathFindingHeap (and PathFindingHeapSimple as well for this case). This ensures the agents will travel to each individual position designated by every node along its path. This helps me see exactly every point of data that the agents are working with when moving. This is helpful to make sure the agents are properly receiving the right elevation data throughout the entirety of their paths.

With all of this done, I got the desired results I expected. The units immediately fly down into their starting position and move along the terrain properly, regardless of elevation. They effectively move up and down inclined surfaces, and can properly navigate up and down bumps and ramps in the terrain. They also show every single node point as a gizmo they are using as a path for movement, which clearly shows their paths following the terrain. I have included a video link for a quick demonstration of the agents in motion.

Vimeo – A* Movement in 3D Edit

AI Agents Moving in 3D with Path Highlighted

Next Steps

This simplified system appears to work exactly how I need it to, and I think this may be the preferred approach moving forward for now since it will be used to represent and show theoretical data. This may make it more practical to show the exact pathing information given as opposed to the skewed pathing created by the path smoothing operations.

The next step will be looking into creating objects which can influence the cost of a number nodes around them (as opposed to just those they are directly on, which is somewhat covered in the behavior of obstacles). This way different objects can influence the likelihood of an agent moving towards/around them.

I am looking at starting with a simple area of effect approach where the grid detects the object on a certain node and then alters the cost of all the nodes around it to some degree (the simpler approach, and mimics the blur effect already present from the tutorial followed). This blur effect makes it so the cost additions of the grass and road are blurred some around where they meet. The future advancement of this topic would be to allow objects to influence the cost of nodes based on line of sight, which is a much more variable amount of nodes to influence, making it a bit more difficult to implement.

Updating A* to Move Units in 3D for Elevations

digm520admin / / A*, AI, Pathfinding, Programming
March 11, 2020

Updating A*

Adding 3D Movement (Elevations)

A* Current System

The current A* system I am using solely works on a 2D plane (on the x-axis and z-axis). It creates a grid on this 2D plane and then allows agents to move specifically along this 2D plane, with no regard for heights. It is currently casting rays from above these grid nodes to detect the layer of the terrain the node is on. Each node also casts a small sphere the same size as it to detect collision for obstacles to determine if a node is traversable or not.

A* Update

Since the system already uses raycasts to detect the terrain type, I edited this to detect the height information from the terrain as well. Using RaycastHit.point, the raycast can return information on the exact point it hits, so I can pass the y-axis information from here to the node. I just do this along with the terrain detection, and pass this to the world position data of the node.

Since this update is specifically targeted at working with various elevations, I do not like using the collision spheres on the nodes to detect obstacles. Since I already have raycast incorporated, I thought it made sense to have it detect obstacles as well. Because there are layers involved for obstacles and terrain, I have the raycast check first if it can detect an obstacle (unwalkable terrain), and then if it does not find one, then check for walkable terrain and what type it is.

Finally, just to clean up, I added an extra variable to account for the unit heights when assigning elevation positions. This can be changed in the editor, but it adds a bit of elevation to the exact value from the terrain so the unit’s positioning as it moves along is a bit above the ground (so it is not in or below the ground).

Next Steps

These changes worked pretty well to get close to the desired effects. The units will move along altered elevation terrains to some degree. The current testing was done with a further simplified waypoint system after grabbing all of the nodes, so only the position data of points where the unit needs to turn is really taken into account for movement. This results in weird issues since the unit will not move up and down to account for elevation if it is moving in a straight line according to the xz-plane. It only accounts for elevation if the specific waypoints end up on varied elevation points (this is why it looks pretty proper on just a slanted plane).

I will look into reverting the simplified system to see if the standard system going to every single node works first. After I get that working again in all 3 dimensions, I will look to adjust back to the simplified waypoints system.

UnityLearn – AI for Beginners – The Mathematics of AI – Pt. 01 – Cartesian Coordinates

digm520admin / / AI, Programming, Tutorial, TutorialList, Unity, UnityLearn
March 6, 2020

AI for Beginners

The Mathematics of AI

Cartesian Coordinates


Artificial Intelligence for Beginners

Unity Learn Course – AI for Beginners

Cartesian Coordinates

Cartesian Plane

Cartesian coordinates:
used to determine locations in space for any number of dimensions
generally used for 2D and 3D space in games (x, y) and (x, y, z)

2 Main Projection Types: Orthographic and Perspective

Orthographic:
3D space represented by a cube or rectangular prism

Perspective:
3D space that looks like a rectangular pyramid with its top cut off

The Camera size in Unity when using the Orthographic perspective dictates how far the camera sees for the smaller dimension of the aspect ratio. It is the number of units in both the positive and negative direction away from the origin the camera sees, so the smaller dimension of the aspect ratio is double that of the Size value given to the camera. The larger dimension in the aspect ratio is then the ratio multiplied by that Size value.

For example, if the orthographic perspective Camera Size is 100, and you select the aspect ratio of 16:10 for your view, the overall height seen is 200 units (+100 to -100 on the y-axis) and the overall width seen is 320 units (+160 to -160 on the x-axis). The size directly correlates with the y-axis since it is the smaller of the dimensions in the aspect ratio, and then the range for x is determined by multiplying that size (100) with the aspect ratio (16:10 or 16/10).

The viewing volume for this orthographic view is a rectangular prism (completely straight on viewing angle). They expound upon this to show movement on the z-axis does not particularly do anything in a 2D game built around the x-axis and y-axis. Placement can matter however as objects do need to be in front of the camera, and objects can be placed in front of or behind other objects.

SUMMARY

  • Unity Camera Size and Aspect Ratio together exactly determine the number of units for the dimensions of place shown on the camera at a time (especially for Orthographic perspective).
  • Orthographic view uses a rectangular prism viewing space, where a Perspective viewing space uses a rectangular pyramid shape.
  • Cartesian planes and coordinates can be used for any number of dimensions (not restricted to just 2D and 3D)

What Are Neural Networks? – Basics Videos

digm520admin / / AI, MachineLearning, NeuralNetworks, Programming, TutorialList
February 17, 2020

Neural Networks

Youtube Videos on the Basics

But what is a Neural Network? | Deep learning, chapter 1

Information #1 – Link

By: 3Blue1Brown


Neural Network Architectures

Information #2 – Link

By: Steve Brunton


Notes

I am following up on my original research into working with neural networks and machine learning. I started looking into the programming more before really looking into the full background of it, so I am going back to make sure I have a better understanding of the theory and concepts behind neural networks and machine learning. These sources I found seemed to be useful lectures to get a hold of the basic foundations for the concepts behind such ideas.

Unity Learn Tutorials – Artificial Intelligence for Beginners and Intro to Optimization

digm520admin / / AI, Programming, Tutorial, TutorialList, Unity, UnityLearn
February 7, 2020

Unity Learn Tutorials

Note: The AI tutorial require Unity Learn Premium to access
Artificial Intelligence for Beginners

Tutorial Series #1 – Link

By: Penny de Byl


Introduction to Optimization with Unity – 2019.3

Tutorial Series #2 – Link

By: Unity Technologies


Notes

These were both tutorial series I saw on Unity Learn that I wanted to note specifically to check out later. The Optimization tutorial is a very small series, so I can look into that rather quickly, but the AI series is a 15+ hour comprehensive class so that will take a large commitment to fully cover.

The AI series however is something I am interested in in general and even covers some topics I am specifically looking into at this time. Some of these topics include: Navigation Meshes, Crowd Simulation, State Machines, and Goal Driven Behavior. This would be very good to follow for my own personal interests as well as possibly being useful for some projects I am looking to work on.

Exploring NavMesh Capabilities

digm520admin / / AI, NavMesh, Programming, Tutorial, TutorialList, Unity
February 5, 2020

NavMesh

Unity Tutorials

Unity NavMesh Tutorial – Basics

Tutorial #1 – Link

By: Brackeys


Navigation Mesh Basics | Unity AI Pathfinding (Part 1) | Table Flip Games

Tutorial #2 – Link

By: Table Flip Games


Use Unity3D NavMeshAgent.Move to customize your navigation control

Tutorial #3 – Link

By: Jason Weimann


Crowd Behaviours on a Dynamic Navmesh in Unity Part 1

Tutorial #4 – Link

By: Holistic3d


Notes

I am looking to explore Unity’s NavMesh to see what features it has to compare with A* Pathfinding, especially my setup I worked on specifically. I want to see the benefits it readily provides over A* as well as see if I can find any useful features that could be implemented in some way into A*.

Tutorials 2 and 4 both are the beginning of series so they can be useful for exploring deeper into NavMesh. Jason Weimann in tutorial 3 is also generally a good source for exploring features more deeply at a more advanced level.

A* Pathfinding: Debugging Special Cases

digm520admin / / A*, AI, Debug, Pathfinding, Programming
December 19, 2019

A* Pathfinding

Debugging Special Cases

ISSUES

Getting an Index Out of Bounds Error in EnemyBasicMovement Script

Error happening on this line:

Vector3 direction = (path.lookPoints[0] – transform.position).normalized;

Suggests that the very first point in a path does not exist, so somehow empty paths are being passed through the system.

Test 1: Increase A* Grid Size to Cover Entire Play Area and Spawn Points

Some of the spawn points are a bit off of the normal play area, so I made sure to cover anywhere the units could possibly exist with the A* grid so they always had a node to latch onto (even though I believe the clamping should cover this error). This did not end up being the issue as the error persisted.

Test 2: Increase Size of Walkable Plane Over Entire Play Area

Similar to the logic of Test 1, I just wanted to make sure the nodes were not not being created because the units were missing some usual piece of information they would have to make them. Turns out this was not the issue either.

Test 3: Make Sure Target is Set Before Instantiating the Enemy

I thought maybe a path was being created before the unit had a target, which could make sense for creating a path with size 0. I did this by having the pathing script disabled initially, and making sure the spawner passed in the target information BEFORE it activated the script. The error continued though.

Test 4: Do Not Move the Target to See if Error Exists

It seemed like most spawns didn’t get errors if the player did not move, so I moved the one spawn that basically did not have to move to reach the player’s x position and tested what happened without the player moving (The X position counted as “very close” to the player at this time since I still had some of the issues with converting between 3D and 2D coordinates). There were no errors at all when not moving the target during the game.

DETERMINED ISSUE

Something about the paths updating later in the units’ lives was creating these size 0 paths.

Test 5: Is Spawning Causing the Issue

I was not sure if spawning the units was somehow causing the problems still, so I just placed 4 of the unit prefabs randomly about into the scene initially and stopped the spawners. This did not get rid of the error, and had the units return to moving in big circles still.

Further Info

This was giving me a lot of trouble, so I went back to following the path of logic to see why it would be producing these 0 count paths.

  • OnPathFound method in EnemyBasicMovement is being passed an empty array of Vector3[] waypoints
  • PathRequestManager class calls this method through its own FinishedProcessingPath method
  • OnPathFound is the method assigned to the callback Action for the PathRequest object
  • PathFindingHeap is creating an empty waypoints array somehow

The zero count path is being created in PathFindingHeap somehow. This should be impossible as every path should at the very least have the start node and the target node, which would be a count of 2.

    Within PathFindingHeap

  • RetracePath takes in a startNode and endNode to create the entire path of nodes between them
  • In the problem case, a new path has been created when the target is only a single node away from the pathfinding unit’s current position
  • there is a while loop that runs until it hits the startNode, so in this case, it only runs a single time (since the only nodes are the startNode and the endNode), creating a single waypoint
  • this creates a path with a count of 1
  • then the SimplifyPath method takes in this path
  • SimplifyPath creates a new List of Vector3 to fill with only necessary waypoints
  • it does this by taking points from the passed in path, but it looks through this with a for loop which starts at i = 1 and ends at i < path.Count, because it needs a previous point to compare to since it is doing a directional check
  • since the path.Count is only 1 here, the for loop never runs, and we return an empty set of waypoints
  • Can possibly solve with a special case since a path of 1 node is also a most simplified case

Test 6: Add Case In Simplify Path to Deal with Receiving One Node

I just added a check case before the normal logic that if the input path for SimplifyPath was only 1 node, it would just use that node as the path. This reduces the number of errors significantly, but there are cases where even the base path passed into SimplifyPath has 0 nodes.

DETERMINED ISSUE

The PathFindingHeap RetracePath method is creating paths with 0 nodes when Unit is close to target. As a result, SimplifyPath also makes 0 count paths. The only way this can be the case is if the startNode == endNode, so this must be happening when a new path is being created even though the unit and its target are already considered to be on the same node. This leads me to believe it is an issue with the difference between the node size and the distance the target has to move before looking for a new path (pathUpdateMoveThreshold in EnemyBasicMovement).

Test 7: Reduce NodeRadius to Half (or Less) of Update Path Threshold

Originally the values for pathUpdateMoveThreshold and the nodeRadius were both 0.5, which lead to a overall node size (nodeDiamater) of 1.0. I reduced the nodeRadius to 0.25 (which gives them a total nodeDiameter of 0.5), so this was at or below the threshold.

SOLVED

This completely removed the errors from happening (I add mostly because I am unsure if there exists a case where having the nodeDiameter exactly equal the threshold could cause an error).

SUMMARY

There was a lot of going back and forth to figure out where this error was coming from, and it was even harder since I was having some other issues since I had not fully converted the 3D system to the 2D system. As far as I can tell, this should cover most of the strange cases the pathing should run into even with an updating target (which should mostly be extra for my purposes anyway). I should add a check between the node size and the update threshold to make sure that issue does not happen again.

A* Pathfinding: Edit for 2D

digm520admin / / A*, AI, Pathfinding, Programming, Unity
December 19, 2019

A* Pathfinding

2D Conversion

ISSUES

Pathing In Circles Away from Target

They move in a large circle around the entire game area. They go in a half circle consistenly then stop in about the same place everytime (either directly above or below the middle of the play area).

Test 1: Tone Values Down

I tried toning all their numbers down since my game area is relatively small in case they were just constantly over shooting node targets, but this did not change the behavior.

I think the direction I am aiming and moving them must be incorrect with how I changed the Vector math from 3D to 2D.

DETERMINED ISSUE

They can only respond to the player’s X position. If the player moves, the properly oriented ones will move slightly to keep at the same X value, whereas those facing the other direction will travel in a large circle to reach the same X value (since I guess they cannot rotate very easily).

Test 2: Edit Rotation Calculation

I just needed to remove an extra (-90) that was being applied to the rotation vectors for aiming them at the target. This completely fixed the issue for their initial movement, but they only move in the x direction after that initial reaching of the target now.

DETERMINED ISSUE

The target position is not changing its Y value for some reason, only its X value.

Next Steps

Either their rotation is messed up (so moving right only moves them along x axis) or the overall translation is messed up and is only moving them left and right. It could be another z/y conversion error somewhere.

Test 3: Change NodeFromWorldPoint Method to Use worldPosition.y instead of z

It looks like PathFindingHeap was using AGrid NodeFromWorldPoint function to determine the proper node from world points, but this was using the z value of the Vector3 input as to determine the y coordinate in the overall grid. This is why it was constantly hovering at the same low Y value, because those were the nodes that correlated with a z input of 0.

SOLVED

These combined edits fixed the pathfinding logic completely. They now constantly followed the target position properly and it updated accordingly.

How Command & Conquer: Tiberian Sun Solved Pathfinding: War Stories: Ars Technica

digm520admin / / AI, GameDesign, Informative, Pathfinding
December 18, 2019

War Stories

How Command & Conquer: Tiberian Sun Solved Pathfinding

How Command & Conquer: Tiberian Sun Solved Pathfinding | War Stories | Ars Technica

Link – Video

By: Ars Technica


Working on Pathfinding

Pathfinding, especially in a dynamic sense, is still a relatively expensive process to run. This is much more so when you are trying to apply it to a lot of units.

Tiberian Sun was running into a lot of issues they called “Artificial Idiocy”, which is when your AI just does really dumb stuff. Really illogical AI from a player’s game units very quickly make the player mad and aggitated. They say “If you spend more time making sure it doesn’t do something stupid, it will actually look pretty smart”. And to follow up, they didn’t need perfect pathfinding, they just needed “not stupid” pathfinding.

Some of their fixes included not accounting for the collision of other friendly units selected to move and wiggling stationary friendly units when encountered by moving friendly units. Not accounting for other selected friendly units made sense since most likely they would also be going to about the same place and would generally be out of each others’ ways. The wiggling was added as very simple to execute logic in hopes that it would “unlock” a path previously obstructed by the stationary units.

SUMMARY

This was just a cool video I stumbled upon pretty randomly. It was very interesting to see some of the “behind the scenes” for one of my first favorite computer games to play a long time ago. There are just so many things you take for granted that took a lot of hard work and were almost revolutionary for their time.

It is also interesting to see that some problems still exist to a degree, like the prcoessing intensity of dynamic pathfinding. I think my research in pathfinding recently is what brought this video recommendation to me on Youtube, so I have at least had a small taste of the pains they went through developing that. I also really like their thoughts on just minimizing the terrible choices of AI instead of maximizing its “smart” moments to make it nicer to work with and really look smarter in the end.

Sebastian Lague A* Tutorial Series – Threading – Pt. 10

digm520admin / / A*, AI, Pathfinding, Programming, Tutorial, TutorialList, Unity
December 16, 2019

A* Tutorial Series

A* Pathfinding (E10: threading)

A* Pathfinding (E10: threading)

Link – Tutorial

By: Sebastian Lague


Intro:

This tutorial gets into the idea of threading to help relieve some of the burden on processing caused by the pathfinding logic. Threading is not something I understand very well, so I will have to look into this more in the future, but I wanted to cover this tutorial just for completions sake.

Tutorial

This setup usese another namespace, the System.Threading namespace. This lets them use the ThreadStart delegate type and the lock keyword. ThreadStart can be assigned the value of some other delegate, with in this case contained the FindPath method from PathfindingHeap. I then looked up the lock keyword here:

https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/lock-statement

While this sort of threading setup has some unique syntax, it is an otherwise simple setup. There is a queue of PathResults that are just checked paths that are waiting to be called for the movement of units. The paths get created and checked to make sure they can hit the target, and once this is satisfied, it gets added to the queue.

Summary

I would need to have a better understanding of threading and how to utilize it to assess how useful this tutorial really was. I know the general idea behind it is to help distribute the processing load, but I do not know how well this new setup accomplishes that.