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 it's value is given automatically?

| improve this question | | | | |
\$\endgroup\$
  • 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 '13 at 23:30
  • \$\begingroup\$ I think if you read this question and its answer, you wouldn't need to ask this question. \$\endgroup\$ – MichaelHouse♦ Oct 6 '13 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 '13 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\$ – Pieter Geerkens Oct 7 '13 at 22:34
  • \$\begingroup\$ @AdamS: Check out my Hexgrid Utilities library for a sample implementation: hexgridutilities.codeplex.com \$\endgroup\$ – Pieter Geerkens Oct 7 '13 at 22:36
5
\$\begingroup\$

Firstly I would suggest looking at some general A* information and A* tutorials, e.g.:
http://en.wikipedia.org/wiki/A*_search_algorithm
http://www.policyalmanac.org/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.

| improve this answer | | | | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.