Sunday, June 14, 2015

Game-development Log (14. CDN Improvements)


I haven't been really active on the development of this project as I've been occupied with other stuff. Regardless, I'm now focused on returning to active development on it.

Interestingly enough what actually triggered my return was a couple of Azure announcements last week on the CDN front. First, some context:

Although I like Azure quite a lot its CDN offering has been quite lacking to say the least. The community was quite vocal in requesting some essential features but Microsoft neglected to provide any updates or expected delivery dates, as seen here: http://feedback.azure.com/forums/169397-cdn

For example, the top voted feature request was the ability to force content to be refreshed, which is, IMHO, completely essential for a CDN offering:

http://feedback.azure.com/forums/169397-cdn/suggestions/556307-ability-to-force-the-cdn-to-refresh-any-cached-con

The feature was requested 5 years ago, eventually marked as "planned", and no further update was provided by Microsoft, similarly to the other requested features.

Well, all of this until last week, when Microsoft apparently woke up.

First they've provided feedback on most of the feature requests and provided an expectation around release dates. Not ideal (as most of these features are late by a few years) but positive nevertheless.

Then, the icing on the top of the cake was this post:

https://azure.microsoft.com/blog/2015/06/04/announcing-custom-origin-support-for-azure-cdn/

Basically Microsoft shipped three awesome features for the CDN:

I'll just copy&paste from that post:
Custom Origins Supported
Azure CDN can now be used with any origin. Previously, Azure CDN only supported a limited set of Azure Services (i.e. Web Apps, Storage, Cloud Services and Media Services) and you only had the ability to create a CDN endpoint for an Azure Service that was in your Azure Subscription. With this recent update, you can now create a CDN endpoint for any origin you like. This includes the ability to create an origin in your own data center, an origin provided by third party cloud providers, etc. and gives you the flexibility to use any origin you like with Azure CDN!
Multiple CDN Endpoints with the Same Origin
Several of you may have tried to create multiple CDN endpoints for the same origin and found this wasn’t possible due to restrictions. We have now removed the restrictions and you now have the ability to create multiple endpoints for the same origin URL. This provides you a more refined control over content management and can be used to improve performance as multiple host names can be used to access assets from the same origin.
Save Content in any Origin Folder
Previously, when you created a CDN endpoint for cloud services you were required to use “/cdn/” as the default origin path. For example, if the path for your cloud service washttp://strasbourg.cloudapp.net you were required to use http://strasbourg.cloudapp.net/cdn/ as the root path to get content from your origin when you created a CDN endpoint. This restriction has been removed and you can store content in any folder. Using the previous example, you can now use http://strasbourg.cloudapp.net/as the root path to get content from your origin.
These might seem minor changes but let me explain how they positively affect this project:

Sunday, May 3, 2015

Using Genetic Algorithms to solve the Traveling Salesman Problem on Bing Maps

A couple of years ago I was really into Genetic Algorithms and Ant Colony Systems, mostly focusing on solving known NP-Complex problems such as the TRP (Traveling Salesman Problem) and the VRP (Vehicle Routing Problem).

As I have a couple of interesting use-cases that could benefit from these types of algorithms what better way to refresh my knowledge than making a simple mapping experiment solving the TRP problem?

Here's a short summary of these concepts:
  • TRP - Optimization problem that tries to find the shortest route that passes on all supplied points
  • Genetic Algorithm
    • There's a population were each element represents a solution to the problem
    • The algorithm progresses through various iterations, called generations
    • On each generation the various elements of the population mate and create new elements
    • The fittest elements survive and the weakest die
It obviously has much more going on than that, including stuff like roulette selection, mutation, elitism, etc.

I'll create a map where the user can input waypoints and the algorithm will find the shortest path.

Saturday, March 21, 2015

Improve tile-loading at the browser

Slippy Map, such as Bing Maps or Google Maps, is composed of multiple tiles. Each tile, typically a 256x256 image, is individually fetched from the server.

As displays are now supporting incredibly high resolutions, this means that tons of server requests will be required to fill a single map view. For example, on my laptop with retina display, opening a single full screen map will result in about 48 individual tiles being requested simultaneously.

This is a problem as by default web browsers will limit the number of active connections for each domain. This value varies per browser, but we're talking about an average of 6 concurrent downloads per domain, which is quite low. So, assuming all tiles are served from the same domain, lots of throttling will occur.

So, how to cope with this?

1. Tile Size

If you control the tile generation process a "simple" option will be to generate bigger tiles, hence reducing the number of requests. Bing Maps, for instance, supports setting different sizes for the tiles (reference).

For example, setting the tile size to be 512 instead of 256:

var MM = Microsoft.Maps;
var map = new MM.Map(document.getElementById("mapDiv"), {
    center: new MM.Location(45.0, 10),
    zoom: 5,
    credentials:"your key here"});

var tileSource = new MM.TileSource({
    width: 512,
    height: 512,
    uriConstructor:  function(tile) {
        return "images/square512.png";              
    }});

    var tileLayer = new MM.TileLayer({ mercator: tileSource});
    map.entities.push(tileLayer);
In this particular case we're talking about 15 tiles being requested (albeit each one being bigger), which is a big difference from the previous 48.

2. Serve tiles from different urls

A technique called domain sharding can be also be used, on which different domains are used to fetch the same information, thus bypassing the "same-domain" browser limitation.

A good example of this can be seed on Bing Maps, as it's using this technique to speed up serving the tiles.

Taking a look at the web-traffic for the base tiles we can see 4 different hostnames being used:

  • https://t0.ssl.ak.dynamic.tiles.virtualearth.net
  • https://t1.ssl.ak.dynamic.tiles.virtualearth.net
  • https://t2.ssl.ak.dynamic.tiles.virtualearth.net
  • https://t3.ssl.ak.dynamic.tiles.virtualearth.net

The corresponding hostname is determined by the last digit of the quadkey that identifies the tile. For example, tile 0331 will use t1, tile 0330 will use t0, and so on.

Monday, March 16, 2015

Game-development Log (13. Polishing the experience)


Although I haven't been really active on my blog I've been playing a lot with this project adding tons of new stuff. I'm going to detail the various elements that I've updated/implemented during the last month:
  • Pre-Generating additional Zoom Level images
  • Representing Altitude
  • Unit Energy
  • Unit Direction
  • Unit LOD Icons
  • Infantry Unit Type
  • Movement Restriction
  • Coordinate display on higher zoom levels

Tuesday, February 3, 2015

Displaying 3d objects on Bing Maps (using Three.js)

On my previous post I've made a couple of experiments on displaying 2d content on top of Bing Maps using Pixi. Performance was top-notch, particularly if the browser supported WebGL (fallbacking to Canvas otherwise).

This time I'm trying to take the WebGL experiment even further by adding 3d content on top of a map. For that I'm going to use the most popular WebGL 3D lib out there: Three.js

Let me start by showing the end-result.


I've placed some boxes on top of a map. Although the map by itself is 2D the boxes are rendered in 3D using WebGL. Thus, as further away from the screen center (the vanishing point) the more pronounced the depth effect will be.

Tuesday, January 6, 2015

Displaying WebGL on Bing Maps (using Pixi.js)

Something that has been on my backlog for some time is trying to mix Bing Maps and WebGL, similarly to what I've done for an "old" Google Maps experiment.

That previous demo was done on top of a Google maps sample, hence just requiring some small tweaks and improvements. Also, was very low-level and not really practical to adapt to more "real-world" usage, as it required programming the shaders, computing the transformation matrixes, etc.
Thus, I was trying to find a alternative WebGL JS lib that was:
  • Fast
  • Easy to use, albeit still providing some low-level control, namely on primitives drawing
After some research I ended up with two candidates:
IvanK Lib is pretty good (and fast) but Pixi.js takes the cake with tons of functionality and a large community using it.

I'm going to enumerate the various experiments I did, showing a sample page for each.

Thursday, January 1, 2015

Game-development Log (12. Scaling up the loader process)


During the last month I've been mostly refactoring the loader process. As it was I had lots of trouble loading larger areas. I've detailed the problem (and the solution) on a previous post. I've also optimized the loading process and I'm able to load the whole world in about 1 day, already including pre-generating the lower zoom level images.

Regardless, I've haven't yet imported the whole world as everything is still work in progress. I'm planning to add some additional stuff to the map, like mountains, regions, cities and overall improved aesthetics.

I've currently imported to Azure a rectangle that goes from coordinate [15E 60N] to [15W 30N]. Basically this area:


If you zoom in inside this area the Bing Maps tiles are replaced with my own (after zoom level 7). For example, zooming in into London:


Or a random area on Norway:

Or B├ęchar in Algeria:

The most important thing to note is that those hexagons are not simply cosmetic. All information is being pushed to client-side so that the units will behave differently depending on the terrain. For example, a tank can only cross a river through a bridge:


I've also added:
Deserts
Two levels of forests: dense and sparse

Anyway, you can play around with it at: https://site-win.azurewebsites.net/