Thanks a lot, Simon!

Yes, I read your essay before writing the paper, and it helped me a whole lot!  I briefly took care of that asymmetry by saying that the pin position depends on direction, and that is kind of sufficient for the scope of the paper.  The main issue here is the space constraint of 12 pages!  I would love to add more details, but I don't know how to fit them all.

By the way, I'm not really doing this for my thesis, it's just for fun!  But thanks anyway.   http://www.lemmingsforums.com/Smileys/lemmings/wink.gif" alt=";)" title="Wink" class="smiley" />

Wow, you are certainly an expert in Lemmings and the related literature.   http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />
Thanks for taking the time to write such a comprehensive comment, I sincerely appreciate your effort!

I was aware that I was omitting some details of the game mechanics: I did it due to space limitations (12 pages), and only if they didn't matter for the later proofs.  The only thing that I really need for the NPO part is that the configuration transition between time units can be computed in polynomial time, which is abuntantly true regardless of the details.  On the other hand, I describe Builders and Bashers as thoroughly as I can, because I am going to need them for the PSPACE-completeness part.

However, I was unaware of many aspects of the game that you pointed out, mainly because I tried to figure them out by experimentation and trial and error.  So your contribution is extremely helpful there.  I also wonder if there is any standard "tool" to discover such things, because right now I am only using the game itself and the Lemmix editor, but I have a hard time pausing the game after each frame, for instance...

Luckily enough, most of my misconceptions don't seem to substantially affect the paper's main results.  I also extensively tested all my gadgets, and they all seemed to work even when I tried my best to "break" them (making such a "robust" Door gadget took me quite a lot of time, actually...).

I will take into account all your comments, and see where I have to correct the paper.  Hopefully I can keep it within 12 pages, which is my main concern right now...

Cheers!   http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" />

P.S.  The Lemmings Wiki was there just a couple of days ago, when I last checked!  Maybe it's just temporarily offline?  Can some admin confirm this?

Hi, I recently wrote a paper discussing the computational complexity of Lemmings.  Inicidentally, it answers the questions you were asking in this thread.
http://www.di.unipi.it/~vigliett/files/papers/lemmings.pdf" class="bbc_link" target="_blank">http://www.di.unipi.it/~vigliett/files/papers/lemmings.pdf

Regards.

P.S.  I would greatly appreciate your comments and corrections, especially concerning my description of the game mechanics (Section 2).
P.P.S.  The PSPACE-completeness proof in my paper builds upon another result of mine, contained in this other paper:
http://www.di.unipi.it/~vigliett/files/papers/gaming.pdf" class="bbc_link" target="_blank">http://www.di.unipi.it/~vigliett/files/papers/gaming.pdf