Classical work on random walk in random environments assumes uniform ellipticity of the environments, so the walker always has available the maximal number of directions to move off in. But interesting questions arise when this condition is relaxed, adding an aspect of percolation to the analysis. I will describe a number of results for such models including a recent shape theorem for the set of accessible sites in what is called the orthant model. This is joint work with Mark Holmes (Melbourne).