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

Question

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:

http://gyazo.com/a2800c0b2da99e92a8c14a9bff5abb09

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!

Answer 1

Ok!! I've finally made it!! I used this code as a base for mine: http://www.redblobgames.com/pathfinding/a-star/implementation.html#csharp

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

 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[i].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<Location> graph, Location start)
     {
         var frontier = new PriorityQueue<Location>();
         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 :D

Answer 2

Answer by Cherno · Apr 09, 2015 at 06:54 AM

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.

Add comment · Show 4 · Share

Targaryen · Apr 09, 2015 at 07:15 AM 0

Share

Thanks! i'll try that way, althought, if i add 2 to every diagonal i check, i end up with diagonals costing 2 all the time.. how i can handle the 1-2-1 logic?? i mean, with your method i can't see how i can give the first diagonal cost 1, the second 2, the third cost 1, the fourth 2... etc

Cherno · Apr 09, 2015 at 08:45 AM 0

Share

Oh, I misread your description then. Well in that case, all you need to add is another counter that counts the number of diagonal connections, and every time you do have a diagonal connection, you check if the counter value is an even number. If yes, then the cost is 2. If not, the cost is 1.

 if((counterValue % 2) == 0) {
 even (divisible by two)
 }
 else if((counterValue % 2) != 0) {
 uneven (not divisible by two)
 }

Targaryen · Apr 10, 2015 at 02:36 AM 0

Share

Hi! I've been trying to code this, without progress.. the method you sugested it's Ok, if you use graphs with 8 conecctions, but that's usually a mess and really hard to code, so, i've been using this C# A*-Pathfinder template http://www.redblobgames.com/pathfinding/a-star/implementation.html and from there, i'm trying to get the movement that i want.

Right now the only problem that i got it's tha the graph i use makes the connections in the 4 cardinal points (up, right, left and down) and i've no idea on how to make the code know when it's making a diagonal.. i'll paste it:

 public double Cost(Location a, Location b, Location c, Dictionary<Location, Location> d)
     { 
         int Coste = 1;
         var current = b;
         var goal = a;
         //recorremos desde el punto que tenemos ahcia atras y contamos el nº de pasos, para luego poner ese numero como el coste
         while (!current.Equals(goal))
         {
             
             if (current.x + 1 == d[current].x && current.y == d[current].y)
             {
                 Coste++;
             }
             if (current.x == d[current].x && current.y + 1 == d[current].y)
             {
                 Coste++;
             }
             if (current.x - 1 == d[current].x && current.y == d[current].y)
             {
                 Coste++;
             }
             if (current.x == d[current].x && current.y - 1 == d[current].y)
             {
                 Coste++;
             }
 
             current = d[current];

         }
 
         return Coste;
     }

a it's the orginal position of the player, b, it's where it's the node of the code right now, c it's what's the next node and d it's the dictionary that keeps who's the parent of all nodes. With this and a few adjustements more in the whole code, the code can apply the cost of every grid following his method (described here http://www.redblobgames.com/pathfinding/a-star/introduction.html) with a result like this:

     * * * * * 8 7 6 5 4 3 4 5 6 7 8 * * * * 
     * * * * 8 7 6 5 4 3 2 3 4 5 6 7 8 * * * 
     * * * 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 * 
     * * 8 7 6 5 4 3 2 1 1 1 2 3 4 5 6 7 8 9 
     * * * 8 7 6 5 ####1 * 1 1 2 3 4 5 6 7 8 
     * * * * 8 7 6 ####1 1 1 2 3 4 5 6 7 8 9 
     * * * * * 8 7 ####2 1 2 3 4 5 6 7 8 9 * 
     * ################3 2 3 4 5 6 7 8 * * * 
     * ################4 3 4 5 6 7 8 * * * * 
     * * * * * * 8 7 6 5 4 5 6 7 8 * * * * * 
     * * * * * * * 8 7 6 5 6 7 8 * * * * * * 
     * * * * * * * * 8 7 6 7 8 * * * * * * * 
     * * * * * * * * * 8 7 8 * * * * * * * * 
     * * * * * * * * * * 8 * * * * * * * * * 
     * * * * * * * * * * * * * * * * * * * * 
     * * * * * * * * * * * * * * * * * * * * 
     * * * * * * * * * * * * * * * * * * * *

as you can see, this pattern doesn't look like dungeons & dragons movement rules...

Cherno · Apr 10, 2015 at 09:49 AM 0

Share

Converted to comment.

Can't help you there, I use Aron Granberg's Astar Pathfinding Project for all my pathfinding needs and it supports 8 connections. I recommend you take a look.

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

2 Replies

Your answer

Follow this Question

Related Questions