Majesty.
It’s a strategy simulation game, a bit like an RTS, but you can’t directly control units.
Instead all units follow general archetypes. Rogues generally won’t spontaneously help you but will do most anything for money. Warriors will seek out monsters and lairs that have been discovered. Rangers will explore the map. Units will also do things like buying potions or upgraded equipment based on their class and intelligence.
As the player you choose what buildings to place and can offer rewards for exploring an area or killing something.
There was a sequel, but it’s a significantly worse game than the original.
No. Military service in place of prison isn’t elective, you still need the state to allow it. Even then you would be completely free, you likely wouldn’t get leave for a while, and a discharge could put you into prison.