should i initalize all the NPC monsters and terrain features for every screen right away

You can, there certainly isn t anything stopping you from doing that:

However it depends on how big your levels are and the tradeoff between load time and lags during the game (for example when the next screen is loaded).

I would suggest the following:

First: Threads

Create two threads that run concurrently, one that is repsonsible for the actual gameplay, and another whose only responsibility is to load new terrain. The gameplay thread is the main one, and will trigger the loader thread to load new terrain data when the player goes to the next screen.

Second: Reducing lags between one terrain and another

Avoid loading the next terrain upon entering it. What you should do instead is (for a sidescroller), load the terrain that s one to the left, and load the terrain that s one to the right of the current position. That way you don t need to keep the entire level in memory at once, and at the same time will never run into a lag upon entering the adjacent terrain. This works rather well with the first point.

This also fits in nicely with your requirement of having the NPC monsters in one terrain being able to "follow" you to the next terrain (if you haven t killed them); with the caveat being that if the player gets through two screens in a row without the NPC monsters getting through one, they are not able to folow you further; which is how many of the sidescrollers I have played appear to work anyway.

Also note that this means that that when you start a level, you will have to load either 2 or 3 terrains at once (depending on whether you start at the edge or the middle of the level), but subsequently, you will only ever have to load one terrain at a time, because all you have to do is swap out the current one with the adjacent one each time the player advances to the next terrain

what s the best format / way for storing what goes into each screen?

Serialize

Given that your chosen platform is Java, I would say the most load-time efficient way of persisting the level data is serialization. Make the classes which store information about the levels and the object in in implement the Serializable interface.

If you do choose this option, when you create the levels for the first time, you would either have to create special methods to hardcode the intialisation of each level and then Serialize them before loading up the game; or you would have to build a level editor.

XML

This option increases your load times considerably as compared to deserialising objects, but it is more robust, and and is easy as hell to make changes. This is probably the best option if your levels aren t very complicated.

In fact, there is nothing stopping you from doing a combination of both.