Caravel

I agree with you about transverse travel across Africa. More realistic to have basically two zones (Morocco and Egypt) that might be invaded or from which invasions might come. Noone would invade Morocco via Egypt or vice versa (alright - the Arabs did it in the 8th century, but that's a one-off and out of period!). If you've got the provinces, there's also a zone in the middle that attracted a couple of crusades in its own right - but I'd suggest less essential to realism than, for example, splitting up Syria.