Sparse Object Space Game

I am making a game similar to Asteroids where the player fights other ships. The game map will be larger than the screen in almost every case. I intend to have small bases and mazes and the sort, similar to this: .............0........................................... ................................................... .....0........................0.................... .......XX..XX........................................... ......X......X...................................... .....X....0...X..............9................ .....X...o....X........0.................... .....X........X........................... ......XXXXXXXX............................................ Anyways, the Xs represent walls, and the numbers represent rocks and small obstacles. Tiles will be about 16x16 for the most part. My first question is this: What would be the best method of storing wall and asteroids/rock/obstacle positions for collision detection? I''ve got a couple of ideas: Treat each wall segment as an individual object in the game. For instance: X is a segment. Test each segment for collision between ships/bullets/etc.. every frame. This method is probably slow, but easy to implement. Treat each wall as an individual, variable size object in the game. For instance XXXXXXXXXXXXXXXX is a single object. Faster than previous, similar to checking ball collision with a paddle in pong, possibly harder to implement. Have a multidimensional array of Bools, solely for collision testing. Walls can''t move, so this would work well. This might be hard to implement. Not to mention the math needed to convert ship positions to indexes into array involves some division, and since ships are about 2.2 times larger than tiles, this would involve checking ~ 9 tiles per ship per frame. I don''t know what I should do! Any other ideas or maybe suggestions? Also, I would like to have a parralax starfield behind the ship the player is controling. Since the ship moves a viewport within the map, I want the stars to move with the ship, but also scroll every time he moves one viewport in any direction... I also want the starfield to look different for every viewport position in the map. Make sense? I am completely bewildered at this. I thought of having a random num gen and seeding it with something like: viewportX^2 + viewportY whenever the ship enters a new section, and then generating a new starfield. Also, the starfield does not move. Like i said, it is parallax. When the ship moves, the position of the bottom layer only changes by .25 of the players movement... and so on. ANy ideas?