The Good, the Bad, & the Weird is an fun movie that might give you ideas as well, although it's set in Manchuria, rather than Xinjiang. It's Korean, rather than Chinese, but it sounds like what you're looking for, and there's a certain amount of commonality between all the former horse nomad areas in Central Eurasia, from Manchuria to the Hungarian plain.