Finding a Position on a 2D Map that meets several criteria

Question

Hi,
as my personal project i develop a game to which users can join at any time. I have a tiled worldmap that is created from a simple Bitmap which has resources at random positions all over the map except for oceans.

When a player joins i want to create his starting position at a place that has at least 1 tile of each of the 4 resources in range (circle with a still to decide diameter, i think about 3-4 tiles) but no ocean tiles (Tile.Type != "ocean") and not conflicting with a field belonging to another player (Tile.Owner == null).

The map size can vary, currently it's 600x450 and it's implemented as a simple Array: Tile[][] with Tile.Resource being either null or having Tile.Resource.Type as a string of the resource name (as it's configurable by plaintext files to fit any scenery i want to put it in, so no built-in enums possible).

I currently have a loop that simple goes through every possible position, checks every field in range and counts the number of each resource field and discards it if there are none for one of them or if one of them belongs to a player or is an ocean field.

I would prefer if it finds a random position but thats not a requirement, mono-compatibility however is a requirement.

What would be the best way to implement an algorithm for that in C#?

Edit

The Area of players can and will increase/change and resources can be used up and may even appear randomly (=> "Your prospectors found a new goldmine") so pre-calculated positions will propably not work.

Answer 1

Instead of looping through all your positions, why don't you loop through all your resources? Your resources are likely to be more scant. Then pick one of the sets of resources that meet your clustering criterion.

Answer 2

Let's suppose that once your map is created you don't have to create a new one often.

Just add the following to each Tile and calculate them once after your map was generated:

-int NrOceanTiles
-int NrResourceA
-int ...

Now when you want to get a tile you can do it quite a bit faster:

IEnumerable<Tiles> goodTiles = tiles.Where(tile => tile.NrResourceA >= 1 && tile.NrResourceB >= 2);
Tile goodTile = goodTiles.ElementAt(randomI);

Answer 3

If the game isn't going to be designed for a huge number of players, most games implement "start spots" on the map. You'd hand-pick them and record the positions in your map somehow, probably similar to how you're implementing the map resources (i.e., on that spot, there exists an item you can pick up, but on top of the tile map).

Since the resources spawn at random, you could either not spawn resources on the start spots (which could be visible or not), or simply not spawn a player at a start spot on which there is a resource (or look within a 9-cell box to find a close alternate location).

Certainly you would want to hold the set of possible starting locations and update it as resources are created and consumed.

Answer 4

Predefined data would still be the best way forward.

As modifying the map size, and adding/losing resources would not happen as often, just update this data table when they do happen. Perhaps you could do the map/resource changes once per day, and have everything done in a daily database update.

In this way, finding a valid location would be far faster than any algorithm you implement to search all the tiles around it.

Answer 5

You might consider simulated annealing ... it's not very complex to implement. You have a set of criteria with certain weight, and randomly "shake" the position at a certain "temperature" (the higher the temp, the greater the radius the position may randomly move within, from it's previous position), then when it "cools" you measure the value of the position based on the total weights and subtract negative things, like spawning too close to where they died, or next to other players, etc..., if the value is not within a certain range, you decrease the temperature, but "shake" the positions again, cool down, check weights and overall value, repeat until you get an acceptable solution.

Simulated annealing is used in map making, to label cities and features with maximum clarity, while staying within range and minimizing overlap. Since it's a heuristic approach there is no guarantee that there will be an optimal solution, so you keep "lowering the temp" and eventually just choose the best result.

Answer 6

It seems like your best bet is to calculate open locations at map generation. Have your start location calculation function optionally take grid location and size or rectangle corners.

Have a list for Free locations and Occupied locations. Player occupies territory? Move resources in range to the Occupied list. Player gets crushed mercilessly? Move resources in range to the Free list. Resource eliminated? Delete any locations that used it in your Open/Occupied lists. Resource added? Recalculate using your effect radius to determine effected area. When your map area expands, just run the initial calculations on the new section of your grid + effect radius and add the new locations.

Then you just have to set the events up and pick a random Free value when someone joins.