Recursive Pathfinding

[Bixarrio]

This is an evil question (well, for me at least):

I am moving from point a to point b on a grid. I can only move left, right, up or down. Once I've started, I cannot go back in the direction I just came from. The cell I'm standing on, gets counted as 1, thus If I want to move 1 cell, I stay where I am. If I want to move 2 cells, I may go to any of the 4 adjacent cells.

I know (through a lot of testing) that:

1 cell = 1 path (since I stay where I am)
2 cells = 4 paths (adjacent cells, no diagonals)
3 cells = 12 paths
4 cells = 36 paths
5 cells = 108 paths
6 cells = 324 paths
etc.

I need to calculate the amount of possible paths.

I figured out that (from 2 upwards) each distance (amount of cells to move) is the amount of paths of the distance - 1, times 3:
2 = 4
3 = (4 * 3) = 12
4 = (12 * 3) = 36
5 = (36 * 3) = 108
6 = (108 * 3) = 324

the answers grow exponentially to where a distance of 20 cells have 1,549,681,956 possible paths!!!!!!!!!

Is there a formula that will calculate these possible paths, that doesn't look like this:

6 = ((((4 * 3) * 3) * 3) * 3)???

[ericlin]

Do you mean:

4*Math.pow(3, n-2)

[Bixarrio]

I mean EXACTLY that!!!!

Thank you, thank you, thank you. I knew there would be a simple formula.

I can KISS YOU!