Hey Unity Developers! 🎮✨
**A* Algorithm in Unity: Unlocking Intelligent Pathfinding**
The A* (A-star) algorithm is a versatile and widely-used pathfinding algorithm in the realm of game development, and Unity provides a robust platform to implement it seamlessly. Here’s a closer look at what A* does and why it’s a game-changer:
1. Efficient Pathfinding:- A* is designed to find the most optimal path from a starting point to a destination on a grid-based environment. In Unity games, this is crucial for characters to navigate through complex terrains while avoiding obstacles.
2. Intelligent Decision-Making:- Unlike simpler algorithms, A* considers both the cost of reaching a particular point and an estimate of the remaining cost to the destination. This dual-cost evaluation makes it highly intelligent in decision-making, ensuring the shortest and most efficient route is chosen.
3. Adaptability to Dynamic Environments:- Unity’s implementation of A* allows developers to adapt pathfinding to dynamic and changing environments. Whether it’s a character moving through a constantly shifting level or avoiding dynamically spawned obstacles, A* can handle the complexity.
4. Customization with Heuristics:- A* introduces the concept of heuristics, enabling developers to customize the algorithm’s behavior based on specific game requirements. This adaptability makes it suitable for a wide range of game genres and scenarios.
5. Seamless Integration with Unity Components:- Unity provides a robust framework for implementing A* pathfinding, making it user-friendly for developers. Components like colliders, raycasting, and mesh manipulation can be seamlessly integrated into the algorithm, enhancing its capabilities.
6. Optimizing Gameplay Performance:- By efficiently finding the shortest paths, A* contributes to optimizing gameplay performance. This is crucial for real-time applications like games, ensuring a smooth and immersive player experience.
7.Visual Representation with Unity Components:- Unity’s visual capabilities make it easy to represent A* paths in the game world. Developers can use tools like LineRenderer or custom meshes to visualize the calculated paths, aiding in debugging and enhancing the overall gaming experience.
Get Jaiswalkishan’s stories in your inbox
Join Medium for free to get updates from this writer.
In this Demo I have created some scripts to pathfinding :-
Path Class — A serializable class representing a path in a hexagonal grid. It contains an array of `Tile` objects representing the tiles in the path.
[System.Serializable]
public class Path
{
public Tile[] tiles;
}Tile Script — Manages hexagonal grid tile properties, including pathfinding costs, highlighting, and modification. Features include terrain cost color-coding and text display.
using UnityEngine;
using TMPro;
using System.Collections.Generic;
public class Tile : MonoBehaviour
{
#region member fields
public Tile parent;
public Tile connectedTile;
public Character occupyingCharacter;
public float costFromOrigin = 0;
public float costToDestination = 0;
public int terrainCost = 0;
public float TotalCost { get { return costFromOrigin + costToDestination + terrainCost; } }
public bool Occupied { get; set; } = false;
[SerializeField]
TMP_Text costText;
#endregion
Dictionary<int, Color> costMap = new Dictionary<int, Color>()
{
{0, new Color(0.42f, 0.38f, 0.38f) }, //Gray
{1, new Color(0.45f, 0.23f, 0.15f) },//Red
{2, new Color(0.3f, 0.1f, 0f) } //Dark red
};
/// <summary>
/// Changes color of the tile by activating child-objects of different colors
/// </summary>
/// <param name="col"></param>
public void Highlight()
{
SetColor(Color.white);
}
public void ClearHighlight()
{
SetColor(costMap[terrainCost]);
}
/// <summary>
/// This is called when right clicking a tile to increase its cost
/// </summary>
/// <param name="value"></param>
public void ModifyCost()
{
terrainCost++;
if (terrainCost > costMap.Count-1)
terrainCost = 0;
if (costMap.TryGetValue(terrainCost, out Color col))
{
SetColor(col);
}
else
{
Debug.Log("Invalid terraincost or mapping" + terrainCost);
}
}
private void SetColor(Color color)
{
GetComponent<MeshRenderer>().material.color = color;
}
public void DebugCostText()
{
costText.text = TotalCost.ToString("F1");
}
public void ClearText()
{
costText.text = "";
}
}PathIllustrator Script — This script, coupled with a LineRenderer component, visually represents paths in a Unity hexagonal grid. It sets the LineRenderer’s positions based on a given Path, creating a path visualization with a constant height offset.
using UnityEngine;
[RequireComponent(typeof(LineRenderer))]
public class PathIllustrator : MonoBehaviour
{
private const float LineHeightOffset = 0.33f;
LineRenderer line;
private void Start()
{
line = GetComponent<LineRenderer>();
}
public void IllustratePath(Path path)
{
line.positionCount = path.tiles.Length;
for (int i = 0; i < path.tiles.Length; i++)
{
Transform tileTransform = path.tiles[i].transform;
line.SetPosition(i, tileTransform.position.With(y: tileTransform.position.y + LineHeightOffset));
}
}
}PathFinder Script — This script is responsible for finding a path between two tiles in a grid-based environment. Below is a breakdown of the key functionalities and components
using System;
using System.Collections.Generic;
using UnityEngine;
[RequireComponent(typeof(PathIllustrator))]
public class Pathfinder : MonoBehaviour
{
#region member fields
PathIllustrator illustrator;
[SerializeField]
LayerMask tileMask;
#endregion
private void Start()
{
if (illustrator == null)
illustrator = GetComponent<PathIllustrator>();
}
/// <summary>
/// Main pathfinding function, marks tiles as being in frontier, while keeping a copy of the frontier
/// in "currentFrontier" for later clearing
/// </summary>
/// <param name="character"></param>
public Path FindPath(Tile origin, Tile destination)
{
List<Tile> openSet = new List<Tile>();
List<Tile> closedSet = new List<Tile>();
openSet.Add(origin);
origin.costFromOrigin = 0;
float tileDistance = origin.GetComponent<MeshFilter>().sharedMesh.bounds.extents.z * 2;
while (openSet.Count > 0)
{
openSet.Sort((x, y) => x.TotalCost.CompareTo(y.TotalCost));
Tile currentTile = openSet[0];
openSet.Remove(currentTile);
closedSet.Add(currentTile);
//Destination reached
if (currentTile == destination)
{
return PathBetween(destination, origin);
}
foreach (Tile neighbor in NeighborTiles(currentTile))
{
if(closedSet.Contains(neighbor))
continue;
float costToNeighbor = currentTile.costFromOrigin + neighbor.terrainCost + tileDistance;
if (costToNeighbor < neighbor.costFromOrigin || !openSet.Contains(neighbor))
{
neighbor.costFromOrigin = costToNeighbor;
neighbor.costToDestination = Vector3.Distance(destination.transform.position, neighbor.transform.position);
neighbor.parent = currentTile;
if (!openSet.Contains(neighbor))
openSet.Add(neighbor);
}
}
}
return null;
}
/// <summary>
/// Returns a list of all neighboring hexagonal tiles and ladders
/// </summary>
/// <param name="origin"></param>
/// <returns></returns>
private List<Tile> NeighborTiles(Tile origin)
{
const float HEXAGONAL_OFFSET = 1.75f;
List<Tile> tiles = new List<Tile>();
Vector3 direction = Vector3.forward * (origin.GetComponent<MeshFilter>().sharedMesh.bounds.extents.x * HEXAGONAL_OFFSET);
float rayLength = 4f;
float rayHeightOffset = 1f;
//Rotate a raycast in 60 degree steps and find all adjacent tiles
for (int i = 0; i < 6; i++)
{
direction = Quaternion.Euler(0f, 60f, 0f) * direction;
Vector3 aboveTilePos = (origin.transform.position + direction).With(y: origin.transform.position.y + rayHeightOffset);
if (Physics.Raycast(aboveTilePos, Vector3.down, out RaycastHit hit, rayLength, tileMask))
{
Tile hitTile = hit.transform.GetComponent<Tile>();
if (hitTile.Occupied == false)
tiles.Add(hitTile);
}
Debug.DrawRay(aboveTilePos, Vector3.down * rayLength, Color.blue);
}
//Additionally add connected tiles such as ladders
if (origin.connectedTile != null)
tiles.Add(origin.connectedTile);
return tiles;
}
/// <summary>
/// Called by Interact.cs to create a path between two tiles on the grid
/// </summary>
/// <param name="dest"></param>
/// <param name="source"></param>
/// <returns></returns>
public Path PathBetween(Tile dest, Tile source)
{
Path path = MakePath(dest, source);
illustrator.IllustratePath(path);
return path;
}
/// <summary>
/// Creates a path between two tiles
/// </summary>
/// <param name="destination"></param>
/// <param name="origin"></param>
/// <returns></returns>
private Path MakePath(Tile destination, Tile origin)
{
List<Tile> tiles = new List<Tile>();
Tile current = destination;
while (current != origin)
{
tiles.Add(current);
if (current.parent != null)
current = current.parent;
else
break;
}
tiles.Add(origin);
tiles.Reverse();
Path path = new Path();
path.tiles = tiles.ToArray();
return path;
}
}#UnityDevelopment #AStarAlgorithm #GameDev #Pathfinding #Unity3D 🚀🎮✨
