I know it's really minor, but every stroke counts:

You have several ternary ops using '==' (e.g. $_==16?$p:$_&=15). Since the variables're all integers, you can accomplish the same thing using '-' and reversing the order of the options. (e.g. $_-16?$_:$p&=15).

In general X==Y?A:B is equivalent to X-Y?B:A. (Note that, in the more complicated (multiple-)ternaries, you'll have to do a bit more shuffling.)

Also, I thought I should tell you that your latest version (4 lines + 70) doesn't work properly on my machine:
(This is perl, v5.8.0 built for i686-linux)
It gets to the upper left corner, the entire grid changes to squares, and it continues to wander.
Update: Or at least that's what it did when I forgot to edit out the other <code> sections... (oops)