Perhaps if you could add a trait for Armies crossing the Desert, making your supply lines rediculously low, that by the time you enter a Neighboring Region, Your Moral would take such a huge negative effect you simply couldn't win. Only by following the Mediterranean Coast could you avoid such a conflict. But then you'd have to take Kyrene...which isn't a very easy task.