How about making the soldiers move in a random direction when they get stuck, rather than return home?
How about making the soldiers move in a random direction when they get stuck, rather than return home?