How can we build a ZKP simulator for “Were is waldo?”?
I think that it would be more suitable to model this as witness hiding, meaning that after the proof it should be still be "computationally hard" to find Waldo. The best place to learn about witness indistinguishability and hiding is either in Oded Goldreich's Foundations of Cryptography (volume 1), or in Uri Feige's PhD Thesis.

In general, witness indistinguishability is a property that just says that it's not possible to distinguish which witness the prover knows. It is not hard to show that zero-knowledge implies witness indistinguishability, but it gets more interesting. For example, parallel repetition of witness indistinguishable proofs preserves witness indistinguishability and reduces soundness. Thus, it is possible to construct 3-round witness indistinguishable proofs for any language in NP (something that is not possible for zero knowledge, at least not for black-box zero knowledge). 

Feige also defines witness hiding, which means that if a language is hard and one cannot extract a witness, then even after the proof the verifier cannot extract a witness. For example, consider a randomly sampled tuple $(g,h,g^x,h^x)$. Then, a prover could prove that this tuple indeed is of this form (what we call a Diffie-Hellman tuple) using a zero-knowledge proof. Alternatively, in some cases it may be enough to just prove that it is of this form in a way that ensures that a cheating verifier cannot learn $x$ (or any other witness to this fact). As such, witness hiding is the "one-way function" analog of zero-knowledge; it is much weaker, but makes sense in some cases. Feige showed that any witness indistinguishable proof with two "computationally independent witnesses" (meaning that one cannot learn one witness without the other) is witness hiding.