How to model irregular boundary of a 2D map in Game?

I am creating a map in a game, the map contains different countries, my question:

Q. How to model the irregular boundary of each countries? How to do quick country searching if I click on the map (given x,y values)?

The simplest way I can think of to do this is make the map into a finite grid or into an image and assign each location an enumerated value (or color). Each country would be a separate value on the map. Then given any xy index or coordinate you could quickly find out the country's value and look up its name in a table.

This depends entirely on your input data.

If all you have is a bitmap, then you'll need some bitmap data. You could paint a parallel image to your game map, but with block colors where the countries are. You'd want the image painted palletized, with each color representing a country. At runtime, load it uncompressed and trivially look up which color, and thus which country is under any given pixel by mapping your pick ray onto the image. If you're just displaying in 2D, it should be easy to map the screen coordinates to the map coordinates. This is a nice fast array lookup, and should be easy to author side by side with the visual map.

If you want to save some memory, it's highly likely that you could quarter this image and still have enough fidelity to feel precise picking countries near borders.

If you're modeling geometry for your countries, say you're making a nice 3D map, then you could just feed each country into a collision library like http://bulletphysics.org/ and just build a pick ray from the camera and collide it with the resulting optimized shapes. Which shape gets picked tells you which country was hit. It's highly likely that this would be fast enough for you, and again it would be easy to author side by side with your visual data.

• +1 for pointing out both a straightforward geometry-based and pixel sampling solution – ghost Apr 20 '11 at 5:50

The question is a bit vague, but, assuming you want to generate some irregular boundaried countries with a quick lookup function, here goes:

Take a very simple country lookup, I'm assuming you have some kind of capital city at the centre, assign the city a strength, then use an adjusted voronoi style map to produce the regular shaped country border map. that gets you something like this:

http://imgur.com/1hrBt

now, for the irregular borders, look at how perlin noise is used to offset into a different texture:

Perlin Noise

this should provide you with a quick way to generate the clean coordinates from the world coordinates. That then should provide you with a rough edged country map.

Without knowing any further constraints, I'd prefer using a BSP to find out which point of (2D) space belongs to which object. This works even with the country borders overlapping (simulating conflicts about the exact borders) or not filling out all the available space (simulating no-man's land and areas outside of the map's chosen projection).

use anchor points

This can be done exactly with using the collision detection from a physics engine and triangulated country shapes. However, I think the results will require lots of work that will be ultimately unsatisfactory.

You're best bet is to hand tune some anchor points. The basic idea is you place anchor points on the map. On user click find the anchor point that is the closest. That is the country you just selected.

Tips:

• add some null anchor points for areas that don't make sense to click.
This avoids surprising the user when the accidentally click on an ocean and suddenly select a country hundreds of miles away.I think you best shot will be to hand tune.

• The anchor points don't need to be fair.
Luxemburg would be very difficult to select. Adding some luxemburg anchor points into its neighboring countries will result in a better user experience.