c# - Dijkstra's Algorithm Ineffeciencies on a Hex Grid, C#, Unity3D
问题描述
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.
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!
解决方案
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.
推荐阅读
- redis - 如果一个主节点只有一个从节点,是否有替代方案可以跳过 Redis 集群中从节点的选举过程?
- html - SVG路径中的工具提示在纯html中工作时不起作用
- java - 在调用操作 api 时获得 403-PERMISSION_DENIED
- spring - 如何访问 org.quartz.Job 类中的应用程序属性?
- android - 使用 Retrofit 获取 Json 中的数据
- objective-c - 如何在微软认知语音库中使用objective-c将OutputFormat.simple设置为OutputFormat.detailed?
- angular - 当从 Angular 4 更改为 Angular 7
- apache-spark - Apache Spark:对流数据集进行连接操作后更新输出模式
- java - 如何在 docker compose 中配置 logstash?
- asp.net-mvc - 在我的情况下实现多个模型的正确方法是什么?