Here I was bracing myself for the imagined complexities of movement logic, and it turned out to be a whole lot simpler than I imagined. Probably blame it on the other two engines I've had experience with path-finding for: Lure, and Tinsel, both of which have their share of complicated logic. For Rex Nebular, though, the implementation was a lot more elegant than I'd expected.
What the MADS engine does for walkable areas is to have two parts. The first is a priority/depth surface, which had already been previously implemented. This is a surface which both specifies the walkable areas, and is also used to determine which parts of an object, at a given 'depth', should be drawn on-screen. In the first room, for example, the area comprising the chair has some varying levels so that the player gets drawn behind it.
The other part to the movement functionality is a series of 'scene nodes'. These are a series of points distributed across the scene to represent appropriate intermediate points in movement. If a straight line between the start and end point isn't possible, because of a marked obstruction, then the engine calculates the distance between each node in the scene, including both the start and end points as two extra nodes. It then calculates which series of nodes will take the shortest amount of time to traverse, and uses that as the basis for movement - the actual walking then moves the player from node to node until the destination is reached.
This works well for the game since, unlike in Tinsel or Lure, there aren't ever any moving actors that could interrupt the walking path. The only NPC character movement that ever happens is in cut-scenes, where the player is either not moving, or is being controlled by the computer (such as when Rex is taken to the cells).
Now that I've got Rex moving around on the screen, the next immediate step is to get the hotspot and selection code working. Somewhat ironically, this is turning out to be more complicated than the walking code itself. I'm currently working my way through disassembling the various routines and implementing comparable code. Hopefully, I'll soon have enough implemented that I can properly implement some actual actions in the first room.