koobas.hobune.stream
Pathfinding sometimes takes wrong path
So I made this pathfinding script that can walk around walls. Problem is that it can get in a situation where 2 tiles/nodes are equally close to the target position and the path makes a little circle before going to the target and in more narrow situations might not be able to get to target at all.
btw. the path cant move diagonally. This is on purpose. Here are some pictures to help explain. (Start is green tile and target is red tile)
In the first picture the path is optimal but in the second it isnt due to the path going left when it hits the wall. 
Heres my script (test code. sorry for mess):
public Transform target;
public Vector3[] rayOrigin = new Vector3[4];
RaycastHit[] hit = new RaycastHit[4];
Transform targetTile;
Transform lastTargetTile;
float oldVal = 1000;
bool targetInRange = false;
public List<Transform> openList = new List<Transform>();
public List<Transform> closedList = new List<Transform>();
void Start ()
{
lastTargetTile = transform;
openList.Add(transform);
StartCoroutine(CoTest());
}
IEnumerator CoTest()
{
while(!targetInRange)
{
FindNearestNodes();
yield return new WaitForSeconds(0.5f);
}
}
void FindNearestNodes()
{
rayOrigin[0] = lastTargetTile.position + lastTargetTile.forward + lastTargetTile.up;
rayOrigin[1] = lastTargetTile.position + lastTargetTile.right + lastTargetTile.up;
rayOrigin[2] = lastTargetTile.position - lastTargetTile.forward + lastTargetTile.up;
rayOrigin[3] = lastTargetTile.position - lastTargetTile.right + lastTargetTile.up;
for (int i = 0; i < 4; i++)
{
Debug.DrawRay(rayOrigin[i], Vector3.down, Color.red);
if (Physics.Raycast(rayOrigin[i], Vector3.down, out hit[i], 2))
{
if (hit[i].transform.CompareTag("Tile"))
{
openList.Add(hit[i].transform);
}
else if (hit[i].transform == target)
{
targetInRange = true;
}
}
}
if(!targetInRange)
ChooseTargetNode();
}
void ChooseTargetNode()
{
Transform[] tempArray = openList.ToArray();
for (int i = 0; i < tempArray.Length; i++)
{
float dist = Vector3.Distance(target.position, tempArray[i].position);
if (dist < oldVal)
{
targetTile = tempArray[i];
oldVal = dist;
}
}
ChangeColor(Color.yellow, targetTile.GetComponent<MeshRenderer>());
oldVal = 1000;
closedList.Add(targetTile);
targetTile.tag = "Untagged";
openList.Clear();
lastTargetTile = targetTile;
targetTile = null;
}
void ChangeColor(Color c, MeshRenderer meshrenderer)
{
meshrenderer.material.color = c;
}
In your solution your missing a few key ingredients.
http://www.redblobgames.com/pathfinding/a-star/introduction.html
Take a look at the following link.
Its to a simple and very easily implementable tutorial on how to develop an A* pathfinding algorithm.
You can even stop short of going the full A* route and just use a floodfill search if your graph isnt massive.
Thanks. That was a great introduction and exactly what I needed.
Incase anyone stumbles upon this post in the future I'll just post my script here. NOTE: This is not super optimized or anything but it works for what I need it for.
Tile script:
public bool visited = false;
public Transform cameFrom;
Actual pathfinding script: public Transform target; public Transform lastTile; public Vector3[] rayOrigin = new Vector3[4]; RaycastHit[] hit = new RaycastHit[4]; float oldVal = 1000; bool targetInRange = false; bool done = false; public int i; public float time;
public List<Transform> openList = new List<Transform>();
public List<Transform> closedList = new List<Transform>();
void Start ()
{
openList.Add(transform);
StartCoroutine(CoTest());
}
IEnumerator CoTest()
{
while(!targetInRange)
{
FindNearestNodes(openList[i]);
i++;
}
while (!done)
{
if (lastTile == transform)
{
done = true;
}
else
{
Tile tileScript = lastTile.GetComponent<Tile>();
closedList.Add(tileScript.cameFrom);
ChangeColor(Color.green, lastTile.GetComponent<MeshRenderer>());
lastTile = tileScript.cameFrom;
}
}
yield return null;
}
void FindNearestNodes(Transform tile)
{
rayOrigin[0] = tile.position + tile.forward + tile.up;
rayOrigin[1] = tile.position + tile.right + tile.up;
rayOrigin[2] = tile.position - tile.forward + tile.up;
rayOrigin[3] = tile.position - tile.right + tile.up;
for (int i = 0; i < 4; i++)
{
Debug.DrawRay(rayOrigin[i], Vector3.down, Color.red);
if (Physics.Raycast(rayOrigin[i], Vector3.down, out hit[i], 2))
{
if (hit[i].transform.CompareTag("Tile"))
{
if (hit[i].transform.GetComponent<Tile>().visited == false)
{
openList.Add(hit[i].transform);
ChangeColor(Color.yellow, hit[i].transform.GetComponent<MeshRenderer>());
Tile tileScript = hit[i].transform.GetComponent<Tile>();
tileScript.visited = true;
tileScript.cameFrom = tile;
}
}
else if (hit[i].transform == target)
{
lastTile = tile;
closedList.Add(lastTile);
ChangeColor(Color.green, lastTile.GetComponent<MeshRenderer>());
targetInRange = true;
}
}
}
}
void ChangeColor(Color c, MeshRenderer meshrenderer)
{
meshrenderer.material.color = c;
}
