Quote:
Originally Posted by stefanhendriks
i dunno about dijkstra exactly. I thought that was by bi-directional searching? Or am i messing stuff up now?
A* always has an heuristic, if it does not have one, it would not create a path at all. So i guess a 'non heuristic' one is meant to be 'find the best node thats gets closer to goal'...
|
No, Aspirin is right ; basically all searching algorithms can be bidirectional if you want, but it is right to say that A* is a directed Dijkstra. The direction influence is provided by the heuristic function.
Having no heuristic function (or a heuristic function that returns the same value for every node evaluated) will make the algorithm not directed at all, and so it will expand in all directions.
A* can have no heuristic ; in this case the algorithm is exactly Dijkstra's (after simplification). Actually I'm starting to wonder if Count Floyd did really write all this A* function himself, because it's really well thought of. If he did, kudos! It's rather a generic-purpose A* template. You can pass as arguments to this function pointers to the addresses of the functions that you want it to use to compute the cost, to evaluate the heuristic, and to determine if the goal is reached or not. It's really polyvalent. But in his implementation, Count Floyd was always calling his A* function with a pointer to a heuristic function that was returning 0 for every node evaluated.
Look at his prototype:
Code:
PATHNODE *AStarSearch (PATHNODE *root, int (*gcalc) (PATHNODE *), int (*hcalc) (PATHNODE *),
int (*goalNode) (PATHNODE *), PATHNODE * (*children) (PATHNODE *),
int (*nodeEqual) (PATHNODE *, PATHNODE *));
gcalc(), hcalc(), goalNode(), children() and nodeEqual() are pointers to functions. Really nice, isn't it ? Although from a strict performance point of view I'm not sure it's very computationally efficient.
The heuristic function he was always passing as hcalc(), was this function:
Code:
// No heurist (greedy) !!
int hfunctionNone (PATHNODE *p)
{
if (p == NULL)
return (65355);
return (0);
}
so I added mine:
Code:
// Square Distance Heuristic
int hfunctionSquareDist (PATHNODE *p)
{
int deltaX = abs ((int) paths[g_iSearchGoalIndex]->origin.x - (int) paths[p->iIndex]->origin.x);
int deltaY = abs ((int) paths[g_iSearchGoalIndex]->origin.y - (int) paths[p->iIndex]->origin.y);
int deltaZ = abs ((int) paths[g_iSearchGoalIndex]->origin.z - (int) paths[p->iIndex]->origin.z);
return (deltaX + deltaY + deltaZ);
}