Theory on A* path finding

Unity Engine
1

ok so ive been looking into A* path finding but all of the tutorials that i find seam to only be done on square grids. and therefore i am having trouble when imagining a* on a way-point graph. as i don not know what to uses as heuristic value(estimate distance to target way-point) as in some situation the correct path will mean that the heuristic for some nodes will be worse and therefor be the last choice. below is an example


if A is the start node and g is the target. picking the smallest heuristics would lead to path A,J,I,H before having to back track and use A,B,C,D,E,F,G,
this is not a problem in the example but this could be a big problem in larger maps and could mean that the correct path is the last path out of 100 trial paths

so my question is what should used for the heuristic of a node in 3D games

2

This simply isn’t how A* works. There is no backtracking, and paths are not evaluated one at a time as you suggest.

It makes absolutely no difference whether examples are in a grid pattern or not. The example you provide could exist on a grid just as easily as in waypoints. A* is just an algorithm for searching a graph. The algorithm doesn’t care how you created the grid or what pattern it makes. It just searches the nodes.

Teaching you the A* algorithm is a bit beyond the scope of a forum. I can only suggest that you go back and read those tutorials again until you understand the algorithm. When you do, implement it. It doesn’t care how you create your graphs.

3

that doesn’t realty help all i wanted to know is what to use as the heuristic value,
so again what should used for the heuristic value of a node in three dimentional games

4

While it is true that A* doesn’t trace paths and doesn’t backtrack, I believe that your statement that nodes AJIH will be evaluated before ABCDEFG using distance as heuristic is completely correct.

However, your conclusion that using euclidean distance as heuristic is a bad idea is really only true for your very simplified example (and pretty much only in the case of A->G, on most other situations it works fine).

In fact, if you would make your maze more complex and add several other corridors extending from the current, you will find that most nodes in those new corridors will actually be ignored using this same heuristic.

A heuristic is supposed to be an easy-to-calculate estimation, and estimations make mistakes by definition, so it’s very easy to find examples where they fail. I’d recommend to stick with distance as heuristic, as it may be difficult to find a cheap one that performs better.

5

Sorry, I assumed that telling you that it made no difference whether you were negotiating a grid or a system of waypoints would make it obvious that the heuristic doesn’t need to change. The tutorials may well have other suggestions on how to vary your heuristic for specific purposes, which is why I suggested going back and reading them properly. However, distance between waypoints is a perfectly good place to start.

You’re right. It will be evaluated first (assuming that the diagram is to scale) as the algorithm spreads out from the start point.

6

Yes it would go as per your figure there, however it would not generate too many paths, it would simply incrementally eliminate nodes.

ie if you have 400 nodes it might do 300 before it finds the target, if the maze is quite complex. If it is simple it may only do 200 or less.

You cant really help this unless you try another algorithm. There are a few variations however I doubt there is anything better. And there are mathematics geniuses working on this. Its a area of mathematics, so for us to try and delve into it, I doubt we would make improvements. We should study their solutions first before changing things.

7

This, http://www.policyalmanac.org/games/aStarTutorial.htm + a week or two and you will have a pathfinding system.

8

Heh, that takes me back. That’s the first tutorial on A* that I could ever follow way back when I was just getting started. Patrick Lester had a real knack for making his subject easy-to-follow without leaving out important information.

9

Hi there

this code is NOT perfect but in might help:

Attach it to an empty game object…

also head to

http://blog.blackicegamesnyc.com/?p=58

for a great Unity pathfinding script!!

var c = new Array ();

var openList = new Array ();
var closedList = new Array ();

var startnode : Vector2;
var endnode : Vector2;

class node {
var f : int;
var g : int;
var pos : Vector2;
var cube : GameObject;
}

function Start(){

for (x=0; x<7; x++) {
c[×] = new Array();
for(y=0;y<7;y++){
c[×][y] = new node();
c[×][y].f = 0;
c[×][y].g = 0;
c[×][y].pos = Vector2(x,y);
c[×][y].cube=GameObject.CreatePrimitive(PrimitiveType.Cube);
c[×][y].cube.transform.position = Vector3(x,1,y);
c[×][y].cube.transform.localScale *= 0.5;
c[×][y].cube.name = “cube” + x + y; }
}

startnode = c[0][0].pos;
endnode = c[6][6].pos;

c[4][4].g=10;
c[4][4].cube.renderer.material.color = Color.red;

c[startnode.x][startnode.y].cube.renderer.material.color = Color.green;
c[endnode.x][endnode.y].cube.renderer.material.color = Color.red;

var traceit = search (startnode,endnode);

for (var xx=0;xx<traceit.length;xx++){
traceit[xx].cube.renderer.material.color = Color.green;}

}

function Update () {

}

function search (snode,enode) {

openList.Push(c[snode.x][snode.y]);
var currentNode = snode;

var lowInd = 0;

while(currentNode != enode ) {

var neighbors = neighbors(currentNode);

for(var n=0; n<neighbors.length;n++) {
var neighbor = neighbors[n];

for(var ccl=0; ccl<closedList.length;ccl++) {
if (neighbor.cube.name == closedList[ccl].cube.name){
continue;}
}

for(var opl=0; opl<closedList.length;opl++) {
if (neighbor.cube.name == openList[opl].cube.name){
continue;}
}

//if (neighbor.g==10){
//continue;}

neighbor.f = 10 + heuristic(neighbor.pos, enode);

openList.Push(neighbor);

}

for(var i=0; i<openList.length; i++) {
if(openList*.f <openList[lowInd].f) { lowInd = i; }*

}

Debug.Log(openList);

currentNode = openList[lowInd];

closedList.Push(currentNode);

currentNode = openList[lowInd].pos;

openList.RemoveAt(lowInd);

}

return closedList;

}
function neighbors (noder) {
var dir = new Array(0,-1,10,1,-1,14,1,0,10,1,1,14,0,1,10,-1,1,14,-1,0,10,-1,-1,14,0,-1,10,1,-1,14,1,0,10);
var ret = new Array();

var x = noder.x;
var y = noder.y;

var sd = 0;
var ed = 21;

if (x==0){
sd=6;
ed=18;}

if(y==0){
sd=0;
ed=12;}

if(x==7){
sd=12;
ed=24;}

if(y==7){
sd=18;
ed=30;}

if(x==0 y==0){
sd=6; ed=12;}

if(x==7 y==7){
sd=18; ed=24;}
for (var d=sd; d<ed; d+=3) {
ret.Push(c[x+dir[d]][y+dir[d+1]]);}

return ret;
}

function heuristic (pos0, pos1) {
//This is the Manhattan distance
var d1 = Mathf.Abs(pos1.x - pos0.x);
var d2 = Mathf.Abs(pos1.y - pos0.y);
return d1 + d2;
}