Skip to content

Instantly share code, notes, and snippets.

@bendangelo
Created March 5, 2022 21:12
Show Gist options
  • Save bendangelo/12f1a9d3278b13e16feded13ebb26c1e to your computer and use it in GitHub Desktop.
Save bendangelo/12f1a9d3278b13e16feded13ebb26c1e to your computer and use it in GitHub Desktop.
PathFind & PathFindProps classes for finding paths in tile-based games
// (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;
}
}
// (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);
}
}
// (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);
};
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment