Posts

Showing posts with the label A*

Architecture AI Pathing Project: Upward Raycast for Better Opening Detection

Image
January 11, 2021 Raycast for A* Nodes Architecture AI Project Original Downward Raycast and Downfalls The raycasting system for detecting the environment to setup the base A* pathing nodes was originally using downward raycasts. These rays traveled until they hit the environment, and then set the position of the node as well as whether it is walkable or not. An extra sphere collision check around the point of contact was also conducted so as to check for obstacles right next to the node as well. This works for rather open environments, but this had a major downside for our particular needs as it failed to detect openings with in walls and primarily doors. Doors are almost always found within a wall, so the raycast system would hit the wall above the door and read as unwalkable. This would leave most doors as unwalkable areas because of the walls above and around them. Upward Raycast System Approach Method The idea of using an upward raycast was that it would help al...

Architecture AI Pathing Project: File Reader and Different Resolutions of Data and A* Pathing Grid

December 1, 2020 File Reader Architecture AI Project File Reader Data Array Creation The file reader for this projects starts with the CSVReader class. This class is responsible for reading data in from .csv files generated by Revit to pass it on to the underlying A* pathing node grid for use by the agents when pathing. These .csv files have 2D coordinate values to locate the data, the actual data value, and a reference ID. The coordinate data and the data values themselves are separated and saved into many data objects within Unity (in a class named DataWithPosition). This prepares the data to be used to pass on to the A* pathing node grid. While the .csv data is generally consistently spaced based on coordinates, it can have many gaps as it does not assign a value somewhere where there is a gap in the model. This results in data that is not perfectly rectangular. To make the process of tying this data array in with the pathing grid more consistent, I manually make a recta...

Architecture AI Prototype Historical Path Visualization and UI Updates

Image
July 1, 2020 Architecture AI Project Added Path Visualization and UI Updates Introduction To top off the prototype, we added a quick visualization tool to show any paths that agents have taken within the current game session. This was necessary to make it easier to compare the paths of various combinations of agents and environments even. Along with this, some elements of modifying the system that were only accessible within the Unity Inspector have been moved to the in game UI. This makes it much more manageable to alter the agents and their pathing for Unity users and non-users alike. The following quick reference image shows an example of this new path visualization tool (the red line going through the diagonal of the area). Reference for New Path Visualization Tool (the Red Line is the Path) Vimeo - My Demo of the Past Path Visualization Tool (with New UI Elements) Past Path Visualization Feature Visualization The path data was already being recorded in an ...

Architecture AI Completed Prototype with Data Visualization and Pathing Options

June 24, 2020 Architecture AI Project Completed Project Prototype Introduction We were exploring different methods for importing architectural models into Unity and decided to try Revit to see what it had to offer. The models are easy to move between softwares, and it also creates .cs scripts that Unity can use to provide some interactive data visualization when using the Revit models. Data Visualization Options I moved everything dealing with the major logic of the A* grid node visualization into its own class named AStarGridVisualization. This allowed me to continue to hold on to all the different debug visualization methods I created over the course of the project and convert them into a list of options for the designer to use for visualization purposes. As can be seen in the demo, there is a list of options in the drop down list in the Unity Inspector so the designer can tell the system which data to visualize from the nodes. The options currently available are: Wa...

Architecture AI Varied Agent Affinities with Varied Pathing

May 28, 2020 Architecture AI Project Varied Agent Affinities with Varied Pathing Demonstration of Varied Agent Affinities with Varied Pathing Vimeo Link - My Demo of Agents Pathing with Varied Affinities Explaining Simple but Unclear Heatmap Coloring System Just to help explain since I don't have great UI in to explain everything currently, the first thing was that I was testing a really rough "heat map" visual for the architectural values for now. When you turn on the option to show the node gizmos now, instead of uniform black cubes showing all the nodes, the cubes are colored according to the architectural value of the node (for this test case, the window value) Unfortunately this color system isn't great, especially without a legend, but you can at least see it's working (I just need to pick a better color gradient). Red is unfortunately both values at/near 0 (min) as well as at/near 100 (max) (but the value range here is only from 0 - 80, so all r...

Architecture AI Heatmap of Architectural Costs

Image
May 27, 2020 Architecture AI Project Visualizing Heatmap of Architectural Costs Architectural Cost Heatmap I was just using basic black cubes to visualize the grid of nodes in the AGrid A* system originally. Now I finally decided to update that system with a bit more information by adding a colored heatmap to map out the architectural values of the nodes. This will help me understand the pathing of my agents better as they start to use these values in more complex and interesting ways. Basic Heatmap Color System It turns out making a heatmap color scale that decently ranges between values of 0.0 and 1.0 is pretty easy. Using HSV color values, you can just vary the H (hue) value while keeping the other two values constant at 1.0 to cover a heatmap spectrum (where H of 0.0 is the lowest value in the range, 1.0 is the highest value in the range, and all other colors are bound within that range). By simply using the min and max architectural values possible in the system as the...

AGrid Inspector Breakdown for A* Pathfinding

Image
May 5, 2020 A* Pathfinding AGrid Inspector Breakdown Display Grid Gizmos: determines whether or not to run gizmo methods (methods used for debugging and visualization in the editor, like the node locations) Unwalkable Mask: this is the Unity layer that is deemed unwalkable to the system (the layer which are picked up by the nodes during raycasting) Grid World Size: a Vector2 which determines the real world size area to attempt to place nodes on (rectangular shaped with alterable width and height) Node Radius: half the real world size of each individual node, which correlates to half the distance between each node's center (in both the x and z direction) Walkable Regions: this section can be opened and various terrain types can be added to this as well as their associated movement cost penalties to make certain terrains more or less navigable (also picked up in the raycast of the nodes) Obstacle Proximity Penalty: adds a bit of ext...

AGrid System Breakdown for A* Pathfinding

May 5, 2020 A* Pathfinding AGrid System Breakdown AGrid class: - this class sets up the initial node grid 1) Determining grid size and resolution - Input: nodeRadius - parameter to create a nodeDiameter (which is the "real world" size of the nodes) - Input: GridWorldSize - determines an x and y distance for the grid to cover (in real world units) - broken into GridWorldSizeX and GridWorldSizeY - Output: number of nodes (node resolution) - System uses these GridWorldSize values and the nodeDiameter to determine how many nodes it needs to create to fill this area - i.e. Inputs: GridWorldSize x = 10; GridWorldSize y = 10; nodeRadius = 1 - Output: Creates grid that is 5 nodes (2 diameter size) by 5 nodes (2 diameter size) - Note: diameter size is a bit misleading since they aren't circle shaped by any means; most dimensions are used in a more rectangular fashion (so diameter is more like edge length) 2) Positioning Nodes in Real World Space - The transfo...

Architecture AI Cost Calculation Class for AStar

April 27, 2020 Architecture AI Project Building Architecture Value to A* Cost Class Math for Calculating A* Cost with Architecture Value and Agent Affinity Integration I needed to translate agent affinities for architectural elements and their interaction with the architectural values themselves found in the nodes throughout the A* grid into cost values to integrate them with A*'s pathfinding logic. With this I wanted to create a class that is constantly available to contain all the math and constraints for dealing with this cost translation. Class MathArchCost The class MathArchCost was created to fulfill this purpose. It is a public class with a public static instance to make it readily available for other classes to acces it to perform calculations or check for minimum and maximum values. I decided to go this route instead of a directly public static class overall because I wanted to make an instance of this object that I could edit in the inspector during building tim...

Updating A* to Incorporate Various Architectural Elements Influencing Pathfinding

March 21, 2020 Updating A* Different Agent Types and Different Architectural Elements Adding Architectural Elements of Influence to A* Pathfinding We want to be able to add various architectural elements to an environment and use them to influence the pathing of AI agents using A* pathfinding. Along with this, we want various agents to respond differently to the same architectural stimulus (i.e. some agents should like moving near windows more, while others should prefer to stay away from windows). This required the addition of some architectural data to both the agents and the nodes within the A* grid. Implementing Architectural Elements I have started to implement my approach outlined in my blog post from yesterday to create the foundation for this architectural pathing addition. I have started with just a single data point to work out the feature by adding a "window" value to both the agents and the nodes of the grid. The Agent window measures their affinity for...

Updating A* for Multiple Agent Types of Pathfinding

March 20, 2020 Updating A* Different Pathfinding Logic for Different Agent Types A* Current System The A* Pathfinding currently performs the same calculations for every agent in order to determine its path. Every unit then takes the same path assuming they have the same starting and target positions. We are looking to adjust this so there are various types of agents which with different affinities to certain objects in the environment. This then needs to be incorporated in the path determination so different types of agents will takes different paths, even when using the same starting position and same target position. Differentiating Pathfinding for Different Types of Agents We want to add more parameters to the grid nodes besides flat cost that influence the agents' paths. These parameters also need to be able to influence different agents' paths differently (i.e. the parameters may give a node a cost of 10 for one agent, but 20 for another). Approach The init...

UnityLearn - AI For Beginners - Navigation Meshes - Pt.02 - Navigation Meshes

March 30, 2020 AI For Beginners Navigation Meshes Navigation Meshes Beginner Programming: Unity Game Dev Courses Unity Learn Course - AI For Beginners Navigation Mesh Introduction Nav Mesh: Unity function for making a navigable area for agents to traverse over. There are 4 main tabs in the Navigation window: Agents Area Bake Object Agents Core Parameters: Radius, Height, Step Height, Max Slope These dimensions determine where the agent can fit when navigating around obstacles, as well as how it can traverse elevation differences. Radius and height help limit where a character can go (cannot go between very small gaps or under objects very close to the ground) where step height is the elevation difference it can traverse in a single jump and max slope is how inclined the surface can be for the agent to travel on. The name allows you to save several types of agents, with various values for these 4 core parameters. Area How you define different costs for diffe...

A* Architecture Project - Spawning Agents and Area of Influence Objects

Image
March 25, 2020 Updating A* Spawn and Area of Influence Objects Spawning Agents Goal: Ability to spawn agents in that would be able to use the A* grid for pathing. Should have options to spawn in different locations and all use grid properly. This was rather straight forward to implement, but I did run into a completely unrelated issue. I created an AgentSpawnManager class which simply holds a prefab reference for the agents to spawn, a transform for the target to pass on to the agents, and an array of possibl spawn points (for incorporating the option of several spawn locations). This class creates new gameObjects based on the prefab reference, and then sets their target to that determined by the spawner. This was something worth tracking since sometimes there can be issues with Awake and Start methods when setting values after instantiation. This was all simple enough, but the agents were spawning without moving at all. It turns out the issue was that the spawn location was a...

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

Image
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 ver...

Updating A* to Move Units in 3D for Elevations

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 work...

A* Pathfinding: Debugging Special Cases

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 m...

A* Pathfinding: Edit for 2D

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 remo...

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

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 ...

Coroutine Error Investigation in A* Tutorial Series - Path Smoothing - E09

December 13, 2019 A* Tutorial Series A* Pathfinding (E09: path smoothing 2/2) A* Pathfinding (E09: path smoothing 2/2) Link - Tutorial By: Sebastian Lague Intro I wanted to further my investigation on the issue I had with coroutines when dealing with updating the pathing of the A* units when following the A* tutorial series, specifically in episode 9. I have included the sections "Error with Updating Path" and "Fix for: Error with Updating Path" from my last post to keep them together, along with my updates for the investigation. Error with Updating Path For some reason my version was not working properly. The path was updating fine, as I could see with the visualization, but the unit would stop moving and never move toward the target again. I was getting an index out of bounds error, some I have some issue with one of my arrays somewhere, but not sure where. It was running fine in the tutorial, so I must have missed something. Fix for: Er...