And one thing that works marvels to make the story more complex is to have factions. Lots of factions, with different motives and different purposes. Even if a faction consists of one person, being at cross-purposes with all the other characters ups the conflict.
And the man with the gun in his hand makes an excellent new faction. He may have to be one, if nothing already in the story would intervene then to shake things up.
BUT -- it does raise a little difficulty in pulling the story together and making it work. If a wandering monster strikes, it is a random episode in the manner condemned as far back as Aristotle. And I notice that in Order of the Stick, after the story got going, there was a wandering monster gag in which some displacer beasts escaped the party by secrecy, and no other wandering monsters appeared. They did not fit into the story. Any story involving a lot of travel faces the danger a lot, too.
All factions have to be resolved one way or another. It can be dangerous to have all twelve or so collide at the climax. Too much clutter. You need to have some vanish or be subsumed in another faction before the end. But the man with a gun in his hand has to be disposed of with enough pomp and circumstance that he doesn't turn into an episode that makes the story episodic, the worst of all plots.