Click here to Skip to main content
11,721,385 members (77,306 online)
Click here to Skip to main content

Client Side Crossword Generator

, 28 May 2014 CPOL 6.7K 265 11
Rate this:
Please Sign up or sign in to vote.
Overview of the structure and process of creating a crossword generator in JavaScript

Download js-xwords-1.0.1.zip

Introduction

As a part time English teacher I wanted something that could help me generate custom crossword puzzles for my students. There are many crossword generators already publicly available but few of them are developed for the web client and those I found didn't fully satisfy requirements.

Here are my requirements:

1. The application should produce a printable question grid (with little numbers like in the newspaper) and also the answers. Also, it needs to print the clues with the question grid.

2. It should run completely on the client side so that the miminum possible load is placed on the server.

3. The display and computational elements should be separated so that the computational part could be added in to an existing or a new design with minimal effort (ideally none!).

4. The interface should have some mechanism for making the crossword easier - for example randomly adding letters within the question grid - this would make the crossword easier for weaker students/groups.

5. Finally, it must be quick and easy to use - with the absolute minimum of clicking and typing.

Background Reading

I owe a huge debt to this previous article on Creating a Crossword Generator

And this book was very helpful with how to use the HTML5 Canvas element - though nothing in my code goes beyond the first two or three chapters of the book.

Online Demonstration

Although it is not required to understand the rest of this article you can see the code in action at http://demos.waystoskinacat.com/xWords/ where you can follow the instructions and try generating a custom crossword puzzle.

Overview

The code is separated into two files. The display code is in xWordsDisplay.js and xWords,js holds the main object xWords which creates, stores and provides access to the crossword puzzle.

The display code in xWordsDisplay is composed of a set of functions which respond to user actions on the HTML page and update the UI with the crossword produced by the xWords object.

The aim of this separation is that xWords.js is completely reusable in other websites or applications with no modification.

The display (xWordsDisplay.js)

The most important variables for the display are declared at the top of the file:

var GRID_SIZE = 25;         // size in pixels of each square in the crossword
var HORIZONTAL_BOXES = 15;  // number of horizontal crossword squares
var VERTICAL_BOXES = 15;    // number of vertical crossword square
var RUN_PROFILER = false;   // profiles the execution - google chrome
var REVEAL_LETTERS = 0;     // indicates percentage of the letters that
                        // will be revealed in the question grid 

The functions in the rest of the file either update these variables or use them to call functions on the xWords object. The most important of these functions is run. It draws the grid on both the question and answer canvases, makes calls to xWords to retrieve the question and answer data and then proceeds to draw them onto the respective canvas elements. Here is the section of code where it makes the call and retrieves the crossword data (in 2 dimensional arrays).

// GENERATE ARRAY OF WORDS TO PUT INTO THE CANVAS
var rawData = $('#txtWords').val();
var aValues = rawData.split('\n');

// GET THE CROSSWORD 
if (RUN_PROFILER) console.clear();
if (RUN_PROFILER) console.profile('xWords.Create()');

var crossword = xWords.Create(
      VERTICAL_BOXES,
      HORIZONTAL_BOXES,
      aValues);

if (RUN_PROFILER) console.profileEnd();

// GET THE GRID WITH NUMBERS
var qGrid = xWords.GetQuestionGrid();

The crossword generator (xWords.js)

The crossword generator is comprised of several objects:

  • xWords - the main object which generates the crossword
  • AlternativeGrid - stores details of a generated crossword so that they can be compared and the best one returned to the caller
  • Word - stores information about an individual word that it is trying to insert into the crossword
  • Position - stores information about a valid postion

Here is how they relate to each other:

The xWords object holds an array of Words which it is trying to place in the crossword.

xWords also maintains an AlternativeGrid which holds all the information needed to generate a crossword puzzle. Each time xWords tries to generate the crossword it stores its results in the alternative crossword if it is better than the current alternative crossword. Better is defined as the crossword which uses more of the provided words, if all the words are used then better is the crossword with fewest orphaned words (words not connected to the rest of the crossword puzzle - ideally there should be none!!!).

Each Word holds two arrays of possible positions that they can be inserted at. Crossing positions are those positions which involve it crossing other words already in the grid. Alternative positions are any valid positions where the word can fit into the grid. When a position is chosen it is always preferable to choose a crossing position. Here is the definition for the word object:

function Word(txt){
    txt = txt.trim();
    var pos = txt.indexOf(',');
    if ((pos > 0)&&(pos < txt.length - 1)){
        this.word = txt.substr(0,pos);
        this.clue = txt.substr(pos + 1);
    } else {
        xWords.sErrors += 'Missing clue: ' + txt + '<br/>'
        this.word = txt;
        this.clue = txt;
    }
    this.crossingPositions = new Array();
    this.availablePositions = new Array();
    this.orphaned = true;
    this.posIndex = -1;
    this.chosenPosition = null;
    this.ResetArrays = function(){
        this.crossingPositions = new Array();
        this.availablePositions = new Array();
    };
    
    this.Reset = function(){
        this.crossingPositions = new Array();
        this.availablePositions = new Array();
        this.orphaned = true;
        this.posIndex = -1;
        this.chosenPosition = null;
    };
} 

The most important function in the xWords object is the Create function. It resets the internal objects and then starts the main loop which runs until it either finds a solution or the time limit is reached (defined by the MAX_RUNTIME variable at the top of the object declaration). By default MAX_RUNTIME is set to 5 seconds.

Within the main loop it repeatedly tries to add the words to the crossword by making calls to the internal AddWord function.

for (var y = 1; y <= this.MAX_PASSES; y++){
    for (var x=0; x < this.Words.length; x++){
        if (((this.Words[x].orphaned)
            &&(this.Words[x].posIndex == this.UNSET))
            ||(y == 1)){
            this.Words[x].Reset();
            this.AddWord(this.Words[x],x,y);
        }
    }
} 

The MAX_PASSES variable is set to 3 by default and this indicates the number of times the code will try to place each word in an attempt. This is because some words can only be added after other words which come later in the Words array are placed in the crossword.

The AddWord function makes calls to GetPositions on each word to update the position arrays inside it and then places the word in the crossword if it is satisfied all the conditions are met.

Ongoing Development

Allthough I am satisfied the current version meets my initial requirements, I will continue to develop the code on GitHub. Various enhancements that I have thought of but haven't had time to implement so far are recorded in the issues section.

History

Version 1.0.1 - This is the first version with some minor fixes.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Richard Rulach
Software Developer waystoskinacat
United Kingdom United Kingdom
Full stack developer
Worked at various software houses for over 10 years.
Currently interested in developing educational software and websites.

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 5 Pin
Bill SerGio Jr.22-Apr-15 10:51
memberBill SerGio Jr.22-Apr-15 10:51 
GeneralMy vote of 5 Pin
gicalle753-Jun-14 10:56
membergicalle753-Jun-14 10:56 
GeneralMy vote of 5 Pin
Abinash Bishoyi28-May-14 19:06
memberAbinash Bishoyi28-May-14 19:06 
GeneralRe: My vote of 5 Pin
Richard Rulach28-May-14 21:00
memberRichard Rulach28-May-14 21:00 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150901.1 | Last Updated 29 May 2014
Article Copyright 2014 by Richard Rulach
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid