0
\$\begingroup\$

We have a formula of f=g+h wherein g is the path cost and h is the distance left to the goal.

Given that I only want to move my unit in 4 direction (N,S,E,W), my question is:

Can we consider h as an input? Because we will choose what heuristic to use? Or not because its value is given automatically?

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'm not sure what exactly you want to know, but the heuristic is constant for all nodes and h's value will be the result of the applied heuristic. f(expected total cost) = g(real cost from begin to node) + h(expected cost from node to end). \$\endgroup\$
    – Appleshell
    Oct 6, 2013 at 23:30
  • \$\begingroup\$ I think if you read this question and its answer, you wouldn't need to ask this question. \$\endgroup\$
    – House
    Oct 6, 2013 at 23:41
  • \$\begingroup\$ This is well tread ground as others have mentioned, but: -The heuristic will be dependent on the application -The path cost would be a derived input, from the inputs current location and goal. \$\endgroup\$
    – Kirbinator
    Oct 7, 2013 at 3:36
  • 1
    \$\begingroup\$ @AdamS: No, the heuristic function is not necessarily constant for all nodes (That is merely a common and simple implementation choice). When executing a ALT implementation, the heuristic is the difference of the lengths of the pre-computed path from two (or more) landmarks. See here:cs.princeton.edu/courses/archive/spr06/cos423/Handouts/GW05.pdf or search for "A-star with Triangle Inequality and Landmarks". These algorithms can speed-up A-star by 2-3 orders of magnitude, as with on-line mapping software. \$\endgroup\$ Oct 7, 2013 at 22:34
  • \$\begingroup\$ @AdamS: Check out my Hexgrid Utilities library for a sample implementation: hexgridutilities.codeplex.com \$\endgroup\$ Oct 7, 2013 at 22:36

1 Answer 1

6
\$\begingroup\$

Firstly I would suggest looking at some general A* information and A* tutorials, e.g.:
http://en.wikipedia.org/wiki/A*_search_algorithm
https://web.archive.org/web/20171022224528/http://www.policyalmanac.org:80/games/aStarTutorial.htm

Secondly, the h function needs to be some sort of heuristic guess on the remaining distance, for example the Euclidean distance or Manhattan distance. The more accurate the heuristic is, the faster A* will find the optimal solution. However take care not to choose a heuristic that overestimates the remaining distance. This is called an inadmissable heuristic, and is not guaranteed to find the optimal solution. More advanced A* users may intentionally choose an inadmissable heuristic for speed purposes or because the resulting path looks nicer, but leave that until you have a basic implementation working. If you're only moving in 4 directions, the Manhattan distance is a good heuristic.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .