Dijkstra's Algorithm Ineffeciencies on a Hex Grid, C#, Unity3D

Question

I'm attempting to create a turn based strategy game using a 3D HexGrid map, I've implemented dijkstra's algorithm but it doesn't run 100% efficiently and I can't work out why. I also attempted to implement A* but have had to stop as I can't work out how to properly implement it, so any help with that would also be massively appreciated.

My unit passes it's GameObject and the Vector3 of it's target to the generate path function and each Node in the graph list is populated with its x,y,z and all of it's neighbors.

The inefficiencies are such that when moving; in a -X direction when on an odd Z plane or in a +X when on an even Z plane, an extra step is made, shown in the screenshots. Another Inefficiency is that when moving in the Z plane an extra step is often taken as the code seems to prefer keeping it's X value the same for as long as possible before approaching on the Z plane. This is leading to the unit being 1 tile further from the goal when it starts it's Z movement than it would have been has it moved 1 X negatively to start with.

I'll add my path generation code, neighbor generation code and my node class code as well as screenshots of where the inefficiencies are occurring as I know my explanations are unclear at best. The neighbor code ensures that the highest adjacent tile is the one stored as the neighbor (it also has to search through types as i have a variety of tile types.

Thank you so much in advance, to anyone that might be able to offer some help or insight in to what is going wrong.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEditor;
using System.IO;
using System;
using System.Linq;

public class UnitMasterScript : MonoBehaviour {

//  private int Number_of_neighbours = 6;
private int Number_of_neighbours = 6;
private GameObject[] Neighbours;
Node[,,] graph;

public bool MapMakerDone = false;

void Update()
{
    if (MapMakerDone == true)
    {
        // Wait for MapMaker to change MapMakerDone to true then allow rest of script to run

        GameObject Map = GameObject.Find("MapMaker");
        int WidthVal = Map.GetComponent<MapMakerFromFile>().WidthVal;
        int HeightVal = Map.GetComponent<MapMakerFromFile>().HeightVal;
        int DepthVal = Map.GetComponent<MapMakerFromFile>().DepthVal;

        // Graph of node generation code
        // Code to find which hex is to each side of this hex
        // Need to find hex to left, right, ul, ur, ll, lr
        // Need to find hex at the top of the stack adjacent
        // 0:L 1:R 2:UL 3:UR 4:LL 5:LR
        graph = new Node[WidthVal, HeightVal, DepthVal];

        for (int x = 0; x < WidthVal; x++)
        {
            for (int y = 0; y < HeightVal; y++)
            {
                for (int z = 0; z < DepthVal; z++)
                {
                    graph[x, y, z] = new Node();

                    graph[x, y, z].x = x;
                    graph[x, y, z].y = y;
                    graph[x, y, z].z = z;
                }
            }
        }

        for (int x = 0; x < WidthVal; x++)
        {
            for (int y = 0; y < HeightVal; y++)
            {
                for (int z = 0; z < DepthVal; z++)
                {

                    // Set up the x and y for the neighbour as the source so it can be used
                    int neighbourX = x;
                    int neighbourY = 0; // must always start from 0 to ensure a downstep isn't missed
                    int neighbourZ = z;
                    int neighbourType = 0;
                    int correct_type = 0;

                    GameObject Hex_Present_checker = null;
                    // First needs to check if there even is a tile at this coordinate location
                    for (neighbourType = 0; neighbourType < 5; neighbourType++)
                    {
                        Hex_Present_checker = GameObject.Find("Hex_" + x + "_" + y + "_" + z + "_" + neighbourType);
                        if (Hex_Present_checker != null)
                        {
                            correct_type = neighbourType;
                        }
                        Hex_Present_checker = null;
                    }

                    if (correct_type != 0)
                    {
                        neighbourType = correct_type;
                        // int Number_of_neighbours = 6;
                        // GameObject[] Neighbours;
                        Neighbours = new GameObject[Number_of_neighbours];

                        // For each value of each tile in neighbours find what the tile coordinates are in XYZ 
                        for (int q = 0; q < Number_of_neighbours; q++)
                        {
                            // Finds X and Z values of the neighbours
                            if (q < 2)
                            {
                                if (q == 0) { neighbourX = x + 1; }
                                if (q == 1) { neighbourX = x - 1; }
                            }
                            if (z % 2 == 1)
                            {
                                if (q == 2) { neighbourX = x; neighbourZ = z + 1; }
                                if (q == 3) { neighbourX = x + 1; neighbourZ = z + 1; }
                                if (q == 4) { neighbourX = x; neighbourZ = z - 1; }
                                if (q == 5) { neighbourX = x + 1; neighbourZ = z - 1; }
                            }
                            else
                            {
                                if (q == 2) { neighbourX = x - 1; neighbourZ = z + 1; }
                                if (q == 3) { neighbourX = x; neighbourZ = z + 1; }
                                if (q == 4) { neighbourX = x - 1; neighbourZ = z - 1; }
                                if (q == 5) { neighbourX = x; neighbourZ = z - 1; }
                            }
                            // Checks for the highest tile for the XZ coordinate and gets its Y value
                            GameObject potential_highest_ring;
                            int highest_Y = 0;
                            int correct_neighbour_type = 0;
                            for (neighbourY = 0; neighbourY < HeightVal; neighbourY++)
                            {
                                for (neighbourType = 0; neighbourType < 5; neighbourType++)
                                {
                                    potential_highest_ring = null;
                                    potential_highest_ring = GameObject.Find("Hex_" + neighbourX + "_" + neighbourY + "_" + neighbourZ + "_" + neighbourType);
                                    if (potential_highest_ring != null)
                                    {
                                        highest_Y = neighbourY;
                                        correct_neighbour_type = neighbourType;
                                    }
                                }
                            }
                            // Need to check if there is a neighbour at the given coordinates
                            // Debug.Log("Hex_" + neighbourX + "_" + highest_Y + "_" + neighbourZ + "_" + neighbourType);
                            Neighbours[q] = GameObject.Find("Hex_" + neighbourX + "_" + highest_Y + "_" + neighbourZ + "_" + correct_neighbour_type);
                            // While there is a neighbour in the neighbours array
                            // add it's coordinates to the graph node as a part of its neighbours sublist
                            if (Neighbours[q] != null)
                            {
                                graph[x, y, z].neighbours.Add(graph[neighbourX, highest_Y, neighbourZ]);
                            }
                        }
                    }
                }
            }
        }
        MapMakerDone = false;
    }
}

// List<Node> currentPath = null;


public List<Node> GeneratePathTo(GameObject SelectedUnit, Vector3 targetVec)
{
    // Dijkstra's Algorithm Implementation
    Dictionary<Node, float> dist = new Dictionary<Node, float>();
    Dictionary<Node, Node> prev = new Dictionary<Node, Node>();

    List<Node> unvisited = new List<Node>();


    Node source = graph[
        SelectedUnit.GetComponent<UnitBasicScript>().HexX,
        SelectedUnit.GetComponent<UnitBasicScript>().HexY,
        SelectedUnit.GetComponent<UnitBasicScript>().HexZ];


    // TargetNode float to int conversion
    int targetVecXInt = (int)targetVec.x;
    int targetVecYInt = (int)targetVec.y;
    int targetVecZInt = (int)targetVec.z;
    Node targetNode = graph[
        targetVecXInt,
        targetVecYInt,
        targetVecZInt];

    // Debug.Log(targetVecXInt + "_" + targetVecYInt + "_" + targetVecZInt);


    dist[source] = 0;
    prev[source] = null;


    // Initialise everything to have infinity distance since no other 
information available
    // Some nodes might not eb erachable therefore infinity is reasonable
    foreach (Node v in graph)
    {
        if (v != source)
        {
            dist[v] = Mathf.Infinity;
            prev[v] = null;
        }

        unvisited.Add(v);
    }

    while (unvisited.Count > 0)
    {
        // u is unvisited node with shortest distance
        Node u = null;
        foreach (Node possibleU in unvisited)
        {
            if (u == null || dist[possibleU] < dist[u])
            {
                u = possibleU;
            }
        }

        unvisited.Remove(u);


        if (u == targetNode)
        {
            break;
        }


        foreach (Node v in u.neighbours)
        {
            float alt = dist[u] + u.Distanceto(v);
            if (alt < dist[v])
            {
                dist[v] = alt;
                prev[v] = u;
            }
        }
    }

    if (prev[targetNode] == null)
    {
        // No route to target
        return null;
    }

    List<Node> currentPath = new List<Node>();

    Node curr = targetNode;

    while (prev[curr] != null)
    {
        currentPath.Add(curr);
        curr = prev[curr];
    }

    currentPath.Reverse();
    return currentPath;
} // End of generate path function

public class Node
{

    public int x = 0;
    public int y = 0;
    public int z = 0;

    public List<Node> neighbours;

    public Node()
    {
        neighbours = new List<Node>();
    }

    public float Distanceto(Node n)
    {
        if (n == null)
        {
            Debug.Log("Error");
        }

        return Vector2.Distance(
            new Vector3(x, y, z),
            new Vector3(n.x, n.y, n.z));
    }
}
}

That concludes the code, I understand everything within monobehaviour has to be indented and it is in my code but upon copying into stackoverflow it lost that indentation. Next are the pictures showing the incorrect paths the units take.

https://i.sstatic.net/Flu9L.jpg

If any other information is needed please let me know and I will be more than happy to provide it. Thank you so much again!

Answer 1

Despite all the glaring inefficiencies which i still haven't resolved, I have resolved the problems with the algorithm implementation. I was getting the distance between the tile grid coordinates which didn't take into account that on a hex grid a diagonal movement has the exact same distance cost as a horizontal movement. Therefore the solution was to get the distance once the node grid coordinates had been converted to world coordinates as this will ensure all distances between adjacent tiles are equal.

Hope this helps if anyone gets stuck with the same problem!

Answer 2

You are using a List instead of a priority queue, which is massively inefficient. Also, since your grid has a simple heuristic, you should consider using A* which will be much faster.