0
\$\begingroup\$

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));
}
\$\endgroup\$
  • \$\begingroup\$ It's used in a game. Any way to 'move' the question to gamedev? \$\endgroup\$ – Rens2Sea Sep 11 '11 at 13:09
  • \$\begingroup\$ Nope :\ just flag it and wait \$\endgroup\$ – Fire-Dragon-DoL Sep 11 '11 at 13:11
  • 2
    \$\begingroup\$ 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! \$\endgroup\$ – Andrew Russell Sep 12 '11 at 0:23
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Andrew Russell Sep 12 '11 at 0:26
5
\$\begingroup\$
 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; }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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