After edits that makes things easier. Check out this topic: https://gamedev.stackexchange.com/questions/37887/generating-random-tunnels

1. Initialize paths for `SCREEN_WIDTH + BUFFER_WIDTH` pixels.
2. Every time you go further, add more curves, but don't remove old (as you can go back)
3. I suggested curves, because pixels take more memory, though they might still be OK.