If we go for the "character can walk away from the screen" concept, I would make sure we have only two "lanes" the player can be on. He can either be on the one closer to the screen or, by pressing the up key, the one farther away. That way we'd make sure it's still a 3d-walking-concept, but we wouldn't need to worry so much about bugs/collision and it would make it check if there's a wall/gap or not, you wouldn't have to try running against the wall 5 times because there might be a gap, you'd only run into the wall once on both lanes, then you can be sure you checked that place and look for a door somewhere else.