Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A tile searching algorithm for tactical-rpgs like games or any tile-based game. Unity C#
// (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.Collections.Generic;
using UnityEngine.Assertions;
using System;
public class TileNode {
public Vector2 pos;
public TileNode parent;
public int depth;
public int cost;
public bool touched = false;
public TileNode(Vector2 pos){
this.pos = pos;
}
public Vector2 ToHash(Vector2 next) {
return this.pos * 1000 + next;
}
}
// (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.Collections.Generic;
using UnityEngine.Assertions;
using System;
public class TileNode {
public Vector2 pos;
public TileNode parent;
public int depth;
public int cost;
public bool touched = false;
public TileNode(Vector2 pos){
this.pos = pos;
}
public Vector2 ToHash(Vector2 next) {
return this.pos * 1000 + next;
}
}
public class TileSearch {
public static int UNLIMITED_LENGTH = -1;
private Queue<TileNode> _stack;
private Dictionary<Vector2, TileNode> _nodes;
private Dictionary<Vector2, bool> _touches;
private Dictionary<Vector2, bool> _finishTouches;
public TileSearchProps props { get; private set; }
public int mapWidth { get; private set; }
public int mapHeight { get; private set; }
public TileSearch(int mapWidth, int mapHeight){
this.Resize(mapWidth, mapHeight);
_stack = new Queue<TileNode>();
_nodes = new Dictionary<Vector2, TileNode>();
_touches = new Dictionary<Vector2, bool>();
_finishTouches = new Dictionary<Vector2, bool>();
}
public void Resize(int mapWidth, int mapHeight) {
this.mapWidth = mapWidth;
this.mapHeight = mapHeight;
}
private bool WithinMap(Vector2 tilePos) {
return tilePos.x >= 0 && tilePos.x < this.mapWidth && tilePos.y >= 0 && tilePos.y < this.mapHeight;
}
public void Search(TileSearchProps props){
this.props = props;
if (props.mapWidth != -1) {
this.Resize(props.mapWidth, props.mapHeight);
}
if (props.length != UNLIMITED_LENGTH) {
Assert.IsTrue(props.minLength < props.length, "Tilesearch min length same or bigger than length");
}
_nodes.Clear();
_stack.Clear();
_touches.Clear();
_finishTouches.Clear();
TileNode parentNode = new TileNode(new Vector2(-1, -1));
parentNode.depth = 1;
AddNode(props.startPos, parentNode);
while(_stack.Count > 0){
TileNode n = _stack.Dequeue();
if (props.OnSpread != null) {
props.OnSpread(n, AddNode);
} else {
AddNode(new Vector2(n.pos.x + 1, n.pos.y), n);
AddNode(new Vector2(n.pos.x - 1, n.pos.y), n);
AddNode(new Vector2(n.pos.x, n.pos.y + 1), n);
AddNode(new Vector2(n.pos.x, n.pos.y - 1), n);
if (props.vertical) {
AddNode(new Vector2(n.pos.x + 1, n.pos.y + 1), n);
AddNode(new Vector2(n.pos.x - 1, n.pos.y - 1), n);
AddNode(new Vector2(n.pos.x - 1, n.pos.y + 1), n);
AddNode(new Vector2(n.pos.x + 1, n.pos.y - 1), n);
}
}
}
}
protected void AddNode(Vector2 pos, TileNode parentNode){
if (props.length > -1 && parentNode.depth > props.length) {
if (props.OnExtend == null || !props.OnExtend(pos, parentNode.pos, parentNode.depth)) {
return;
}
}
Vector2 nodeHash = parentNode.ToHash(pos);
if (_finishTouches.ContainsKey(pos) || _touches.ContainsKey(nodeHash)) {
return;
}
if (props.withinMapBounds && !WithinMap(pos)) {
return;
}
int depth = parentNode.depth;
if (!CanPass(pos, parentNode.pos, depth)) {
_touches[nodeHash] = true;
return;
}
int cost = 0;
if (props.OnCost != null) {
cost = props.OnCost(pos, parentNode.pos, depth);
// ensure has enough cost to enter tile
if (cost == -1 || parentNode.cost + cost > props.costLimit) {
_touches[nodeHash] = true;
return;
}
}
if (props.OnVisit != null && depth > props.minLength) {
if (props.OnValidVisit == null || props.OnValidVisit(pos, parentNode.pos, depth)) {
props.OnVisit(pos, depth);
// reached last step, ignore all further queries
_finishTouches[pos] = true;
}
} else {
// reached last step
_finishTouches[pos] = true;
}
// touched from this direction
_touches[nodeHash] = true;
// continue searching
TileNode node;
if (!_nodes.TryGetValue(pos, out node)) {
node = new TileNode(pos);
_nodes.Add(node.pos, node);
}
node.parent = parentNode;
node.depth = depth + 1;
node.cost = cost + parentNode.cost;
_stack.Enqueue(node);
}
protected bool CanPass(Vector2 pos, Vector2 parentPos, int depth){
if (!props.diagonal && (pos.x != props.startPos.x && pos.y != props.startPos.y)) {
return false;
}
if (props.OnCheck != null && !props.OnCheck(pos, parentPos, depth)) {
return false;
}
return true;
}
}
// (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;
public class TileSearchProps {
public const int MAX_LENGTH = 99;
public static int defaultMapWidth = -1;
public static int defaultMapHeight = -1;
public Vector2 startPos { get; set; }
public int length { get; set; }
public int minLength { get; set; }
public bool vertical { get; set; }
public bool diagonal { get; set; }
public bool withinMapBounds { get; set; }
public string name { get; set; }
public int costLimit { get; set; }
public int mapWidth { get; set; }
public int mapHeight { get; set; }
public Action<Vector2, int> OnVisit { get; set; }
public Func<Vector2, Vector2, int, bool> OnCheck { get; set; }
public Action<TileNode, Action<Vector2, TileNode>> OnSpread { get; set; }
public Func<Vector2, Vector2, int, int> OnCost { get; set; }
public Func<Vector2, Vector2, int, bool> OnExtend { get; set; }
public Func<Vector2, Vector2, int, bool> OnValidVisit { get; set; }
public TileSearchProps() {
Reset();
}
public void Reset() {
diagonal = true;
vertical = false;
minLength = 0;
withinMapBounds = true;
OnSpread = null;
OnCheck = null;
OnCost = null;
OnExtend = null;
OnValidVisit = null;
costLimit = 0;
mapWidth = defaultMapWidth;
mapHeight = defaultMapHeight;
}
// below are examples of how this class can be used
void KnifeCheck(IEntity currentEntity, Weapon weapon, Vector2 startPos) {
Reset();
length = weapon.Range + 1;
minLength = 1;
diagonal = false;
costLimit = weapon.HeightLimit;
this.startPos = startPos;
OnValidVisit = (pos, par, d) => {
return tileUtil.CanTargetTile(pos);
};
OnCheck = (pos, par, depth) => {
return tileMap.IsWalkable(pos.x, pos.y);
};
OnCost = (pos, par, depth) => {
return AbilityCost(pos, par, weapon.HeightLimit);
};
}
public void MoveCheck(IEntity currentEntity, Vector2 startPos) {
Reset();
this.startPos = startPos;
length = currentEntity.equip.MoveRange + 1;
minLength = 0;
costLimit = currentEntity.equip.JumpLimit;
bool moveThroughEnemies = currentEntity.HasGadget(GadgetType.BarbedWire);
OnCheck = (pos, par, depth) => {
bool walkable = tileUtil.IsWalkable(pos, (en) => en.IsTeammate(currentEntity) || en.IsDead || moveThroughEnemies);
return walkable;
};
OnCost = (pos, par, depth) => {
if (par.x == -1) return 0;
int cost = tileUtil.JumpCost(pos, par);
// remove water for now
// float water = objectMap.GetWaterDepth(pos);
// if (water > 0) return (int)water + cost;
if (currentEntity.equip.HasVal(Stat.UnlimitedJump)) return 0;
return cost;
};
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment