Searching a C# Array with LINQ

In the last chapter, we added some extra detail to our roguelike game map by specifying separate class properties for the map elements, the items on the map and the characters walking the map. This will actually make searching the map easier. In the classic Rogue game, there are scrolls that will look for any food or enchanted items on the current level. You’ve already seen how to search the map using a nested loop and by poking it at random but there’s actually a way to query the entire map contents or other collections at once for specific items and that’s by using Language INtegrated Query (LINQ) syntax.

This post is part of a series on creating a roguelike game in C#. For the latest chapters and more information, please visit the Official Project Page on ComeauSoftware.com. The current code for this project is also available on Github.

What is LINQ?

LINQ is a set of query tools that has been part of .NET since 2007. In simple terms, it’s meant to provide a consistent way to search and manipulate many types of data in C#, from arrays to collections like generic lists and datasets retrieved from databases like SQL Server.

If you want more background on LINQ itself and some extra demos, I recommend this Microsoft Learning video for an overview and some of the extra resources at the end of the article. Meanwhile, I’m going to demonstrate how to use it to query a two-dimensional database like the one we’re using to hold the map content in the game.

Querying the Map

In previous chapters, we needed a way to find an open space within one of the map rooms to place a gold deposit or the player object. This meant searching randomly for an unoccupied space within a room, like this code from the PlaceMapCharacter() function:

while (!freeSpace)
{
    xPos = rand.Next(1, MAP_WD);
    yPos = rand.Next(1, MAP_HT);

    freeSpace = (levelMap[xPos, yPos].MapCharacter == ROOM_INT)
        && levelMap[xPos, yPos].DisplayCharacter == null
        && levelMap[xPos, yPos].ItemCharacter == null;
}

It worked well enough because C# is so fast but it’s inefficient. What if there was a way to instantly return a list of the spaces that are open and select a random space from those? LINQ provides this – let’s start with the basic syntax for a LINQ query:

var spaces = from space in levelMap 
                where space.MapCharacter == ROOM_INT
                && space.ItemCharacter == null
                && space.DisplayCharacter == null
                select space;

We’ll need a couple changes before it works with the array but I wanted to show you the basic syntax first. This is an example of LINQ’s query syntax which is similar to SQL in its use of clauses like from, where, and select although it puts select at the end instead of the beginning. The line breaks shown here are not necessary but I put them in for readability.

The var declaration on the first line indicates that LINQ isn’t immediately concerned with the type being represented. It’s accepting whatever’s contained in the collection and inferring or guessing at the type. The first line then uses a variable to refer to each object in the collection which, in this case, is our array.

The next three lines provide the criteria for our selection using the object properties of the data in the array. Intellisense will actually see these properties since all the array elements contain MapSpace objects.

Then, the final line selects and returns whatever items meet the criteria.

With multidimensional arrays, however, there’s a slight difference:

var spaces = from MapSpace space in levelMap 
                where space.MapCharacter == ROOM_INT
                && space.ItemCharacter == null
                && space.DisplayCharacter == null
                select space;

LINQ is not equipped to search more than one dimension of the data and infer the type at the same time so it needs a little help. The MapSpace declaration on the first line specifies how the data in each element is to be treated and enables the query to proceed. Now we have a new object that implements the IEnumerable interface which is a set of methods that enables C# to loop through a collection of items like this one.

At this point, we can’t really do anything with the spaces object other than apply additional LINQ operations because it’s not in a specific type of collection so we need to cast it to one.

List<MapSpace> spaces = (from MapSpace space in levelMap 
                where space.MapCharacter == ROOM_INT
                && space.ItemCharacter == null
                && space.DisplayCharacter == null
                select space).ToList();

This throws the entire collection of objects into a list that we can select from as needed using a syntax like this line that would take the first item from the list.

MapSpace first = spaces[0];

We need to do a bit more than that, though. Let’s see what this does for the PlaceMapCharacter() function.

MapSpace select;         

// Select random space from array.
List<MapSpace> spaces = (from MapSpace space in levelMap 
                where space.MapCharacter == ROOM_INT
                && space.ItemCharacter == null
                && space.DisplayCharacter == null
                select space).ToList();
            
select = spaces[rand.Next(0, spaces.Count)];

// If the character is for the player or a monster, add
// it to the Display character. Otherwise, use the item character.
if (Living)
    select.DisplayCharacter = MapChar;
else
    select.ItemCharacter = MapChar;

return select;

Instead of randomly poking the map trying to find an available space, we now have a list of available spaces and we can simply select one at random using the count of the list’s items as the high number in the Random.Next() function and then work with it as needed.

Is it faster? It seems like it should be but I haven’t tested it and, in this context it doesn’t make much difference since this function won’t be run 2000 times in a row like others we’ve seen. It does simplify the code, however, which is always nice. It also leads to some handy refactoring.

public List<MapSpace> FindOpenSpaces(bool hallways)
{
    // Return a list of all open spaces on the map by checking the
    // map character.
    string charList = hallways ? 
    (HALLWAY.ToString() + ROOM_INT.ToString()) : ROOM_INT.ToString();

    List<MapSpace> spaces = (from MapSpace space in levelMap where
                            charList.Contains(space.MapCharacter)
                            && space.ItemCharacter == null
                            && space.DisplayCharacter == null
                            select space).ToList();

    return spaces;
}

Now I have a dedicated function that can return a List of all the available spaces any time I need it and can include hallway spaces if necessary. This can replace the LINQ statement in the PlaceMapCharacter() function. Notice that it’s also public so it’s available to the Game class and other classes. Let’s put it to work.

private void AddStairway()
{
    // Search the array randomly for an interior room space
    // and mark it as a hallway.
    List <MapSpace> openSpaces = FindOpenSpaces(false);
    MapSpace stairway = openSpaces[rand.Next(openSpaces.Count)];
    levelMap[stairway.X, stairway.Y] = 
        new MapSpace(STAIRWAY, stairway.X, stairway.Y);
}

That certainly made placing a stairway on the map simpler.

More Search Functions

As our player starts traveling the map, it’s important to be able to see all the surrounding spaces at any given moment since some items only remain visible when the player is near them. LINQ gives us an easy way to do this. This function accepts coordinates and looks for any spaces on the map where the X and Y is only offset from those coordinates by one at the most.

public List<MapSpace> GetSurrounding(int x, int y)
{
    // Return a list of all spaces around given space in eight directions.

    List<MapSpace> surrounding = (from MapSpace space in levelMap
                                where Math.Abs(space.X - x) <= 1
                                && Math.Abs(space.Y - y) <= 1
                                select space).ToList();

    return surrounding;
}

Then there are a couple of functions to find all occupants such as the player and any monsters and to find all items such as gold and other collectibles.

public List<MapSpace> FindAllOccupants()
{
    // Return a list of all monsters and the player by checking the
    // display character.

    List<MapSpace> occupants = 
        (from MapSpace space in levelMap
             where space.DisplayCharacter != null
             select space).ToList();

    return occupants;
}

public List<MapSpace> FindAllItems()
{
    // Return a list of all items on the map by checking the
    // item character.

    List<MapSpace> items = 
         (from MapSpace space in levelMap
              where space.ItemCharacter != null
              select space).ToList();

    return items;
}

Our game map just became a lot more capable.

Eliminating Steps

As a final example, there’s the VerifyMap() function which verifies that all the rooms on the game map are accessible by looking for rows or columns in the array that have only empty characters. Here’s the original code it used to check just for blank rows:

dirCheck.Clear();
for (int x = 0; x <= MAP_WD - 1; x++)
{
    if (!dirCheck.Contains(levelMap[x, y].MapCharacter))
        dirCheck.Add(levelMap[x, y].MapCharacter);
}
retValue = dirCheck.Count > 1;
if (!retValue) { break; }

It has to manually clear the list it’s using to get the unique characters in the row, loop through and assemble the list of characters and then count the number of unique characters. Compare this to a LINQ operation:

dirCheck = (from MapSpace space in levelMap
                where space.X <= MAP_WD
                && space.Y == y
                select space)
                .Select(c => c.MapCharacter)
                .Distinct().ToList();

retValue = dirCheck.Count > 1;
if (!retValue) { break; }

With LINQ, you can chain operations as shown above. The main LINQ statement is in parentheses and then the Select and Distinct methods further refine it. That one statement redefines the list so it doesn’t have to be manually cleared. Then it does the following:

  1. Limits the collection to the coordinates needed
  2. Selects just the MapCharacter property from each item using a lambda expression
  3. Limits the collection to unique characters
  4. Outputs it to a list.

Then, all that remains is to count the number of items as before.

Exploring Further

Just from these examples, you should be able to see the power that is available through LINQ and that it’s an important part of the C# language. You’ll probably see more about it in this series but if you can’t wait to see more, here are a few links to learning resources.

C# Fundamentals for Absolute Beginners – Working with LINQ (Video)

Understanding the .NET Language Integrated Query (LINQ)

Introduction to Language Integrated Query (LINQ) (Video Series)