? Map Stitching/Tiling - e.g. Google Map, etc ?

I was wondering if anyone had any code or direction on how to develop something similar to google maps, where as you zoom closer the large single earth image is replaced with more detailed (high res) maps of the currently zoomed area…and the deeper you go the more detailed the maps become.

Basically I want to try to implement the following (I believe…I’m still trying to understand it):
http://msdn.microsoft.com/en-us/library/bb259689(printer).aspx

So, as in the example above, I have 1 map texture for the overall zoomed out map view, then I break the map into quadrants (or something similar) and have higher res maps for those quadrants, and based on the zoom level I have currently I would swap out the map image with the tiles and still be correctly zoomed over the correct point above the map.

I think I understand this, but I don’t know the best way of going about the replacing of the image…the easiest test solution would probably be simply to replace the entire image I currently have with one of the higher resolution, but obviously it would be a waste to draw the parts that are not visible, so how do I go replace just the section that I’m zoomed over…it it fairly simple? Do I just drawImage while specifying the x,y coordinates and width/height and is it that simple?

I’m just thinking that this has to be harder that I’m describing…anyone do this before? it it hard?

Just a thought, if you are going to use PNG for your images, I believe the format allows partial image decompression. i.e. say you have a 3000x3000 image saved as a PNG, you can “load” only a sub section of the PNG, lets say 640x480 at location 400,600. This will mean that you do not need to decompress the entire image in to memory and will save having to have pre-cut tile images.

This means you need only have as many images as you have zoom levels. (of course these images will increase in dimensions as you increase in zoom)

You may need to research to find a PNG loader for java which allows you to do this.

Interesting, I was not aware of this, thanks. I was not planning on using PNG images at the moment, though I guess they can be converted to that format.

I might have to use that if I can’t figure out the tiling with zooming. I’ll still try to pursue the tiling option as that has been of interest to me for a while, but now I actually need a solution for the map tool I’m making. The biggest question that I have so far is how to do the zooming properly. Currently I have one image, and this images gets scaled by the zoom factor and so as you get closer you get a more grainy/blurry image - obviously. With the zooming and tiling (or whatever it is called) you initially would still scale your image until you reached the appropriate threshold at which point you replace the current image with the composite of higher resolution images, but at that point I think you have to clear your scale factor because you would effectively be doing double scaling: first scaling via scaling factor, and second scaling because you swapped to higher resolution images…does that sound right?

Hi,

I’ve got some code that you could modify to do something like what google maps does.

I’m making a top-view down game where I use tiled images as a back-buffer which I draw other images and effects onto, these tiles form the map. As the player moves to the left, the tiles on the right which are not on the screen anymore are recycled and moved to the left where they are needed. These recycled tiles are re-painted appropriately.

Currently if you zoom in, the tiles are zoomed into as well, so there are fewer tiles visible on the screen. If you zoom out, then the tiles are zoomed out too and you need more tiles on the screen.

Let me know if you would find this code useful.

It is worth a shot, CommanderKeith…I won’t turn down free code and would be useful to see how people implement things…so yes, I would like what you could provide. Thank you.

A little off centre, but I have had the thought that instead of “blurring” when zooming, how about a total paradigm shift?

Instead of having discrete sets of tiles at different levels of zoom, why not generate mathematical models of how the pixels from the highest resolution (zoomed in) image progressively merge as you zoom out. In this fashion you will achive very little burring and you can have an arbitrary zoom level.

I am thinking that using Least Mean Squares to generate equations to produce the mathematical model of how the pixels merge. To do this I would start with the highest resoultion image and the progressively resize the image, say by 10% each time, generating a list of samples corresponding to each original image corordinate. The least Mean Squares would use each list of samples to generate a function which approximates the list.

This way, all you need to do is to do generate a zoomed image is something like:



double multiplier = MAX_ZOOMED_IN_IMAGE_WIDTH / image.getWidth();

for (int y=0;y<image.getHeight();y++)
{
  for (int x=0;x<image.getWidth();x++)
  {
    image.setRGB(x,y,model.getRGB(offsetX + x*multiplier, offsetY + y*multiplier,zoom);
  }
}

where
offsetX,offsetY are offsets on the original high res image representing the current view image offsets.
multiplier is used in conjunction with the x and y coordiantes of the zoomed image being created to reference the correct model.
The zoom is a value between 0 and 1 where 0 is the max zoomed in image and 1 is the max zoomed out image.

But you are talking about going backwards in the zooming…from the highest resolution image to the lowest. Though you only have one image to start with, it is a huge image. The purpose of the tiling approach is to load only the images that you want and as you zoom closer and closer you are only loading or retrieving from a cache the data that you want.

For the creation of the functions which will represent the model the zooming will happen in reverse. This can and should be precomputed.

You do not need to know all the functions at runtime. You need only request the relevant functions to produce at image at a given zoom, so even if you do not cache the functions locally, for each zoom the max number of functions to request is img_width*img_height. With caching of the functions the number that you need to request decreases.

Your program can choose an arbitrary zoom or if you know your program can only zoom in and out then you can pre-fetch functions which could be used.

Sorry for the delay, here’s the code which shows the tiles, I hope you find it useful:



package sydneyengine.shooter;

import sydneyengine.shooter.maths.*;
import sydneyengine.*;
import sydneyengine.superserializable.*;
import java.io.*;
import java.util.*;
import java.awt.*;
import java.awt.image.*;
import java.awt.geom.*;
import java.net.*;
import javax.imageio.*;

/**
 *
 * @author Keith W
 */
public class TileGrid extends SSAdapter{
	ArrayListSS<ArrayListSS<TileImage>> tiles;
	ArrayListSS<TileImage> spareTiles;
	int tileWidth;
	int tileHeight;
	
	GameWorld world;
	
	public TileGrid(){
	}
	
	public TileGrid(GameWorld world){
		this.world = world;
		tileWidth = 200;
		tileHeight = 200;
		tiles = new ArrayListSS<ArrayListSS<TileImage>>();
		spareTiles = new ArrayListSS<TileImage>();
	}
	
	protected TileImage getSpareTile(){
		if (spareTiles.size() > 0){
			TileImage spareTile = spareTiles.remove(spareTiles.size()-1);
			return spareTile;
		}else{
			TileImage spareTile = new TileImage();
			return spareTile;
		}
	}
	
	public void render(ViewPane v){
		Graphics2D g = v.getBackImageGraphics2D();
		BBox viewRect = v.getViewRectInWorldCoords();
		
		int newStartTileIndexX = (int)(Math.floor(viewRect.getX()/tileWidth));
		int newStartTileIndexY = (int)(Math.floor(viewRect.getY()/tileHeight));
		
		int numXTiles = (int)Math.ceil(viewRect.getW() / tileWidth) + 1;
		int numYTiles = (int)Math.ceil(viewRect.getH() / tileHeight) + 1;
		
		//System.out.println("viewRect.w == "+viewRect.w+", numXTiles == "+numXTiles+", tileWidth == "+tileWidth+"... "+(numXTiles * tileWidth));
		//System.out.println("viewRect.h == "+viewRect.h+", numYTiles == "+numYTiles+", tileHeight == "+tileHeight+"... "+(numYTiles * tileHeight));
		
		int xShift = 0;
		int yShift = 0;
		
		if (tiles.size() > 0 && tiles.get(0).size() > 0){
			TileImage topLeftCornerTile = tiles.get(0).get(0);

			int oldStartTileIndexX = topLeftCornerTile.getIndexX();
			int oldStartTileIndexY = topLeftCornerTile.getIndexY();

			xShift = newStartTileIndexX - oldStartTileIndexX;
			yShift = newStartTileIndexY - oldStartTileIndexY;

			if (xShift > 0){
				for (int a = 0; a < xShift; a++){
					ArrayListSS<TileImage> col = new ArrayListSS<TileImage>();
					tiles.add(col);
				}
				// trim off excess tiles
				while (tiles.size() > numXTiles){
					ArrayListSS<TileImage> col = tiles.remove(0);
					spareTiles.addAll(col);
				}
			}else if (xShift < 0){
				for (int a = 0; a < -xShift; a++){
					if (tiles.size() == 0){
						break;
					}
					ArrayListSS<TileImage> col = tiles.remove(tiles.size()-1);
					spareTiles.addAll(col);
				}
				// add on any needed columns to the start of the column list
				while (tiles.size() < numXTiles){
					//System.out.println("added column to tiles");
					ArrayListSS<TileImage> col = new ArrayListSS<TileImage>();
					tiles.add(0, col);
				}
			}
			
			if (yShift > 0){
				for (int i = 0; i < tiles.size(); i++){
					ArrayListSS<TileImage> col = tiles.get(i);
					for (int a = 0; a < yShift; a++){
						col.add(getSpareTile());
					}
					// trim off excess tiles
					while (col.size() > numYTiles){
						TileImage tile = col.remove(0);
						spareTiles.add(tile);
					}
				}
			}else if (yShift < 0){
				for (int i = 0; i < tiles.size(); i++){
					ArrayListSS<TileImage> col = tiles.get(i);
					for (int a = 0; a < -yShift; a++){
						if (col.size() == 0){
							break;
						}
						spareTiles.add(col.remove(col.size()-1));
					}
				}
				// make sure the tile lists are the right size
				while (tiles.size() < numXTiles){
					tiles.add(new ArrayListSS<TileImage>());
				}
				// add on any needed tiles to the start of the row list
				for (int i = 0; i < numXTiles; i++){
					ArrayListSS<TileImage> col = tiles.get(i);
					while (col.size() < numYTiles){
						//System.out.println("added tile to row");
						col.add(0, getSpareTile());
					}
				}
				
			}
		}
		
		// make sure the tile lists are the right size
		while (tiles.size() < numXTiles){
			tiles.add(new ArrayListSS<TileImage>());
		}
		
		for (int i = 0; i < numXTiles; i++){
			ArrayListSS<TileImage> col = tiles.get(i);
			while (col.size() < numYTiles){
				col.add(getSpareTile());
			}
		}
		
		for (int i = 0; i < numXTiles; i++){
			ArrayListSS<TileImage> col = tiles.get(i);
			for (int j = 0; j < numYTiles; j++){
				TileImage tile = col.get(j);
				if (tile.isInitialised() == false || tile.getIndexX() != newStartTileIndexX+i || tile.getIndexY() != newStartTileIndexY+j){
					//System.out.println("bad match, tile.getIndexX() != newStartTileIndexX+i ("+tile.getIndexX()+" != "+(newStartTileIndexX+i)+"), tile.getIndexY() != newStartTileIndexY+j ("+tile.getIndexY()+" != "+(newStartTileIndexY+j)+"), time == "+getWorld().getTimeNowSeconds());
					tile.setStats(this, newStartTileIndexX+i, newStartTileIndexY+j, (i + newStartTileIndexX)*tileWidth, (j + newStartTileIndexY)*tileHeight, tileWidth, tileHeight);
					tile.drawOntoImage();
				}
			}
		}
		//System.out.println("tiles.size() == "+ tiles.size()+", tiles.get(0).size() == "+tiles.get(0).size()+", spareTiles.size() == "+spareTiles.size());
		
		for (int i = 0; i < numXTiles; i++){
			ArrayListSS<TileImage> col = tiles.get(i);
			for (int j = 0; j < numYTiles; j++){
				TileImage tile = col.get(j);
				tile.render(v);
			}
		}
		
		//System.out.println("tiles.size() == "+tiles.size()+", tiles.get(0).size() == "+tiles.get(0).size());
	}
	
	public GameWorld getWorld() {
		return world;
	}
}


And here’s the code for the actual tiles. The forum software wouldn’t let me post the code altogether.



package sydneyengine.shooter;

import sydneyengine.shooter.maths.*;
import sydneyengine.shooter.vectorgraphics.*;
import sydneyengine.*;
import sydneyengine.superserializable.*;
import java.io.*;
import java.util.*;
import java.awt.*;
import java.awt.image.*;
import java.awt.geom.*;
import java.net.*;
import javax.imageio.*;
/**
 *
 * @author Keith W
 */
public class TileImage extends SSAdapter implements RenderArea{
	VolatileImage vImage;
	boolean initialised = false;
	TileGrid tileGrid;
	int w;
	int h;
	int x;
	int y;
	int indexX, indexY;
	
	Point2D.Double viewCenterInWorldCoords;
	BBox viewRectInWorldCoords = new BBox();
	Graphics2D backImageGraphics2D;
	
	public TileImage(){
	}
	
	public TileImage(TileGrid tileGrid, int indexX, int indexY, int x, int y, int width, int height){
		setStats(tileGrid, indexX, indexY, x, y, width, height);
	}
	public void setStats(TileGrid tileGrid, int indexX, int indexY, int x, int y, int width, int height){
		initialised = true;
		this.tileGrid = tileGrid;
		this.indexX = indexX;
		this.indexY = indexY;
		this.x = x;
		this.y = y;
		this.w = width;
		this.h = height;
		
		if (viewCenterInWorldCoords == null){
			viewCenterInWorldCoords = new Point2D.Double(x + (width/2f), y + (height/2f));
		}else{
			viewCenterInWorldCoords.x = x + (width/2f);
			viewCenterInWorldCoords.y = y + (height/2f);
		}
		viewRectInWorldCoords.x = x;
		viewRectInWorldCoords.y = y;
		viewRectInWorldCoords.w = w;
		viewRectInWorldCoords.h = h;
	}
	
	protected VolatileImage createVolatileImage() {	
		//System.out.println(TileImage.class.getSimpleName() + ": calling createVolatileImage(...)");
		VolatileImage volatileImage = ImageBank.createVolatileImage(getW(), getH(), Transparency.OPAQUE);
		Graphics2D g = (Graphics2D)volatileImage.getGraphics();
//		g.setColor(Color.RED);
//		g.fillOval(x, y, w, h);
		return volatileImage;
	}
	
	public void render(ViewPane v){
		GraphicsEnvironment ge = GraphicsEnvironment.getLocalGraphicsEnvironment();
		GraphicsConfiguration gc = ge.getDefaultScreenDevice().getDefaultConfiguration();
		if (vImage == null || getW() != vImage.getWidth() || getH() != vImage.getHeight() || vImage.validate(gc) != VolatileImage.IMAGE_OK) {
			vImage = createVolatileImage();
			drawOntoImage();
		}
		do {
			int valid = vImage.validate(gc);
			if (valid == VolatileImage.IMAGE_INCOMPATIBLE) {
				vImage = createVolatileImage();
				drawOntoImage();
			}
		} while (vImage.contentsLost());
		Graphics2D viewPaneGraphics = v.getBackImageGraphics2D();
		viewPaneGraphics.setTransform(v.getPlayerCenteredATRounded());
//		viewPaneGraphics.setColor(Color.MAGENTA);
//		viewPaneGraphics.drawLine(0, 0, w, h);
		viewPaneGraphics.drawImage(vImage, x, y, null);
//		viewPaneGraphics.setColor(Color.MAGENTA);
//		viewPaneGraphics.drawString("x == "+this.getIndexX()+", y == "+this.getIndexY(), x+10, y+20);
//		viewPaneGraphics.drawString("x"+this.x+", y"+this.y, x+10, y+40);
//		viewPaneGraphics.drawString("w"+this.w+", h"+this.h, x+10, y+60);
	}
	
	protected void drawOntoImage(){
		GraphicsEnvironment ge = GraphicsEnvironment.getLocalGraphicsEnvironment();
		GraphicsConfiguration gc = ge.getDefaultScreenDevice().getDefaultConfiguration();
		if (vImage == null || getW() != vImage.getWidth() || getH() != vImage.getHeight() || vImage.validate(gc) != VolatileImage.IMAGE_OK) {
			vImage = createVolatileImage();
		}
		backImageGraphics2D = vImage.createGraphics();
		backImageGraphics2D.translate(-x, -y);
		
		ViewPane.setGraphicsHints(backImageGraphics2D);
		
		for (int i = 0; i < getWorld().getEnvironment().getFloors().size(); i++) {
			getWorld().getEnvironment().getFloors().get(i).render(this);
		}
		for (int i = 0; i < getWorld().getEnvironment().getPaths().size(); i++) {
			getWorld().getEnvironment().getPaths().get(i).render(this);
		}
		for (int i = 0; i < getWorld().getEnvironment().getRiverBeds().size(); i++) {
			getWorld().getEnvironment().getRiverBeds().get(i).render(this);
		}
		for (int i = 0; i < getWorld().getEnvironment().getRivers().size(); i++) {
			getWorld().getEnvironment().getRivers().get(i).render(this);
		}
		// If there is no map-making happening, render the below things onto this unchanging tile image. 
		// Otherwise the GameWorld will render it so, for example, it changes position after it's moved around.
		if (GameFrame.getStaticGameFrame().getScriptFrame() == null){
			for (int i = 0; i < getWorld().getEnvironment().getEditableImages().size(); i++) {
				getWorld().getEnvironment().getEditableImages().get(i).render(this);
			}
			for (int i = 0; i < getWorld().getEnvironment().getEditableObstacles().size(); i++) {
				getWorld().getEnvironment().getEditableObstacles().get(i).render(this);
			}
		}
		
//		backImageGraphics2D.setColor(Color.BLACK);
//		backImageGraphics2D.drawLine(x, y, x+w, y);
//		backImageGraphics2D.drawLine(x+w, y, x+w, y+h);
//		backImageGraphics2D.drawLine(x, y, x, y+h);
//		backImageGraphics2D.drawLine(x, y+h, x+w, y+h);
		backImageGraphics2D.dispose();
	}
	
	public int getX(){
		return x;
	}
	
	public int getY(){
		return y;
	}
	
	public int getW(){
		return w;
	}
	public int getH(){
		return h;
	}

	public int getIndexX() {
		return indexX;
	}
	public int getIndexY() {
		return indexY;
	}

	public Graphics2D getBackImageGraphics2D() {
		return backImageGraphics2D;
	}
	public BBox getViewRectInWorldCoords() {
		return viewRectInWorldCoords;
	}
	public Point2D.Double getViewCenterInWorldCoords() {
		return viewCenterInWorldCoords;
	}

	public boolean isInitialised() {
		return initialised;
	}

	public TileGrid getTileGrid() {
		return tileGrid;
	}
	public GameWorld getWorld() {
		return getTileGrid().getWorld();
	}
	
	
}



Have a look at the Understanding Google Map server to see how google maps stores its images.

You should create quad-tree. Start off with a node containing the whole map (earth) at 256x256. Then split the node up recursively. One split will replace one 256x256 image with 4 256x256 images. When you move you may need to merge nodes as well. Kind of a bad explanation, but if you google for it you should get plenty of hits.

I made mandelbrot zoomer that uses this method. I’ve attached the code (it’s a zip file, extract to get the code). It uses java3D and I also think there is a Java2D version.