Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm currently working on a generator that generates rooms in biomes and i was wondering what is the fastest way of checking if a certain position is already occupied.

I've got 3 possible ways of doing this:

1. Use nested foreach loops to directly loop through all rooms and check the position. (ugh)

public bool IsOccupiedPosition(Vector2 position)
{
    foreach (Biome biome in this.Biomes)
    {
        foreach (Room room in biome.Rooms)
        {
            if (room.Position == position)
            {
                return true;
            }
        }
    }
    return false;
}

2. Use a List, put everything in there, then check that using the Contains() method.

public List<Vector2> RoomCoordinatesAsList { get; set; }

public void AddRoomCoordinates(Vector2 position)
{
    this.RoomCoordinatesAsList.Add(position);
}

public bool IsOccupiedPosition(Vector2 position)
{
    return this.RoomCoordinatesAsList.Contains(position);
}

3. Use a Dictionary, where the first type is the X position and the second a list of Y positions. (my preference)

public Dictionary<float, List<float>> RoomCoordinates { get; set; }

public void AddRoomCoordinates(Vector2 position)
{
    if (!this.RoomCoordinates.ContainsKey(position.X))
    {
        this.RoomCoordinates.Add(position.X, new List<float>());
    }
    this.RoomCoordinates[position.X].Add(position.Y);
}

public bool IsOccupiedPosition(Vector2 position)
{
    return (this.RoomCoordinates.ContainsKey(position.X) &&
        this.RoomCoordinates[position.X].Contains(position.Y));
}
share|improve this question

migrated from stackoverflow.com Sep 11 '11 at 23:17

This question came from our site for professional and enthusiast programmers.

    
It's used in a game. Any way to 'move' the question to gamedev? –  Rens2Sea Sep 11 '11 at 13:09
    
Nope :\ just flag it and wait –  Fire-Dragon-DoL Sep 11 '11 at 13:11
2  
Premature optimisation, much? How much data are you working with? If it's too much for a list to handle (option 1 and 2 are essentially the same) then you want to move to doing proper spatial partitioning (after you measure it and determine you have a performance issue). A simple grid is probably ideal (see Blau's answer). There are way too many things wrong with your third option to even begin to list them! –  Andrew Russell Sep 12 '11 at 0:23
3  
Also: you shouldn't be comparing floats using the == operator. And that includes comparing Vector2s, as they are made up of two float components. All of your listed options do this. –  Andrew Russell Sep 12 '11 at 0:26

1 Answer 1

up vote 5 down vote accepted
 bool[,] Rooms = new Rooms[Width, Height];

 bool IsPositionAvalaible(int x, int y) { return !Rooms[x,y];}

 bool SetPositionValue(int x, int y, bool Avalaible) { Rooms[x,y] = !Avalaible; }
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.