Given two points on a 2D grid, how many paths of length N connects them? The paths are not required to be monotonic, and they may self-intersect. This sounds like a difficult question, so what I am really asking is if this problem has a name, if it is NP-hard and if there is some upper bound. I assume the grid to be infinitely large.
The image below shows some example paths for two points, $A$, $B$, but I am not asking about these points specifically. The paths have length $N=7$, $N=9$ and $N=11$.

 A: Let the two points be $A(a,b)$ and $B(a+r,b+u)$. Note that $r$ and $u$ represent the net moves along the $x$ and $y$ axes respectively required to reach point B from point A.
Case $1$:  If $|r|+|u|=N$, then the paths have to be monotonic and the answer is simply $$N\choose |r|$$
Case $2$: If $|r|+|u|>N$, then there aren't  enough moves and the answer is $0$.
Case $3$: $|r|+|u|\lt N$ 
Now for the harder part. I'll write $|r|+|u|+2x=N$. The $2x$ here represents the extra moves needed. Notice that the  number of extra moves will be always be even as with every additional left move, we need a right move and with every additional down move, we need an up move. 
Now, define $P_1$ to be the number of extra pairs $\boxed{LR}$ (one left and one right move) and similarly $P_2$ to be the number of extra pairs $\boxed{DU}$(one down and one up move). Clearly, $P_1+P_2=x$, and $P_1$ and $P_2$ can range from $0$ to $x$ giving us a total of $x+1$ possibilities. Furthermore, it's not hard to check that for a fixed $P_1$, the total number of $$\text{Right moves is} \ (|r|+P_1) \\ \text{Left moves is} \ (P_1) \\ \text{Up moves is} \ (|u|+x-P_1) \\ \text{Down moves is} \ (x-P_1) $$ Given all this, the only thing that remains is to take care of the order of moves, which is equivalent to permuting the stated number of $R’s, L’s, U’s$ and $D’s$. Summing the possibilities fetches the answer. 
In the sum below, the first factor decides where the $R’s$ go, the second factor decides where the $L’s$ go in the remaining places, and the third factor decides where the $U’s$ go, after which the $D’s$ are already taken care of.
$$\sum_{P_1=0}^x {N\choose {|r|+P_1}} {{N-(|r|+P_1)}\choose{P_1}} {{N-(|r|+2P_1)}\choose{|u|+x-P_1}}
\\ =\sum_{k=0}^{\frac{N-|r|-|u|}{2}} {N\choose {|r|+k}} {{N-(|r|+k)}\choose{k}} {{N-(|r|+2k)}\choose{\frac{N+|u|-|r|}{2}-k}} $$ A monstrosity indeed.
A: Here is just an idea, so correct me if I am wrong
Say we need to get to a point B($n_1,n_2$) from A($0,0$), in $N$ steps.
Let $x_i$ denote a move in the $x$ direction (its value can be $1$ or $-1$ depending on right or left.)
Similarly define a variable $y_i$.
Now,
$$x_1+x_2+x_3+....x_r=n_1........(1)$$
$$y_1+y_2+y_3+.....y_{N-r}=n_2.......(2)$$
So possible solutions for (1) can be found by:
=coefficient of $x^{n_1}$ in $(x^1+x^{-1})^r$ =$A(r)$
Similarly, no. of possible solutions for (2):
=coeff. of $x^{n_2}$ in $(x^1+x^{-1})^{N-r}$ = $B(r)$
So the total possible combinations are;
=$$\sum_{r=0}^N A(r) \times B(r) $$
If the functions of $A(r)$ and $B(r)$ are found, then I think you can get a nice closed form.
