Unity A* поиск пути с использованием путевых точек
Я пытаюсь создать алгоритм поиска пути A*, используя путевые точки, которые я сгенерировал, используя отдельный скрипт на моей местности. Проходные и необратимые путевые точки на местности определяются их цветом - зеленый - проходимый.
Расположение узлов можно увидеть по ссылке: 
Проходные путевые точки хранятся в списке.
Чтобы начать поиск пути, я создал словарь, в котором каждая пройденная путевая точка хранится в виде уникального ключа (type = gameobject). Значения каждого ключа были его соседями (тип = список), рассчитанными с использованием функции расстояния.
Затем я попытался создать алгоритм A*, используя онлайн-ссылки и адаптируя их к моей ситуации. Комментарии к каждой части можно увидеть в моем коде ниже. Функция findPath является фактическим алгоритмом (ну, моя лучшая попытка это сделать).
void findPath()
{
// Adds start node to open list
// take nodes around start node and add to lista*
open.Add(startNode);
while (open.Count > 0)
{
nodeDistances = 1000;
foreach (GameObject node in open)
{
GCost = Vector3.Distance(startNode.transform.position, node.transform.position);// G distance form node to start
HCost = Vector3.Distance(targetNode.transform.position, node.transform.position); // H distance from node to target
FCost = GCost + HCost;
if (FCost < nodeDistances) // if current node has smaller F cost than the node before that
{
tempGCost = GCost; // Gets the lowest G cost
tempFCost = FCost;
current = node; // Replaces Game Object variable
nodeDistances = FCost;
}
}
if (current.transform.position == targetNode.transform.position)
{
Debug.Log("Goal reached");
break;
}
open.Remove(current);
closed.Add(current);
neighbours = attachedToWaypoint[current];
// path.Add(current);
foreach (GameObject n in neighbours)
{
if (!closed.Contains(n))
{
float g_score = tempGCost + 1; // Takes current node GCost and adds value of 1 for each neighbour
float h_score = Vector3.Distance(n.transform.position, targetNode.transform.position); // Gets distance from each neighbour to the target node
float f_score = g_score + h_score;
if (closed.Contains(n) && f_score >= tempFCost) // If F cost of neighbour is greater than F cost of current node
continue;
if (!open.Contains(n) || f_score < tempFCost) // If 'open' list does not currently contain neighbour or neighbours F score is smaller than that of the current node
{
GCost = g_score;
HCost = h_score;
tempFCost = GCost + HCost; // update current node F score value to get neighbour with the smallest F score
if (!open.Contains(n))
{
open.Add(n); // if neihgbour is not in open list, add to open list
}
}
}
}
}
}
Однако, глядя на узлы, хранящиеся в закрытом списке, видно, что что-то идет не так - выбор узлов в закрытом списке: https://imgur.com/5cF7voO
Может кто-то с большим опытом, пожалуйста, дайте мне несколько советов, на каком аспекте я должен сосредоточиться? Кроме того, как бы вы использовали это, чтобы найти самый дешевый путь?
Любая помощь будет чрезвычайно ценится.
Спасибо кальвин
Полный скрипт ниже:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class TEST : MonoBehaviour
{
Dictionary<GameObject, List<GameObject>> attachedToWaypoint = new Dictionary<GameObject, List<GameObject>>();
List<GameObject> gameObjectForDic = new List<GameObject>();
GameObject[] waypoints;
List<List<GameObject>> nodeData = new List<List<GameObject>>();
List<GameObject> neighbours = new List<GameObject>(); // Not currently used
public GameObject enemy;
public GameObject player;
GameObject startNode;
GameObject targetNode;
List<GameObject> open = new List<GameObject>();
List<GameObject> closed = new List<GameObject>();
float distanceToEnemy;
float distanceToPlayer;
float tempFCost;
float FCost;
float GCost;
float HCost;
float tempGCost;
float accumulatedCost;
float accumulatedCostTemp;
float nodeDistances;
GameObject current;
public GameObject parent;
List<GameObject> path = new List<GameObject>();
// Use this for initialization
void Start()
{
distanceToEnemy = 1000;
distanceToPlayer = 1000;
nodeDistances = 10000;
waypoints = GameObject.FindGameObjectsWithTag("Waypoint");
storeNodesInDictionary();
findPath();
// findPathtoPlayer();
testing();
}
void storeNodesInDictionary()
{
for (int i = 0; i < waypoints.Length; i++)
{
nodeData.Add(new List<GameObject>());
float distEnemy = Vector3.Distance(enemy.transform.position, waypoints[i].transform.position); // Closest node to enemy
if (distEnemy < distanceToEnemy)
{
startNode = waypoints[i];
distanceToEnemy = distEnemy;
}
float distPlayer = Vector3.Distance(player.transform.position, waypoints[i].transform.position);// Closest node to player
if (distPlayer < distanceToPlayer)
{
targetNode = waypoints[i];
distanceToPlayer = distPlayer;
}
for (int j = 0; j < waypoints.Length; j++)
{
float distanceSqr = (waypoints[i].transform.position - waypoints[j].transform.position).sqrMagnitude; // Gets distance values
if (distanceSqr < 60 && waypoints[i] != waypoints[j]) // Is waypoints are within a spcific distance
{
nodeData[i].Add(waypoints[j]);
}
}
attachedToWaypoint.Add(waypoints[i], nodeData[i]); // Adds parent node and neighbouring nodes within a 3x3 grid
}
}
void findPath()
{
// Adds start node to open list
// take nodes around start node and add to lista*
open.Add(startNode);
while (open.Count > 0)
{
nodeDistances = 1000;
foreach (GameObject node in open)
{
GCost = Vector3.Distance(startNode.transform.position, node.transform.position);// G distance form node to start
HCost = Vector3.Distance(targetNode.transform.position, node.transform.position); // H distance from node to target
FCost = GCost + HCost;
if (FCost < nodeDistances) // if current node has smaller F cost than the node before that
{
tempGCost = GCost; // Gets the lowest G cost
tempFCost = FCost;
current = node; // Replaces Game Object variable
nodeDistances = FCost;
}
}
if (current.transform.position == targetNode.transform.position)
{
Debug.Log("Goal reached");
break;
}
open.Remove(current);
closed.Add(current);
neighbours = attachedToWaypoint[current];
// path.Add(current);
foreach (GameObject n in neighbours)
{
if (!closed.Contains(n))
{
float g_score = tempGCost + 1; // Takes current node GCost and adds value of 1 for each neighbour
float h_score = Vector3.Distance(n.transform.position, targetNode.transform.position); // Gets distance from each neighbour to the target node
float f_score = g_score + h_score;
if (closed.Contains(n) && f_score >= tempFCost) // If F cost of neighbour is greater than F cost of current node
continue;
if (!open.Contains(n) || f_score < tempFCost) // If 'open' list does not currently contain neighbour or neighbours F score is smaller than that of the current node
{
GCost = g_score;
HCost = h_score;
tempFCost = GCost + HCost; // update current node F score value to get neighbour with the smallest F score
if (!open.Contains(n))
{
open.Add(n); // if neihgbour is not in open list, add to open list
}
}
}
}
}
}
}
1 ответ
Несколько предложений:
Хорошая структура данных для Closed это HashSet, это определенно ускорит ваш код и не требует особых изменений.
К сожалению, правильная структура данных для Open является приоритетной очередью, но в C# она не встроена; если вы хорошо используете стороннюю реализацию, которая даст вам наилучшую производительность, стоимость f будет вашим приоритетом. В противном случае вам нужно будет написать свой собственный.
Что касается вашей закрытой картинки, она выглядит неплохо, но из того, что я смог выяснить, ошибка может быть следующей:
GCost = Vector3.Distance(startNode.transform.position, node.transform.position); // G distance from node to start
Предполагается, что стоимость g является фактическим расстоянием, которое нужно пройти от startNode до узла, но вы используете ту же функцию для вычисления g, которую используете для вычисления h. Это все равно, что использовать две прямые линии все время, если вы представляете, как это будет пытаться пройти по зигзагообразной траектории с обходом прямой траектории прямо рядом с ней, то все время будет идти по зигзагообразной траектории, думая, что идет прямо. от начального узла до текущего узла.
Ниже приведено то, что я сделал с кодом во время исследования, вы можете делать с ним все, что захотите.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Some.Namespace.That.Gets.PriorityQueue;
public class TEST: MonoBehaviour {
Dictionary<GameObject, List<GameObject>> attachedToWaypoint = new Dictionary<GameObject, List<GameObject>>();
GameObject[] waypoints;
GameObject startNode;
GameObject targetNode;
GameObject current;
PriorityQueue<float, GameObject> open = new PriorityQueue<float, GameObject>();
HashSet<GameObject> closed = new HashSet<GameObject>();
List<GameObject> path = new List<GameObject>();
float distanceToEnemy;
float distanceToPlayer;
float FCost;
float GCost;
float HCost;
float nodeDistances;
public GameObject enemy;
public GameObject player;
public GameObject parent;
// Use this for initialization
void Start() {
distanceToEnemy = 1000;
distanceToPlayer = 1000;
nodeDistances = 10000;
waypoints = GameObject.FindGameObjectsWithTag("Waypoint");
storeNodesInDictionary();
findPath();
// findPathtoPlayer();
testing();
}
void storeNodesInDictionary() {
for (int i = 0; i < waypoints.Length; i++) {
var waypoint = waypoints[i];
var nodeData = new List<GameObject>();
var waypointPosition = waypoint.transform.position;
float distEnemy = Vector3.Distance(enemy.transform.position, waypointPosition); // Closest node to enemy
if (distEnemy < distanceToEnemy) {
startNode = waypoint;
distanceToEnemy = distEnemy;
}
float distPlayer = Vector3.Distance(player.transform.position, waypointPosition); // Closest node to player
if (distPlayer < distanceToPlayer) {
targetNode = waypoint;
distanceToPlayer = distPlayer;
}
for (int j = 0; j < waypoints.Length; j++) {
if (i == j)
continue;
var otherWaypoint = waypoints[j];
float distanceSqr = (waypointPosition - otherWaypoint.transform.position).sqrMagnitude; // Gets distance values
if (distanceSqr < 60) // Is waypoints are within a spcific distance
{
nodeData.Add(otherWaypoint);
}
}
attachedToWaypoint.Add(waypoint, nodeData); // Adds parent node and neighbouring nodes within a 3x3 grid
}
}
void findPath() {
var startPosition = startNode.transform.position;
var targetPosition = targetNode.transform.position;
open.Push(Vector3.Distance(startPosition, targetPosition), startNode);
while (open.Count > 0) {
FCost = open.Pop(out current);
var currentPosition = current.transform.position;
if (currentPosition == targetPosition) {
Debug.Log("Goal reached");
break;
}
HCost = Vector3.Distance(currentPosition, targetPosition);
GCost = FCost - HCost;
closed.Add(current);
var neighbours = attachedToWaypoint[current];
// path.Add(current);
foreach(GameObject n in neighbours) {
if (!closed.Contains(n) && !open.Contains(n)) // If 'open' list does not currently contain neighbour or neighbours F score is smaller than that of the current node
{
var neighbourPosition = n.transform.position;
var neighbourFCost = GCost + Vector3.Distance(currentPosition, neighbourPosition) + Vector3.Distance(neighbourPosition, targetPosition)
open.Push(neighbourFCost, n); // if neighbour is not in open list, add to open list
}
}
}
}
}