We parked the motorbikes and trudged up to the crst of the sand dune. Sure enough, down in the depression below, a jerrycan handle poked out above the windblown sand. Below the surface lay more fuel, some vital water and a barrel of food.

We excavated the cache and gorged ourselves like fools, relieved to have reached the Erg Killian, a sand sea close to Algeria’s border with Niger. This was the sharp end of our illicit excursion into Niger, destination Arbre Perdu, an isolated landmark in the featureless Ténéré Desert.

With the fuel cache (buried months earlier during a 4WD recce) we could now continue our 1500-kilometre round trip to the Tree and back. We had no visas for Niger, but as expected saw no one for five days.

I’d cooked up the radical Desert Riders Project with a couple of friends, to motorbike off-piste in the heart of the Sahara. At one stage we’d managed just four kilometres in a day before collapsing in an exhausted heap, but out here on the wild borderlands of Algeria the riding was exhilarating and serene.

It seemed like a good time to explore the remote reaches of Algeria, the perfect Saharan country. Desert tourism was returning to its late-Eighties heyday and, while the troubles in the north had barely touched the desert, it was only a matter of time.

In late February, just a week after we’d got back from Desert Riders, four bikers we’d met in Tamanrasset were reported missing in the ravines of the Tassili N’Ajjer plateau on a route we’d travelled ourselves just weeks before. In the following weeks party after party disappeared inexplicably, 32 desert tourists abducted, it transpired, by a little-known Islamic group.

After two months in captivity, half were rescued in an army raid after a camel they’d shot for food was tracked by a nomad they’d stole it from, who contacted the police. Of the remaining fifteen hostages there are still only rumours of Libyan mediators and huge ransoms*.

And so for desert travellers, Algeria slips into the shadows once more. Countries open up gradually, then close for years in a matter of days. But, as the Tuareg observe, “the desert endures”.

Chris Scott first visited the Sahara aged 21. Twenty years and as many trips later he’s written the Adventure Motorcycling Handbook and Sahara Overland while organising tours, filming, or simply exploring. His books and dvds, including Desert Riders, are available from sahara-overland.com.

* All but one of the remaining hostages were released in late August after this was written. Michaela Spritzer died of heatstroke in June.