Friday, 20 March 2009

Building super fast, super portable mobile maps - Part Two - Getting Maps onto the Screen

So, I've got a client who wants mobile maps, and I've got a supplier of map tiles. I've signed up as a developer on CloudMade, got my API key and I can see tiles. Now I've got to get them on screen.

About a 40 years ago (ok, about 25 years ago maybe) I was working out how to get my Acorn Electron to play Chess. I was just hacking around more or less directionlessly, and I fell into a classic programming trap.

My thought process was: "A chessboard. That's an 8x8 grid. So I'll represent the board in memory with a two-dimentional array. 10 DIM BOARD[8,8]". This seems obvious, but it is not the easiest way to implement a grid where you want things to move from one place to another place, and it isn't too quick in implementation. For example, to calculate valid knight's moves becomes fairly complex. If I've got a knight at [2,0] then I need to try permuations of where it can go in both dimensions. If I created a board as a single dimension array (10 DIM BOARD[64]), then I know that valid moves are:

currentLocation + 6, currentLocation + 10, currentLocation + 15, currentLocation + 17 currentLocation - 6, currentLocation -10, currentLocation - 15, currentLocation - 17

provided that the result is between 0 and 64.

Similar decisions are needed when you create a map grid on a mobile phone. So, again I started with an assumption of having a 240x320 screen. If I imagined a grid of 6x6 squares for the map tiles, then that will give me a total grid size of 384x384 - enough to cover the whole screen, plus a margin all around so that when the user scrolls, the tiles are ready. If I create this grid as a single object array[36] then it makes life really easy when it comes to scrolling. More on this later.

So I created a class to represent a MapTile, a marshaller to handle the downloads, and a Widget to put the map on screen. The widget converted the location from the GPS (or location API) into a CloudMade tile reference, and then took this as a basis for calculating the references for all the other tiles.

Each MapTile is responsible for formatting a URL which will get the image from the CloudMade server. It requests a download from the marshaller, and in turn gets its image.

The widget then puts each image on screen as they are downloaded, building the map. It also handles the scrolling, where the smart decision about an array MapTile[36] pay dividends.

To put the map on screen, I need to know which tile is going into the top-left corner. I call this the 'origin tile'. When my map starts this is the tile at MapTileArray[0]. The tile with the actual location I want to see is MapTileArray[14], which is about the middle of the screen. I start by displaying MapTileArray[originTile] top left, and then rip through the array in order, adding 1 MOD 36 to get to the next tile. This means when I get to MapTileArray[35] and want the next tile, I know that the next tile is MapTileArray[0].

I also wanted it to prioritise which tiles to get first. I don't want it to start with the top left tile and work sequentially though. I wanted it to start with the tile which shows the relevant location and spiral out. Initially, I worked on an overly complex algorithm which will calculate the order that the tiles should be downloaded in at runtime. In the end, I got some common-sense together, and just set up the order in code. I add each of these values to the value of the origin tile, MOD 36, and that is the order of the tiles that I want.

If I'd gone with a two dimensional array, then I've got an array I want to reflect on screen. This means that a scrolling operation doesn't mean adding to subtracting either 1 or 6 (depending on the direction of the scroll), but I've got to switch all the tiles into different locations into the array to maintain its reflection of the screen. Massive pain.

So I can scroll my map around nicely, my array is working quickly and easily. Its a lot slower than Google Maps though, and I start to wonder why.

Part Three >>

No comments: