You can throw directions out the window and use Inform for abstract locations if you like. There are ways in which choice-based is a better fit for conversation than parser-based, but parser-based games often mitigate it by using a choice-based conversation mechanic. Twine has less built-in support for a world model, which might or might not matter depending on the details of what you want (and you can implement something world-model-ish, with work).
With apologies for veering from the question as asked, here are some links of interest regarding mystery IF: