Tile a board with randomly colored trominoes in C#

[example]

The post Tile a board with colored trominoes in C#explains how to color a tromino filing so no two adjacent trominoes share the same color. That example basically tried every possible color for each of the trominoes until it found one that worked.

Unfortunately, that approach makes the algorithm prefer colors near the beginning of the color list. That’s not a big problem with the trominoes because the tiling pattern requires the program to use a lot of colors, but the result can look strange when you color some other maps. In those cases, the coloring uses the first few colors the most and only occasionally uses the other colors. For example, the result might be a map that uses lots of yellow and blue areas and only one or two red areas.

This example examines the allowed colors in random order so it will use more of the colors that are later in the list of allowed colors. The program also uses more colors than the previous version, so the trominoes look more randomly colored.

The only change to the program is in the following code snippet where the program tries different colors for a tromino.

// Try each of the colors for this Chair.
Chair this_chair = Chairs[start_chair];
int[] color_nums =
    Enumerable.Range(0, Chair.BgBrushes.Length).ToArray();
color_nums.Randomize();
foreach (int color_num in color_nums)
{
    if (this_chair.ColorAllowed(color_num))
    {
        this_chair.BgBrushNum = color_num;
        if (FindColoring(start_chair + 1)) return true;
    }
}

This code creates an array named color_nums that contains the numbers 0, 1, 2, up to one less than the number of colors in the Chair.BgBrushes array. It then uses the Randomize extension method described shortly to randomize the color_nums array. The code then loops through the randomized colors and tries each until it finds one that works.

The following code shows the Randomize extension method.

// Randomize an array.
public static void Randomize<T>(this T[] items)
{
    // For each spot in the array, pick
    // a random item to swap into that spot.
    for (int i = 0; i < items.Length - 1; i++)
    {
        int j = Rand.Next(i, items.Length);
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
}

This method loops through the spots in the array. For each spot, it picks a random following spot and swaps the items in those two positions. When it is done, each of the array’s items may have been swapped into any of the array’s positions with equal probability.

See the previous example and download this example’s program to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, drawing, graphics, mathematics, recursion. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.