2
\$\begingroup\$

anyone can share a link for a tutorial or article about optimizing A* for horizontal / vertical movement (no diagonal). Is not as easy as change the G values to 10 everytime.

Thanks

\$\endgroup\$
8
\$\begingroup\$

A* is a graph search; the algorithm doesn't know or care whether you're searching a grid (with or without permissible diagonal movement) or a free-form graph. To "optimize" for the case where diagonal movement isn't allowed, make sure to never return diagonally-adjacent nodes when computing the neighbors of the current node. Between that and selecting an appropriate heuristic for your scenario, there's little in the way of optimizations available specifically for the 4-directional grid case (as far as I'm aware).

\$\endgroup\$
4
  • \$\begingroup\$ That's what I have done already, but still the score is strange. For example, I get the same F score for every node. \$\endgroup\$
    – Veehmot
    Jul 26 '11 at 3:53
  • 3
    \$\begingroup\$ That sounds more like a bug in your implementation. Perhaps you should post another question asking for help with your code? \$\endgroup\$
    – user1430
    Jul 26 '11 at 5:06
  • \$\begingroup\$ Nevermind, it is an issue of A* itself. I found the answer here theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12 \$\endgroup\$
    – Veehmot
    Jul 26 '11 at 5:16
  • 1
    \$\begingroup\$ @Veehmot If you have found a solution, please post it as an answer and Accept it. \$\endgroup\$
    – Jesse Dorsey
    Jul 26 '11 at 16:40
0
\$\begingroup\$

I found the info needed here: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S7

\$\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.