What is the generating function of $f_{m,n}$?
$ f_{m,n} = \begin{cases} 0 , & \text{if $m<0 $ or $ n<0$ }; \\ f_{n,m} , & \text{ if $n<m$}; \\ 1, & \text{ if $0=m$ and $ n\in\{0,1\} $}; \\ f_{0 ,n-1}+ f_{1,n-1}, & \text{ if $0=m$ and $ n>1 $}; \\ f_{m-1 ,n}+ f_{m ,n-1}+ f_{m-1,n-1}, & \text{ if $0<m\in \{n,n-1\} $}; \\ f_{m-1 ,n}+ f_{ m ,n-1}+ f_{m-1,n-1} + f_{m+1,n-1},& \text{ if $0<m<n-1$}. \end{cases} $
Consider the following generating function: $$F(x,y) := \sum_{n=0}^\infty \sum_{m=0}^n f_{m,n} x^n y^m$$ and its diagonal $$D(z) := \sum_{n=0}^\infty f_{n,n} z^n.$$ Then the recurrence implies the following functional equation: $$2(1-x-y-xy)F(x,y) - 2x\frac{F(x,y)-F(x,0)}y = 1 + (1-xy-2y)D(xy).$$ I'm not yet sure if it can be solved explicitly.
It's also worth to mention a couple of boundary properties for $F(x,y)$: $$[y^1]\ F(x,y) = \left.\frac{F(x,y)-F(x,0)}y\right|_{y=0} = \frac{(1-x)F(x,0)-1}x$$ and $$\sum_{n=1}^\infty f_{n-1,n} z^n = \frac{(1-z)D(z)-1}2.$$
ADDED. Introducing another generating function: $$G(x,y) := F(x,\frac{y}{x}) = \sum_{n=0}^\infty \sum_{m=0}^n f_{m,n} x^{n-m} y^m$$ we get a self-contained functional equation: $$2(y-xy-y^2-xy^2-x) G(x,xy) = y + (y-2y^2-xy^2) G(0,xy) – 2x G(x,0).$$
