koobas.hobune.stream
A* problem with path
hello everyone, I have a problem with the A * algorithm (astar). It 'the first time you try to implement. From how I'm doing, the algorithm does not always find the shortest path. The figure I am attaching, the algorithm should follow the green line instead follows the blue line and then to your destination takes nodes that do not serve. Someone can help me?
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace blablabla
{
[System.Serializable]
public class Node
{
public float G { get; set; }
public float H { get; set; }
public float F { get { return this.G + this.H; } }
public bool isWalkable { get; set; }
public Vector3 position { get; set; }
public GameObject floor;
public int current { get; set; }
}
public class GenerateCell : MonoBehaviour
{
private List<Node> nodes;
[SerializeField]
private GameObject floor;
private Vector3 startPosition;
[SerializeField]
private int xSize;
[SerializeField]
private int ySize;
private List<GameObject> allCell;
private List<Node> openList;
private List<Node> closedList;
private List<Node> neighboringNode;
[SerializeField]
private int range;
[SerializeField]
private GameObject wall;
[SerializeField]
List<Node> adjacentNodes;
public Node startNode, currentNode;
void Awake()
{
startPosition = new Vector3(0f, 0f, 0f);
allCell = new List<GameObject>();
nodes = new List<Node>();
openList = new List<Node>();
closedList = new List<Node>();
neighboringNode = new List<Node>();
adjacentNodes = new List<Node>();
createFloor();
createNode();
createWall();
}
void createFloor()
{
for (int i = 0; i < xSize; i++)
{
for (int j = 0; j < ySize; j++)
{
GameObject instantiate = Instantiate(floor, new Vector3(i, 0f, j), Quaternion.Euler(90f, 0f, 0f)) as GameObject;
instantiate.name = ((i * xSize) + j).ToString();
allCell.Add(instantiate);
}
}
}
void createWall()
{
for (int i = 0; i < nodes.Count; i++)
{
if (nodes[i].isWalkable == false)
Instantiate(wall,
new Vector3(nodes[i].position.x, nodes[i].position.y + 0.5F, nodes[i].position.z),
Quaternion.identity);
}
}
void createNode()
{
for (int i = 0; i < xSize * ySize; i++)
{
nodes.Add(new Node());
nodes[i].floor = allCell[i];
nodes[i].position = allCell[i].transform.position;
nodes[i].current = i;
nodes[i].isWalkable = true;
}
nodes[11].isWalkable = false;
nodes[12].isWalkable = false;
nodes[13].isWalkable = false;
nodes[14].isWalkable = false;
pathFind(nodes[4], nodes[22]);
debug();
}
float setG(Node starPosition, Node currentNode)
{
float valueG = heuristic(starPosition, currentNode);
return valueG;
}
float setH(Node currentNode, Node endNode)
{
float valueH = heuristic(currentNode, endNode);
return valueH;
}
float heuristic(Node firstNode, Node secondNode)
{
float manhattanDistance = Mathf.Abs(secondNode.position.x - firstNode.position.x) + Mathf.Abs(secondNode.position.z - firstNode.position.z);
return manhattanDistance;
}
void findNeighboards(Node currentNode)
{
for (int i = 0; i < nodes.Count; i++)
{
if (Vector3.Distance(currentNode.position, nodes[i].position) == range)
{
if (nodes[i].isWalkable && !closedList.Contains(nodes[i]))
{
adjacentNodes.Add(nodes[i]);
}
}
}
}
void debug()
{
Renderer r;
for (int i = 0; i < closedList.Count; i++)
{
if (closedList[i] != closedList[0])
{
r = closedList[i].floor.GetComponent<Renderer>();
r.material.color = Color.blue;
}
else
{
r = closedList[i].floor.GetComponent<Renderer>();
r.material.color = Color.red;
}
}
}
private void pathFind (Node start, Node end)
{
openList.Add(start);
while(openList.Count != 0)
{
Node currentNode = openList.OrderByDescending(minValue => minValue.F).Last(); // findMin(openList);
openList.Remove(currentNode);
findNeighboards(currentNode);
closedList.Add(currentNode);
if (closedList.Contains(end))
break;
foreach (Node item in adjacentNodes)
{
if (closedList.Contains(item))
continue;
if (!openList.Contains(item))
{
item.G = setG(start, item);
item.H = setH(item, end);
float result = item.F;
openList.Add(item);
}
}
adjacentNodes.Clear();
}
}
}
}
