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\$
4
  • \$\begingroup\$ It's used in a game. Any way to 'move' the question to gamedev? \$\endgroup\$
    – Rens2Sea
    Commented Sep 11, 2011 at 13:09
  • \$\begingroup\$ Nope :\ just flag it and wait \$\endgroup\$ Commented Sep 11, 2011 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\$ Commented Sep 12, 2011 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\$ Commented Sep 12, 2011 at 0:26

1 Answer 1

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\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .