Right

			//The bounding box
			float left   = focusObjs.get(0).x;
			float right  = focusObjs.get(0).x + focusObjs.get(0).getWidth();
			float top    = focusObjs.get(0).y;
			float bottom = focusObjs.get(0).y + focusObjs.get(0).getHeight();

			for(int i = 1; i < focusObjs.size(); i++)
			{
				GameObject focus = focusObjs.get(i);
				
				if (focus.x < left)
					left = focus.x;

				if (focus.x + focus.getWidth() > right)
					right = focus.x + focus.getWidth();
				
				if (focus.y < top)
					top = focus.y;

				if (focus.y + focus.getHeight() > bottom)
					bottom = focus.y + focus.getHeight();
			}
			
			float width = right - left;
			float height = bottom - top;

			/* Set the zoom */
			
			if(stage.visibleWidth > width && stage.visibleHeight > height) //Avoid modify the zoom value if the entities are close to each other
				zoom = 1;
			else if(width > height)
				zoom = width / stage.visibleWidth;
			else
				zoom = height / stage.visibleHeight;
			
			/* Translate tx and ty */

			float middleX = left + (width  / 2);
			float middleY = top  + (height / 2);
			float marginX = stage.visibleWidth / 2;
			float marginY = stage.visibleHeight / 2;
			
			if(marginX > middleX)
				tx = marginX;
			else if(middleX > stage.width - marginX)
				tx = stage.width - marginX;
			else
				tx = middleX;
			
			if(marginY > middleY)
				ty = marginY;
			else if(middleY > stage.height - marginY)
				ty = stage.height - marginY;
			else
				ty = middleY;

Note, visibleWidth and visibleHeight is the size of the view, which is 800x600.

			/* 1) Compute the bounding box. */
			
			float boxX	= focusObjs.get( 0 ).x;
			float boxY	= focusObjs.get( 0 ).y; 
			float boxWidth	= boxX + focusObjs.get( 0 ).getWidth();
			float boxHeight	= boxY + focusObjs.get( 0 ).getHeight();

			for(int i = 1; i < focusObjs.size(); i++)
			{
				GameObject focus = focusObjs.get(i);
				
				boxX = Math.Min( boxX, focus.x );
				boxY = Math.Min( boxY, focus.y );
				
				boxWidth  = Math.Max( boxWidth, focus.x + focus.getWidth() );
				boxHeight = Math.Max( boxHeight, focus.y + focus.getHeight() );
			}
			
			/* 2) Apply a padding so that none of the focus objects are on the edges of the viewport.
			   
			   Probably better to use a 'static final' member of some important class.
			   
			   The padding should be a value in pixels (e.g. '20') of the thickness of 
			   the border that insets from the viewport. */
			
			boxX -= gameEngine.CAMERA_FOCUS_PADDING;
			boxY -= gameEngine.CAMERA_FOCUS_PADDING;
			boxWidth  += gameEngine.CAMERA_FOCUS_PADDING * 2;
			boxHeight += gameEngine.CAMERA_FOCUS_PADDING * 2;

			/* 3) Constrain the padded bounding-box to the stage. */
	
			boxX = Math.Max( boxX, 0 );
			boxX = Math.Min( boxX, stage.width - boxWidth ); 			

			boxY = Math.Max( boxY, 0 );
			boxY = Math.Min( boxY, stage.height - boxHeight );
			
			/* 4) Set the zoom. */

			if ( boxWidth > boxHeight )
				zoom = boxWidth / stage.visibleWidth;
			else
				zoom = boxHeight / stage.visibleHeight;

			zoom = Math.Max( zoom, 1.0f ); // Don't let zoom factor be less than 1.0f.

			/* 5) Final step, compute the center of the box. */

			float middleX = boxX + ( boxWidth / 2 );
			float middleY = boxY + ( boxHeight / 2 );

Thanks. The code piece did not work at all first. The bounding box was always wrong, being way to large.

I checked it out and noticed two missing lines after the for-loop:

boxWidth = boxWidth - boxX;
boxHeight = boxHeight - boxY;

That fixes the bounding box. However, the results are almost identical to the previous code. The bug showed in the video still occurs.

I am suspecting boxWidth > boxHeight is not enough, but dunno.

Thanks. The code piece did not work at all first. The bounding box was always wrong, being way to large.
I checked it out and noticed two missing lines after the for-loop:

boxWidth = boxWidth - boxX;
boxHeight = boxHeight - boxY;

I tried removing some code, such as padding and camera camera constraining. No luck.

However, I added some debug code after the zoom is set:

if(isKeyPressed(Keys.E))	
	zoom = boxHeight / stage.visibleHeight;

So basically, I pressed 'E' every time the zoom messed up and it was corrected every time. So I am fairly sure that the if-statement boxWidth > boxHeight is the issue.

Not sure how to resolve it though.

if ( (float)( boxWidth / boxHeight ) > (float)( stage.visibleWidth / stage.visibleHeight ) )

Tried that among a bunch of other conditions. Wont work :(

EDIT: Actually, the code snippet posted above by Kryzon works fine, thanks again for all the help.

The problem was in the casting. For example, (float)( stage.visibleWidth / stage.visibleHeight), these are two ints that are divided. The results, which is also an int, is then casted to a float, which is wrong.