Navigation Meshes

Since pathfinding algorithms work on graphs you can model terrain as interconnected polygons instead of a tileset. Each face represents what used to be a tile and the edges of the face represent how one tile connects to another tile.

Valid locations to stand can be modeled as these planes/faces overlaid on top of the floor of a level. Traversing 3D space is irrelevant because the pathfinder still sees this as a regular old graph, so going up a stairwell is “just” walking the nodes of the graph that happen to be laid on top of the staircase.

You use regular old pathfinding routines to path from one tile to another tile.

Because tiles may be large you will need a secondary mechanism to avoid collisions with temporary obstacles which also exist on each face. This may be some complicated flow-based pathing or a simple obstacle avoidance heuristic.