Search.cs

using UnityEngine;
using System.Collections.Generic;

public class Search : MonoBehaviour
{
    int gridSize = 10;
    void Start()
    {
        Tile[,] tiles = new Tile[gridSize, gridSize];
        for (int x = 0; x < gridSize; x++)
        {
            for (int z = 0; z < gridSize; z++)
            {
                GameObject newObject = new GameObject("Tile " + x + " " + z);
                tiles[x, z] = newObject.AddComponent<Tile>();
                newObject.transform.position = new Vector3(x, 0, z);
            }
        }

        for (int x = 0; x < gridSize; x++)
        {
            for (int z = 0; z < gridSize; z++)
            {
                if (InBounds(x, z - 1))
                {
                    tiles[x, z].neighbors.Add(tiles[x, z - 1]);
                }
                if (InBounds(x, z + 1))
                {
                    tiles[x, z].neighbors.Add(tiles[x, z + 1]);
                }
                if (InBounds(x - 1, z))
                {
                    tiles[x, z].neighbors.Add(tiles[x - 1, z]);
                }
                if (InBounds(x + 1, z))
                {
                    tiles[x, z].neighbors.Add(tiles[x + 1, z]);
                }
            }
        }

        Tile[] path = makePath(tiles[0, 0], tiles[gridSize - 1, gridSize - 1]);
        foreach (var tile in path)
        {
            Debug.Log(tile.transform.position + " " + tile.gScore + " " + tile.fScore);
        }
    }

    bool InBounds(int x, int z)
    {
        return (0 <= x && x < gridSize) && (0 <= z && z < gridSize);
    }

    //A*, please be gentle (Reference: https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode)
    Tile[] makePath(Tile start, Tile destination)
    {
        //setup - reset all nodes' values
        foreach (Tile t in FindObjectsOfType<Tile>())
        {
            t.pathParent = null;
            t.gScore = 0;
            t.fScore = 0;
        }

        List<Tile> closedList = new List<Tile>();   //already evaluated tiles
        List<Tile> openList = new List<Tile>();     //discovered, but not yet evaluated, tiles
        openList.Add(start);
        start.fScore = getFScore(start.gameObject, destination.gameObject);

        //while there are still tiles to be evaluated
        while (openList.Count > 0)
        {
            Tile current = null;
            int lowestFScore = int.MaxValue;

            //Find the lowest F Score and make that tile the current one to evaluate
            foreach (Tile t in openList)
            {
                if (t.fScore < lowestFScore)
                {
                    current = t;
                    lowestFScore = t.fScore;
                }
            }



            //We did it reddit! Destination found and path completed
            if (current == destination)
            {
                //Put together the path with all the parent references
                List<Tile> fullPath = new List<Tile>();
                Tile currPahNode = destination;
                while (currPahNode != start) //DON'T add the starting tile (that the unit is already on) to the list.  Star the path at the first tile to go to.
                {
                    fullPath.Add(currPahNode);
                    currPahNode = currPahNode.pathParent;
                }

                //Reverse list to get the forward direction
                fullPath.Reverse();
                return fullPath.ToArray();
            }



            //Current node has been evaluated, but we're not done yet.  Find the next one to evaluate!
            openList.Remove(current);
            closedList.Add(current);
            foreach (Tile neighbor in current.neighbors)
            {
                //skip empty neighbor links or already evaluated tiles
                if (neighbor == null || closedList.Contains(neighbor))
                    continue;

                int tentativeGScore = current.gScore + getFScore(neighbor.gameObject, destination.gameObject);

                //if this is a better path, update its info and (if not already in the open list,) add it to the open list of tiles to evaluate
                if (!openList.Contains(neighbor) || tentativeGScore < neighbor.gScore)
                {
                    neighbor.pathParent = current;
                    neighbor.gScore = tentativeGScore;
                    neighbor.fScore = getFScore(neighbor.gameObject, destination.gameObject);

                    if (!openList.Contains(neighbor))
                        openList.Add(neighbor);
                }
            }
        }

        //Failure
        Debug.Log("Could not find a path from " + start.gameObject.name + " to " + destination.gameObject.name + ".  Returning Null!");
        return null;
    }
    // (X, Z) distance between two tiles
    int getFScore(GameObject from, GameObject to)
    {
        Vector2 start = new Vector2(from.transform.position.x, from.transform.position.z);
        Vector2 finish = new Vector2(to.transform.position.x, to.transform.position.z);
        return Mathf.RoundToInt(Vector2.Distance(start, finish) * 1000);
    }
}