How to simulate D&D 3.5 Pathfinding with square grid? C#

Hello!

I’m working on an TBS game like Final Fantasy Tactics or XCOM:Enemy Unkown, and i’m facing a really hard problem.

I want my units to move using D&D 3.5v rules, where the diagonal movement cost it’s 1-2-1. I’ve already have a way to set up the basic grid so my game looks like this right now:

My problem comes when i’ve to apply this movement with pathfinding, so the grid knows what obstacles there are in the way, and how much does it really cost to reach to X position.
For my solutions, i need an algorithm that allows me to check every square around my character, and calculates the movement cost of those squares, but, applying the 1-2-1 diagonal movement rule. I’ve tried to use Breadth First Search and Dijkstra’s algorythms but i can’t find a way to apply that extra diagonal movement rule…

So, any ideas on how to solve this??

Thanks!

I did it like this:

Assuming that each grid space is 1 Unity unit big:

For every waypoint in the path, check if the distance to the next one is > ~ 1.2 (A straight connection would be ~1, a diagonal connection would be ~1.7 IIRC). If it is, then you know the next waypoint is diagonal and you need to add 2 to your movement cost, otherwise add 1. You can also use the two waypoints’ coordinates and directly compare them; if x AND z differ, then you know it has to be diagonal.

Ok!! I’ve finally made it!! I used this code as a base for mine: Implementation of A*

and after a lot of tweaks, EUREKA!! :smiley:

using System;
using System.Collections;
using System.Collections.Generic;


// A* needs only a WeightedGraph and a location type L, and does *not*
// have to be a grid. However, in the example code I am using a grid.
public interface WeightedGraph<L>
{
    //property signatures   
    double Cost(Location a, Location b, Location c, Dictionary<Location, Location> d);
    IEnumerable<Location> Neighbors(Location id);
}


public struct Location
{
    // Implementation notes: I am using the default Equals but it can
    // be slow. You'll probably want to override both Equals and
    // GetHashCode in a real project.

    //Fields de la estructura
    public readonly int x, y;
    //constructor de Location
    public Location(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}


public class SquareGrid : WeightedGraph<Location>
{
    // Implementation notes: I made the fields public for convenience,
    // but in a real project you'll probably want to follow standard
    // style and make them private.

    //Fields
    public static readonly Location[] DIRS = new[]
        {
            new Location(1, 0),
            new Location (1,-1),
            new Location(0, -1),
            new Location (-1,-1),
            new Location(-1, 0),
            new Location(-1,1),
            new Location(0, 1),
            new Location(1,1)
        };

    public int width, height;
    public HashSet<Location> walls = new HashSet<Location>();
    public HashSet<Location> forests = new HashSet<Location>();

    //Constructor
    public SquareGrid(int width, int height)
    {
        this.width = width;
        this.height = height;
    }

    //Other Functions

    //This cheks' if we're in the border of the map
    public bool InBounds(Location id)
    {
        return 0 <= id.x && id.x < width && 0 <= id.y && id.y < height;
    }

    //This tells us where are the walls
    public bool Passable(Location id)
    {
        return !walls.Contains(id);
    }

    //Property implementation

    //This returns the cost of the tile we want to move
    public double Cost(Location a, Location b, Location c, Dictionary<Location, Location> d)
    {

        double Coste = 1;
        var current = b;
        var next = c;
        var start = a;
        
        //We check if the direcctionof the next tile it's a diagonal and then we return the cost
        //if (next.x - 1 == d[current].x && next.y + 1 == d[current].y)
        //Console.Write(" Current x y: " + current.x + " " + current.y);

        //Console.Write(" parent x,y: " + d[current].x + " " + d[current].y);
        if (next.x + 1 == current.x && next.y + 1 == current.y)
        {
            Coste = 1.5;
        }
        if (next.x - 1 == current.x && next.y + 1 == current.y)
        {
            Coste = 1.5;
        }
        if (next.x - 1 == current.x && next.y - 1 == current.y)
        {
            Coste = 1.5;
        }
        if (next.x + 1 == current.x && next.y - 1 == current.y)
        {
            Coste = 1.5;
        }

        return Coste;
    }

    public IEnumerable<Location> Neighbors(Location id)
    {
        foreach (var dir in DIRS)
        {
            Location next = new Location(id.x + dir.x, id.y + dir.y);
            if (InBounds(next) && Passable(next))
            {
                yield return next;
            }
        }
    }
}


public class PriorityQueue<T>
{
    // I'm using an unsorted array for this example, but ideally this
    // would be a binary heap. Find a binary heap class:
    // * https://bitbucket.org/BlueRaja/high-speed-priority-queue-for-c/wiki/Home
    // * http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx
    // * http://xfleury.github.io/graphsearch.html
    // * http://stackoverflow.com/questions/102398/priority-queue-in-net

    private List<Tuple<T, int>> elements = new List<Tuple<T, int>>();

    public int Count
    {
        get { return elements.Count; }
    }

    public void Enqueue(T item, int priority)
    {
        elements.Add(Tuple.Create(item, priority));
    }

    public T Dequeue()
    {
        int bestIndex = 0;

        for (int i = 0; i < elements.Count; i++)
        {
            if (elements*.Item2 < elements[bestIndex].Item2)*

{
bestIndex = i;
}
}

T bestItem = elements[bestIndex].Item1;
elements.RemoveAt(bestIndex);
return bestItem;
}
}

public class AStarSearch
{
public Dictionary<Location, Location> cameFrom
= new Dictionary<Location, Location>();
public Dictionary<Location, double> costSoFar
= new Dictionary<Location, double>();

public AStarSearch(WeightedGraph graph, Location start)
{
var frontier = new PriorityQueue();
frontier.Enqueue(start, 0);

cameFrom.Add(start, start);

costSoFar.Add(start, 1.5);

//intentamos que recorra solo un area que nosotros delimitamos
//en cada vuelta hace: 4 casillas, luego 8, luego 12, luego 16…
int vueltas = 0;
//esto es el nº de veces que da la vuelta
int radio = 8;
//llenamos k con el valor que nos interesa
for (int k = 0; k < radio; k++)
{
vueltas = vueltas + (k * 4); //esto ya esta procesado par que el bucle haga bien su recorrido
}
//este primer bucle nos controla lo grande que es el radio de nuestro algritmo de busqueda
for (int i = 0; i <= vueltas; i++)
{
var current = frontier.Dequeue();

foreach (var next in graph.Neighbors(current))
{
//int newCost = costSoFar[current] + graph.Cost(current, next);
//esto es lo que controla lo que cuestan las siguientes casillas; aquí está la clave
//Console.Write(" next: " + next.x + " " + next.y);

double newCost = costSoFar[current] + graph.Cost(start, current, next, cameFrom);
//if (!costSoFar.ContainsKey(next) || newCost < costSoFar[next])
if (!cameFrom.ContainsKey(next))
{

costSoFar.Add(next, newCost);
cameFrom.Add(next, current);
frontier.Enqueue(next, (int)newCost);

}
}
}
}
}

public class Test
{
static void DrawGrid(SquareGrid grid, AStarSearch astar)
{
// Print out the cameFrom array
for (var y = 0; y < 20; y++)
{
for (var x = 0; x < 20; x++)
{
Location id = new Location(x, y);
Location ptr = id;
if (!astar.cameFrom.TryGetValue(id, out ptr))
{
ptr = id;
}
if (grid.walls.Contains(id)) { Console.Write(“##”); }

else if (ptr.x == x + 1) { Console.Write(Math.Floor(astar.costSoFar[ptr]) + " "); }
else if (ptr.x == x - 1) { Console.Write(Math.Floor(astar.costSoFar[ptr]) + " "); }
else if (ptr.y == y + 1) { Console.Write(Math.Floor(astar.costSoFar[ptr]) + " "); }
else if (ptr.y == y - 1) { Console.Write(Math.Floor(astar.costSoFar[ptr]) + " "); }

else { Console.Write("* "); }
}
Console.WriteLine();
}
}

static void Main()
{
// Make “diagram 4” from main article
var grid = new SquareGrid(20, 20);
for (var x = 1; x < 9; x++)
{
for (var y = 7; y < 9; y++)
{
grid.walls.Add(new Location(x, y));
}
}

for (var x = 7; x < 9; x++)
{
for (var y = 4; y < 9; y++)
{
grid.walls.Add(new Location(x, y));
}
}

// Run Dijkstra
var astar = new AStarSearch(grid, new Location(10, 4));

DrawGrid(grid, astar);
}
}
Sorry for all the spanish comments, i’ll edit it later.
This code it’s just a C# implementation, to use it in Unity, you just have to adjust the location structure to match your tile strcuture. and the start position, to match your Player position. Also this is made with tuples (X,Y) posiitons, so all the calculus have to be adjusted for the X,Y,Z coordinates… but it’s a matter of time. All the logic works :smiley: