PathFind & PathFindProps classes for finding paths in tile-based games

Node.cs

// (c) 2022 Ben D'Angelo. www.throwtheproject.com
// This code is licensed under MIT license (see LICENSE.txt for details)
using UnityEngine;
using System.Collections;
using System;

public class Node : IComparable<Node> {

    public Vector2 pos;
    public Node parent;

    public int depth;
    public int cost;
    public float g;
    public float f;
    public float h;

    public bool closed = false;
    public bool opened;

    public Node(Vector2 pos){
        this.pos = pos;
    }

    public int CompareTo(Node other){
        int value = (int)(other.f - this.f);

        return value;
    }

    public bool IsFirstNode(){
        return pos.x == -1;
    }

}

PathFind.cs

// (c) 2022 Ben D'Angelo. www.throwtheproject.com
// This code is licensed under MIT license (see LICENSE.txt for details)
using UnityEngine;
using UnityEngine.Assertions;
using System.Collections;
using System.Collections.Generic;
using System;
using Wintellect.PowerCollections;

public class PathFind {
    static float SQRT2 = 1.4142135623730951f;

    private OrderedSet<Node> _openList;

    private Dictionary<Vector2, Node> _nodeCache;

    private PathFindProps _props;

    private Vector2[] _directions;

    private Deque<Vector2> _finishedPath;

    private int _nodeCount;

    private int mapWidth;
    private int mapHeight;

    public PathFind(int mapWidth, int mapHeight){
        this.Resize(mapWidth, mapHeight);

        _openList = new OrderedSet<Node>();
        _nodeCache = new Dictionary<Vector2, Node>();
        _directions = new Vector2[4];

        _directions[0] = new Vector2(1, 0);
        _directions[1] = new Vector2(-1, 0);
        _directions[2] = new Vector2(0, 1);
        _directions[3] = new Vector2(0, -1);
    }
    
    public void Resize(int mapWidth, int mapHeight) {
        this.mapWidth = mapWidth;
        this.mapHeight = mapHeight;
    }

    public Deque<Vector2> Search(PathFindProps pathFindProps){
        _openList.Clear();
        _nodeCache.Clear();
        _nodeCount = 0;

        _props = pathFindProps;

        if (_props.mapWidth != -1) {
            this.Resize(_props.mapWidth, _props.mapHeight);
        }

        int count = 0;

        Node parent = new Node(new Vector2(-1, -1));
        parent.depth = ++_nodeCount;
        parent.opened = true;
        AddNode(_props.startPos, parent);

        Node n;

        while (_openList.Count != 0){
            n = _openList.RemoveLast();

            n.closed = true;

            for(int i=0; i<_directions.Length; i++){
                Vector2 dir = n.pos + _directions[i];
                if(AddNode(dir, n)){
                    return _finishedPath;
                }
            }

            count++;
            if(count >= _props.maxLength){
                // max searchs met
                return null;
            }

        }

        // path not found
        return null;
    }

    private float Heuristic(float dx, float dy){
        // manhattan, moves in big straight lines
        // return (dx + dy) * 1000000;
        // chebyshev
        return Mathf.Max(dx, dy) * 1000000;
        // euclidean
        // return Mathf.Sqrt(dx * dx + dy * dy) * 1000000;
    }

    private bool WithinMap(Vector2 tilePos) {
        return tilePos.x >= 0 && tilePos.x < this.mapWidth && tilePos.y >= 0 && tilePos.y < this.mapHeight;
    }

    private bool AddNode(Vector2 pos, Node parentNode){
        if (!WithinMap(pos)) return false;

        bool result = CheckTile(pos, parentNode);

        if (!result) {
            return false;
        }

        int cost = 0;

        if (_props.OnCost != null) {
            cost = _props.OnCost(pos, parentNode.pos);

            // ensure has enough cost to enter tile
            if (cost == -1 || parentNode.cost + cost > _props.costLimit) {
                return false;
            }
        }

        Node n;
        int currentCost = cost + parentNode.cost;

        if (!_nodeCache.TryGetValue(pos, out n)) {
            n = new Node(pos);
            n.depth = ++_nodeCount;
            n.cost = cost + parentNode.cost;
            _nodeCache.Add(n.pos, n);
        }

        if (currentCost < n.cost) {
            // this node has a cheaper cost
            // so use it
            n.cost = currentCost;

            // check tile again
            n.closed = false;
            n.opened = false;
        }

        // if already checked, skip
        if (n.closed) {
            return false;
        }

        // path is finished when both nodes meet
        if (n.pos == _props.endPos) {
             CreatePath(n, parentNode);
             return true;
        }

        Vector2 nodePos = n.pos;

        // get distance between current node and parent node
        float ng = parentNode.g + ((nodePos.x - parentNode.pos.x == 0 || nodePos.y - parentNode.pos.y == 0) ? 1 : SQRT2);

        // check is node has not been inspected yet or 
        // can be reached with smaller cost from current node
        if(!n.opened || ng < n.g) {
            n.g = ng;

            if(n.h == 0) {
                n.h = _props.weight * Heuristic(Mathf.Abs(nodePos.x - _props.endPos.x), Mathf.Abs(nodePos.y - _props.endPos.y));
            }

            // scale up the useful numbers
            // add depth to guarantee uniqueness
            n.f = (n.g + n.h) + n.depth;
            n.parent = parentNode;

            // if(n.parent.IsFirstNode()){
            //     n.g = 0;
            //     n.f = 0;
            // }

            if(!n.opened){
                n.opened = true;
                _openList.Add(n);
            }

        }

        return false;
    }

    private bool CheckTile(Vector2 pos, Node parentNode){
        bool result = true;

        if(_props.OnCheck != null){
            result = _props.OnCheck(pos, parentNode.pos);
        }

        return result;
    }

    private List<Vector2> CreateBacktrace(Node node, Node parentNode){
        List<Vector2> path = new List<Vector2>();
        path.Add(node.pos);
        path.Add(parentNode.pos);

        if (parentNode.parent != null) {
            while (!parentNode.parent.IsFirstNode()) {
                parentNode = parentNode.parent;
                path.Add(parentNode.pos);
            }
        }

        return path;
    }

    private void CreatePath(Node node, Node parentNode){
        List<Vector2> path = CreateBacktrace(node, parentNode);

        if (_props.pathLimit > 0) {
            if (path.Count > _props.pathLimit) {
                // path starts from the end -> beginning
                // temporarily reverse to cut off the non-wanted
                path.Reverse();
                path = path.GetRange(0, _props.pathLimit);
                path.Reverse();
            }
        }

        _finishedPath = new Deque<Vector2>(path);
    }
}

PathFindProps.cs

// (c) 2022 Ben D'Angelo. www.throwtheproject.com
// This code is licensed under MIT license (see LICENSE.txt for details)
using UnityEngine;
using System.Collections;
using System;

public class PathFindProps {

    public static int defaultMapWidth = -1;
    public static int defaultMapHeight = -1;

    public ObjectMap objectMap;

    public ITileUtil tileUtil;

    public Vector2 startPos { get; set; }
    public Vector2 endPos { get; set; }

    public Func<Vector2, Vector2, bool> OnCheck { get; set; }
    public Func<Vector2, Vector2, int> OnCost { get; set; }

    public int maxLength { get; set; }
    public float weight { get; set; }
    public int costLimit { get; set; }
    public int pathLimit { get; set; }

    public int mapWidth { get; set; }
    public int mapHeight { get; set; }

    public PathFindProps() {
        maxLength = 100;
        weight = 1.0f;
    }

    public void Reset() {
        mapWidth = defaultMapWidth;
        mapHeight = defaultMapHeight;
    }

    public void MoveCheck(IEntity currentEntity, Vector2 startPos, Vector2 endPos, bool ignoreWalls = false) {
        Reset();

        costLimit = currentEntity.equip.JumpLimit;
        this.pathLimit = 0;
        this.startPos = startPos;
        this.endPos = endPos;

        bool moveThroughEnemies = currentEntity.HasGadget(GadgetType.BarbedWire);

        OnCheck = (tile, par) => {
            if (ignoreWalls) {
                if (tile == endPos) {
                    // allow final tile to have an entity
                    // because not stopping there (see dialogue)
                    return tileUtil.IsWalkable(tile, (e) => true);
                }

                // avoid all entities in path to prevent stopping on one
                return tileUtil.IsWalkable(tile, (e) => e == currentEntity);
            }

            if (tile == endPos) {
                // ensure final tile is free from any entity
                return tileUtil.IsWalkable(tile);
            }

            return tileUtil.IsWalkable(tile, (en) => en.IsTeammate(currentEntity) || en.IsDead || moveThroughEnemies);
        };

        OnCost = (pos, par) => {
            if (ignoreWalls) return 0;
            if (par.x == -1) return 0;

            if (currentEntity.equip.HasVal(Stat.UnlimitedJump)) return 0;

            return tileUtil.JumpCost(pos, par);
        };
    }
}