# A recursive problem?

• 10-31-2005
salman86
A recursive problem?
Hey guys,

I have a 2 dimension 8 by 8 array which is fill with "." and 2 Xs. I need to find the shortest possible path from one X to another X recursivley. Can anyone help me to find the solution please? Thanks in advance. Here is the array which i've:

Code:

```char grid[][8] = {             {'.','.','.','.','.','.','.','.'},             {'.','.','.','.','.','.','.','.'},             {'.','.','.','.','.','.','.','.'},             {'.','.','.','X','.','.','.','.'},             {'.','.','.','.','.','.','.','.'},             {'.','.','.','.','.','X','.','.'},             {'.','.','.','.','.','.','.','.'},             {'.','.','.','.','.','.','.','.'}      };```
• 10-31-2005
Enahs
What exactly do you mean by shortest possible path from one x to another x?
• 10-31-2005
durban
the shortest possible path would be a line, look up some line algorithms on google
• 10-31-2005
durban
You could translate this algorithm to use recursion. Its called the bresenham algorithm, made for drawing effective lines between 2 pixels quickly:

Code:

```void brenenham1(int x1, int y1, int x2, int y2) {     int slope;     int dx, dy, incE, incNE, d, x, y;     // Reverse lines where x1 > x2     if (x1 > x2)     {         bresenham1(x2, y2, x1, y1);         return;     }     dx = x2 - x1;     dy = y2 - y1;     // Adjust y-increment for negatively sloped lines     if (dy < 0)     {         slope = -1;         dy = -dy;     }     else     {         slope = 1;     }     // Bresenham constants     incE = 2 * dy;     incNE = 2 * dy - 2 * dx;     d = 2 * dy - dx;     y = y1;     // Blit     for (x = x1; x <= x2; x++)     {         putpixel(x, y);         if (d <= 0)         {             d += incE;         }         else         {             d += incNE;             y += slope;         }     } }```
EDIT:
if all else fails, you could modify the array to hold a struct and apply the bellman-ford algorith to it. It's made for picking the shortest possible path throughout a whole bunch of nodes. It's used fo routing data throughout large networks such as the internet :). A good way to impress your professor nonetheless.
• 10-31-2005
salman86
Quote:

Originally Posted by Enahs
What exactly do you mean by shortest possible path from one x to another x?

Can't you display the whole array and kind of path with other letter for example "P" from one X to another X?