Every monster has 1000 bytes artificial intelligence (AI henceforth), so they will reside around the place where they found money or food the last time they looked. Depending on whether they are hungry or tired you can find them scavenging the dungeon for a meal or dozing off for an afternoon nap.

They even have personality. Undead skeletons will be found around fresh corpses, giant spiders in dusty quarters, while the vampires want to live somewhere, as dark and secluded as possible.

And make sure to pay everybody off - well. If the monsters don't get paid, they will leave faster than you can say:

"Peter Molyneux".

The navigational part of AI demands a lot too. Since you're the one who will be taking decisions concerning where to build and mine - the monsters can't have a preset pattern for getting around. They will have to cope for themselves and totter around till they know your hideout by heart.

Basically the navigational CPU-part is done by selecting the shortest path and then adding a "stupidity factor" so the imps will make a wrong turn every once in a while. And if somebody gets helplessly stuck in a remote corner of your realm - you may have to take over it's body for a short while and get it back on the track again.