Structuring a Word Search Generator

• Download demo/source - 48.2 KB

Introduction

While in the midst of making a long pursued game, it occurred to me what I could do other than games, but similar. A couple of weeks back I had begun to learn Java and started making Java Applets. This brought me to think about all of those word search generators online (because of Java Applet capabilities) and I realized I wanted to explore the process of making one also.

Background

In this article I pursue the basic concepts of Custom Controls and classes, so an intermediate skill level would be recommended to understand the code, but if you just like to browse articles and test them, continue reading.

Using the code

To start off with a Windows Form application, I went ahead and started up a basic Windows Form application. I had an idea of the difficulty of the actual algorithm and created pseudocode alongside with it. (This is just the logic, we'll get to the placing and seeding for words later.)

function generate(Words)
{
    gridlength := maxlength(listofwords);
    while (successful)
    {
        notfound := false;
        foreach (word in list)
        {
            word->Location := Calculate(wordsplaced, word);
            if (Location == null)
            {
                notfound := true;
                break;
            }
            if (!notfound)
            {
                return FormGrid(words, locations);
            }
            else
            {
                gridlength++;
            }
        }
    }
}

Before starting the word structuring, I had to make a basic custom control. This control I decided would have access to displaying the grid, while I would assign the responsibility of generation to another class. When I was first making custom controls I was taught to start off with just graphics, but if you want an even further double buffer, you can always use the BufferedGraphics class file already pre-loaded. You'll see what I mean.

public partial class WordSearch : UserControl
{
    public WordSearch()
    {
        InitializeComponent();
        this.SetStyle(ControlStyles.OptimizedDoubleBuffer | 
          ControlStyles.AllPaintingInWmPaint | ControlStyles.UserPaint, true); //Subsitute
    }
    private Graphics graphics; //Could use BufferedGraphics
    
    protected override void OnPaint(PaintEventArgs e)
    {
        graphics = this.CreateGraphics(); //e.Graphics?
        //base.OnPaint(e); (For optimized buffer)
    }
}

We'll need another class file to hold place values to characters and locations. Letter maybe?

public class Letter
{
    public int X { get; set; }
    public int Y { get; set; }
    public char _Letter { get; set; } //Boo! Can't name property the same as Class
    public Letter(char letter, Point p )
    {
        this._Letter = letter;
        this.X = p.X;
        this.Y = p.Y;
    }
}

With a start to a double buffered control you can start to turn your psuedocode into C#! Since I didn't know where to start, I decided just by making a class for it, keeps you organized, and started structuring the basic code for options like uppercase with properties, etc. Which I already assume you know how to do, so let's continue on with our class. I started to introduce LINQ so don't get lost, there are lots of loops taking place because of the type of recursion that presents for directions and positions in the word grid.

//Foreach word in words set default length to max
//If needed we'll increase later.
int length = Words.Max(t => t.Length); 
while (true) //Loops until a solution is found, by increasing length each loop
{
    //Create filled list from Words
    List<string> left = new List<string>(Words);
    //Create empty list for words (Letter[])
    List<Letter[]> words = new List<Letter[]>();
    //Variable used for solution results.
    bool notfound = false;
    while (left.Count > 0)
    {
        //Calculate
        Letter[] next = Next(words.ToArray(), left[left.Count - 1], length); //We need logic!
        if (next == null) //No solution? exit loop.
        {
            notfound = true;
            break;
        }
        //Success! Add the word to bank
        words.Add(next);
        //Remove the word so we don't add it again!
        left.RemoveAt(left.Count - 1);
    }
    if (!notfound)
    {
        //Finalize Words to grid (Essentially a character grid without answers)
        char[,] without = From(words.ToArray(), length); 
        this.lastlength = length; //Don't forget to set lastlength!
        this.answers = words.ToArray(); //Don't forget to set answer key!
        this.lastgrid = without; //Don't forget to set lastgrid!
        return Fill(without); //Finially fill the grid with random letters in the empty spots.
    }
    //Oh no! Increase the length of the grid size.
    length++;
}

There is not much to it. Besides that all we need is some good word placing logic and organization. These last methods are the core, the seeding and placing. For these methods most of the explanation would be better placed inside the code. These ones took me a while. Please note, the while(list.Count > 0) are there because we don't want to always go in a linear loop. Otherwise generation would bring the same results every time! > /p>

private Letter[] Next(Letter[][] letters, string word, int length)
{
    List<Point> all = new List<Point>(AllPoints(length));
    while (all.Count > 0)
    {
        int index = rand.Next(0, all.Count);
        List<Direction> dirs = new List<Direction>(AllDirections());
        while (dirs.Count > 0)
        {
            int index2 = rand.Next(0, dirs.Count);
            Direction current = dirs[index2];
            Letter[] c = Construct(all[index], current, word, length);
            bool legal = true;
            for (int i = 0; i < c.Length; i++)
            {
                if (c[i].X < 0 || c[i].X >= length || c[i].Y < 0 || c[i].Y >= length)
                {
                    legal = false;
                    break;
                }
                else
                {
                    for (int j = 0; j < letters.Length; j++)
                    {
                        Point[] pts = letters[j].Select<Letter, Point>(t => new Point(t.X, t.Y)).ToArray();
                        int _index2 = pts.ToList().FindIndex(t => t.X == c[i].X && t.Y == c[i].Y);
                        if (_index2 != -1) //Do letters intersect?
                            if (c[i]._Letter != letters[j][_index2]._Letter)
                            //Are the letters the same at intersection?
                                legal = false;
                    }
                }
            }
            if (legal)
                return c;
            dirs.RemoveAt(index2);
        }
        all.RemoveAt(index);
    }
    return null;
}

Things to Manipulate/Add

During the project, I realized that I could incorporate a difficulty setting. I thought about setting a difficulty based on the range of letters used to scramble. For example the words: dog, cat with an example difficulty of two might use the letters c, d to fill with.

Points of Interest

During the project I did not learn anything except fulfilling my ideas and not give in to my weakness of deletion!