using System.Collections.Generic;
using System.Linq;
using UnityEngine;
namespace Voodoocado
{
public class Step
{
public Vector2Int position;
public float height;
public float F;
public float G;
public float H;
public Step parent;
public new string ToString()
{
return position.ToString();
}
}
public class Path
{
public List<Step> steps;
public Path(List<Step> steps)
{
this.steps = steps;
}
public new string ToString()
{
string str = "";
foreach (Step step in steps)
str += step.ToString() + ", ";
return str;
}
}
public static class AStar
{
public delegate bool IsFree(Vector2Int position);
public static Path FindPath(IsFree isFree, Vector2Int from, Vector2Int to)
{
// algorithm
Step current = null;
var start = new Step { position = from };
var target = new Step { position = to };
var openList = new List<Step>();
var closedList = new List<Step>();
// start by adding the original position to the open list
openList.Add(start);
while (openList.Count > 0)
{
//Debug.Log(current != null ? current.position.ToString() : "null");
// get the square with the lowest F score
var lowest = openList.Min(l => l.F);
current = openList.First(l => l.F == lowest);
// add the current square to the closed list
closedList.Add(current);
// show current square on the map
/*
GameObject sphere = GameObject.CreatePrimitive(PrimitiveType.Sphere);
sphere.transform.position = Game.instance.gameState.map.GetRealWorldVectorPosition(current.position);
sphere.transform.parent = spheres.transform;
sphere.name = "Path";
*/
// remove it from the open list
openList.Remove(current);
// if we added the destination to the closed list, we've found a path
if (closedList.FirstOrDefault(l => l.position.x == target.position.x && l.position.y == target.position.y) != null)
break;
var adjacentSquares = GetWalkableAdjacentSquares(isFree, current.position, to);
//Debug.Log(adjacentSquares.Count);
foreach (var adjacentSquare in adjacentSquares)
{
// if this adjacent square is already in the closed list, ignore it
if (closedList.FirstOrDefault(l => l.position.x == adjacentSquare.position.x
&& l.position.y == adjacentSquare.position.y) != null)
continue;
// if it's not in the open list...
if (openList.FirstOrDefault(l => l.position.x == adjacentSquare.position.x
&& l.position.y == adjacentSquare.position.y) == null)
{
// compute its score, set the parent
adjacentSquare.H = ComputeHScore(adjacentSquare.position, target.position);
adjacentSquare.F = adjacentSquare.G + adjacentSquare.H;
adjacentSquare.parent = current;
// and add it to the open list
openList.Insert(0, adjacentSquare);
}
else
{
// test if using the current G score makes the adjacent square's F score
// lower, if yes update the parent because it means it's a better path
if (adjacentSquare.F > adjacentSquare.G + adjacentSquare.H)
{
adjacentSquare.F = adjacentSquare.G + adjacentSquare.H;
adjacentSquare.parent = current;
}
}
}
}
List<Step> result = new List<Step>();
// assume path was found; let's show it
while (current != null)
{
result.Add(current);
current = current.parent;
}
result.Reverse();
return new Path(result);
}
private static Vector2Int[] neighbours =
{
new Vector2Int(-1,0),
new Vector2Int(0,1),
new Vector2Int(1,1),
new Vector2Int(1,0),
new Vector2Int(0,-1),
new Vector2Int(-1,-1),
};
internal static float Distance(Vector2Int from, Vector2Int to)
{
// Calculate the distance in relation to 1 hex tile
float distance =
Vector3.Distance(GetWorldPosition(from), GetWorldPosition(to)) /
GetWorldPosition(new Vector2Int(1, 0)).magnitude;
return distance;
}
// Convert radial hex grid map position to real world position
public static Vector3 GetWorldPosition(Vector2Int radialPosition)
{
// sqrt(3) * 0.75
const float gridX = 1.299038f;
// 3 * 0.75
const float gridY = 2.25f;
return new Vector3(
gridX * radialPosition.x, 0,
gridY * radialPosition.y);
}
static List<Step> GetWalkableAdjacentSquares(IsFree isFree, Vector2Int position, Vector2Int finalTarget)
{
var proposedSteps = new List<Step>();
// Hex grid radial position neighbours
foreach (Vector2Int neighbour in neighbours)
{
Vector2Int proposedStep = position + neighbour;
if ((proposedStep != finalTarget) && !isFree(proposedStep))
continue;
float g = ComputeGScore(position, proposedStep);
// A g score of zero indicates that it is not possible to pass this square
if(g > 0f)
proposedSteps.Add(new Step { position = proposedStep, G = g });
};
return proposedSteps;
}
// Just a measurement of how close we are to the target at any given point
// Could also be computed as the x and y components individually, for example.
//
static float ComputeHScore(Vector2Int from, Vector2Int to)
{
Vector3 positionFrom = GetWorldPosition(from);
Vector3 positionTo = GetWorldPosition(to);
return (positionFrom - positionTo).magnitude;
}
static float ComputeGScore(Vector2Int from, Vector2Int to)
{
Vector3 positionFrom = AStar.GetWorldPosition(from);
Vector3 positionTo = AStar.GetWorldPosition(to);
return (positionFrom - positionTo).magnitude;
}
}
}