13

I'm implementing NxN puzzels in Java 2D array int[][] state. am required to use the Manhattan heuristic in the following way: 

             the sum of the vertical and horizontal distances from 
                the current node to the goal node/tile

                                +(plus)

    the number of moves to reach the goal node from the initial position

At the moment I don't know how to go further. Am a beginner in puzzle game programming with 2D arrays so am having trouble to understand certain concepts. How can I write this code in Java?

halfer
  • 19,824
  • 17
  • 99
  • 186
Eddy Freeman
  • 3,207
  • 6
  • 35
  • 55

1 Answers1

55

This is more a math question, but anyways the Manhattan distance is the sum of the absolute values of the horizontal and the vertical distance

int distance = Math.abs(x1-x0) + Math.abs(y1-y0);

More info: http://en.wikipedia.org/wiki/Taxicab_geometry

Otto Allmendinger
  • 27,448
  • 7
  • 68
  • 79
  • thanks for your reply. Is that all i need to calculate the horizontal and vertical distances? Am a beginner so need help. I thought maybe i have to move from tile to tile and add 1 each time to the accumulated cost. – Eddy Freeman Nov 22 '11 at 09:30
  • The code I gave is just for the plain Manhattan distance - if I understand the puzzle correctly you have to add the number of moves to that. – Otto Allmendinger Nov 22 '11 at 09:36
  • 1
    Eddy: yes, because the mahattan distance is the same, regardless which "street" do you take to get there. – malejpavouk Nov 22 '11 at 09:38
  • For some reason, when I did my AI class, I was under the impression that Manhattan distance was Euclidian distance squared (as in to save a sqrt) Thank you for saving my students a few points – 3Doubloons Nov 23 '11 at 04:39