bullets and ship locations would eat up more space than that... Just let the game generate a script, which it can playback (I have seen that a few times in ASSS)
adjustable tile properties (fly over, fly under, etc); ex: allow any tile to be fly over EDIT: woops, didn't see Samapico already suggested this, ah well