# Count paths of length $n$ that a player can take

I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $$n$$ that a character can take, where the character can move left, right, or up. The caveat is that the character cannot go back to the same position in a path.

I've come up with a mediocre brute-force method the count the paths, but any ideas on an efficient way to calculate this?

• Are some cells of the grid forbidden ? – Optidad Jun 11 '19 at 17:47

This is a question in combinatorics, and can be calculated in a closed formula.

The key settings are:

• "Down" is not allowed
• Visiting previously visited square is not allowed

From the two requirements, we can draw the following conclusions:

• Up is always a valid move (since we never went down, going up is essentially revealing a new square)
• Left is not valid after Right, but is valid after Up (revealing new row) or after Left (which is essentially unvisited)
• Right is not valid after Left, but is valid after Up (revealing new row) or after Right (which is essentially unvisited)

Denote $$U$$, $$L$$ and $$R$$ for Up, Left and Right respectively. We can now represent a path in a string like so: $$P = (U,U,U,U,L)$$

The question is now: How many valid paths strings of length $$n$$ are there?

Let $$T(n)$$ be the number of valid strings of length $$n$$

• If the first move is $$U$$ then the remaining strings are $$T(n-1)$$

• If the first move is $$L$$ then the remaining strings are those starting with $$L$$ or $$U$$

• If the first move is $$R$$ then the remaining strings are those starting with $$R$$ or $$U$$

Looking at strings where the first move is either $$L$$ or $$R$$: the remaining strings are: strings starting with $$U$$ (twice), starting with $$L$$, or starting with $$R$$. (simple summation of all the options in 2nd and 3rd bullet).

Note that all the strings starting with $$U$$ + all the strings starting with $$L$$ + all the strings starting with $$R$$ is exactly $$T(n-1)$$ since the first move is already set.

We are left with one more instance of "all the strings starting with $$U$$" = $$T(n-2)$$ (again, first move is set)

Which results the following recursive formula: $$T(n) = 2T(n-1)+T(n-2)$$ where:

$$T(1) = 3, \space T(2) = 7$$

Calculations omitted, the closed formula for the relation above is:

$$T(n)= \frac{(1+\sqrt{2})^{n+1}}{2} + \frac{(1-\sqrt{2})^{n+1}}{2}$$

Obervations :

• As you only allow for up and left/right moves, when you leave a row (by going up), you can't come back to it.
• As you cannot revisit the same node in a given path, when you go right on a row, you can't go left afterwards.

I think this can lead to a direct formula for paths of length $$n$$, but you can first try to compute the paths with $$k$$ moves up, and then sum for $$k$$ from 0 to $$n$$ (and you get a recurrence relationship here)