I was looking at some of the old games I have in storage and I came across what I think might be the perfect game for Asterion: the PS2 classic ICO. A protagonist with horns leads a prisoner out of a "labyrinth" of sorts. There's even a prominent room near the beginning that features a large spiral staircase, similar to the hotel. There is some combat, but it's very rudimentary and is secondary to the main draw of navigating a vast environment.