Running (not walking) on the edge of the map makes it easier. It should allow to skip on a lot of those - even more so with Chameleon. Also you can run even if combat begins, which is an often easier and almost always quicker way to deal with encounters.

If you fight more than half your encounters you should really improve your movements ;)

Once you get the X-Ray spell, things get a lot easier. With it you can see where enemies are on your automap, which makes it easier to avoid encounters.