Продолжим написание игры начатой в первой части. Для тех кто хочет просто поиграть вот вам сылка
Как и в прошлой статье в основном все пояснения буду давать в коде как комментарии.

Поиск линий

По правилам игры линия считается собранной, если по диагонали, вертикали или горизонтали вместе набрано не меньше пяти шариков, чтобы нам можно было легко изменять условия игры константы, будем брать из переменных. Т.к. у нас все изменение игривого поля происходят относительно одного шарика, поэтому нам не нужно проверять все поле. Вокруг одного шарика может собраться только четыре линий.

Нам нужно пройтись по всем линиям и подсчитать в них шарики одного цвета относительно исходного. Вот собственно код, эту функцию надо добавить в класс Game
/**
* Поиск собранных линий
* @param Начальный шарик
*/
searchLines:function(sBall)
{
  var color = sBall.color;  // Будем считать шарики этого цвета
  var x0 = sBall.cell.x,y0 = sBall.cell.y;  // Начальные координаты
  var t = [  // Направление сканирования
    [1,0],  // вправо
    [1,1],  // верх-вправо
    [0,1],  // верх
    [1,-1]  // вниз-вправо
  ];  // Все остальные направление это зеркальное отображение этих
  var lines = []; // Здесь мы будем хранить линии удовлетворяющие условиям
  // Пройдемся по всем направлениям.
  for(var i=4;i--;)
  {
    var p = t[i], // Выберем текущее направление
      ball,    // Это у нас текущий шарик
      line=[sBall], // Создадим новую линию, и запишем туда стартовый шарик, он вед нужного цвета :)
      count=1,  // Количество шаров одного цвета в линии, пока он один
      x = x0,y = y0,  // Координаты текущего шара
      dx = p[0],dy = p[1]; // Направление движения, мы будем каждый раз изменять координаты на эти значения
    // Ну и теперь пробежимся по линиям и подсчитаем шарики одного цвета, если встретили шар другого цвета то выходим из цикла
    do
    {
      x = x+dx,y = y+dy;  // Переходим на следующий шар
      var index = this.getIndex(x,y);  // Получаем его индекс в массиве, -1 если вышел за предела поля
      // Следующей строчкой мы проверяем
      if(index>=0)
      {
        ball = this.cell[index].getBall(); // Достанем шар из ячейки
        if(!ball || ball.color!= color) break; // Если нет шарика или цвет другой то выходим
      }
      else
      {
        break;
      }
      /*
        Предыдущие 9 строчек можно заменить на одну, но так понятнее :)
        if(index<0 || !(b = this.cell[index].getBall()) || b.color!= color) break;
      */
      line.push(ball); // Добавим шар в линию
      count++;  // Увеличим количество шаров
    }while(count<this.minline); // это на всякий случай чтоб не за цыклилось, а если вы немного подумаете поймете почему не может быть больше шаров в одном направление
    // Половина линии мы подсчитали теперь вторая
    x = x0,y = y0,  // Вернемся в начало
    dx = -p[0],dy = -p[1],  // инвертируем направление
    count = 1  // Сбросим счетчик
    // А теперь копипаст. А почему именно копипаст? А чтобы не тратить время на вызов функции.
    do
    {
      x = x+dx,y = y+dy;  // Переходим на следующий шар
      var index = this.getIndex(x,y);  // Получаем его индекс в массиве, -1 если вышел за предела поля
      // Следующей строчкой мы проверяем
      if(index>=0)
      {
        ball = this.cell[index].getBall(); // Достаём шар из ячейки
        if(!ball || ball.color!= color) break; // Если нет шарика или цвет другой то выходим
      }
      else
      {
        break;
      }
      /*
        Предыдущие 9 строчек можно заменить на одну, но так понятнее :)
        if(index<0 || !(b = this.cell[index].getBall()) || b.color!= color) break;
      */
      line.push(ball); // Добавим шар в линию
      count++;  // Увеличим количество шаров
    }while(count<this.minline); // это на всякий случай чтоб не за циклилось, а если вы немного подумаете поймете почему не может быть больше шаров в одном направление
    if(line.length>=this.minline) lines.push(line);  // А теперь если длина линии больше или равна минимальной добавим ее в массив линий
  }
  return lines;
}
 

Подсчет балов

Линии мы нашли, осталось подсчитать количество балов за них. Мы будем за каждый шарик в линии давать по балу, запишем этот параметр в переменную costBall. И чтобы было играть более интереснее, за сложные конструкции будем давать больше балов. Формула расчета будет вот такой:

Балы за ход = количество шариков в линиях* costBall*количество линий;

Добавим новый метод к игре. Он будет посчитывать балы и сразу удалять шарики.


/**
* Удаление линий и подсчет балов
* @param Массив линий
*/
clearLines:function(lines)
{
  var score = 0;  // Для хранения балов
  for(var i=lines.length;i--;)
  {
    var line = lines[i]; // Достаним очередную линию
    for(var j=line.length;j--;)
    {
      var ball = line[j];  // достаним шарик
      ball.remove();  // и удалим его
      score += this.costBall; // приплисуем количество балов доваемое за шарик
    }
  }
  this.score += score*lines.length; // Увеличим количество балов на количество линий, чтобы играть было интересней. И добавим к общему счету
  this.callEvent('onchangescore',[this.score]); // Сообщим то что счет изменился
}
 

Можно заметить, что вставляемый шарик удаляется несколько раз для каждой из линий, в javascript`е это не страшно т.к. мы просто обнуляем переменные, разрывая связи, чтобы сборщик мусора их удалил, для других языков как Си нужно будет проверять. Теперь нужно эти методы, где то вызвать. Немного изменим метод selectCell

Посмотрим что у нас получилось

Исходники Продолжим создание игры цветные линии.

Волновой алгоритм поиска пути.

Для нахождения пути есть много разных алгоритмов. Мне больше нравится волновой алгоритм, его еще используют для трассировки плат. Плюсы алгоритма:

1. Находит самый короткий путь.
2. Если путь существует, то он обязательно его найдет.

Минусы алгоритма:

1. Очень медленный
2. Расходует много памяти

Для нашей игры он самый оптимальный не смотря на минусы. Игровое поле очень мало, по этому памяти не так много нужно. Выполняется один раз за ход игрока, потерю в скорости он не заметит. Этот алгоритм заключается в том, что из конечной точки пути испускается волна в четырёх или в восьми направлениях, зависит от того может ли предмет перемещаться по диагонали. У нас перемещение возможно только вертикали и горизонтали, поэтому волна у нас буде в 4 направления.

Алгоритм.

1. Создаем дополнительный массив размерностью равным игровому полю;
2. Записываем по координатам конечного пункта 1;
3. Записываем по координатам начального пункта -1;
4. Присваиваем номеру волны 1;
5. Ищем ячейки, в которых записан номер волны;
6. Смотрим что в соседних клетках {0,1},{1,1},{1,0},{0,0}, если -1 (начало пути ) значит путь найден и переходим прохождению этого пути 8, если по этим же координатам на карте есть препятствие ставим -2, если клетка пуста тогда ставим {номер волны +1 };
7. Увеличиваем номер волны на единицу и переходим к пункту 5;
8. Проходим из начального пункта ступая на клетку, где номер волны наименьший;

Вот и сама реализация:
/**
*  Строит карту пути
*  @param Координата начала пути по оси X
*  @param Координата начала пути по оси Y
*  @param Координата конца пути по оси X
*  @param Координата конца пути по оси Y
*  @param Масси координат пути
*/
getTraceMap:function(x0,y0,x1,y1)
{
        var tempMap = []; // Временный масив
        tempMap[this.getIndex(x0,y0)] = 1; //начало пути
        tempMap[this.getIndex(x1,y1)] = -1; //конец  пути
        var w = 1; // Волна
        for(var i=this.cell.length;i--;) if(!this.cell[i].isBall()) this.cell[i].dom.innerHTML = ''; // для демонстрации волны
        function testCell(x,y,w) // Тестирует клетку и записывает о ней иформацию во временный массив
        {
                var i = this.getIndex(x,y);
                if(i>=0) // За пределами игравого поля клетки нас не интересуют
                {
                        var c = tempMap[i];
                        if(c == -1)
                        {
                                tempMap[i] = w+1; // мы нашли конец пути, запишим туда очередную волну и выйдем
                                return true;   
                        }
                        if(!c && i in this.cell)        // Если клетка времменного массива пуста и есть такая ячека игравого поля
                        {
                                if(this.cell[i].isBall()) // В этой ячеки стаит шарик то записываем -2
                                        tempMap[i] = -2;
                                else
                                {
                                        tempMap[i] = w+1;       // Иначе на еденицу больше волны
                                }
                        }
                }
        }
        function waveItem(w)
        {
                for(var x=this.width;x--;)
                {
                        for(var y=this.height;y--;)
                        {
                                var i = this.getIndex(x,y);
                                if(i>=0 && tempMap[i] == w) // Если мы в области игравого поля и в клетке времменного массива записан номер волны
                                // тогда проверим соседнии клетки
                                {
                                        if(testCell.call(this,x+1,y,w)
                                                || testCell.call(this,x-1,y,w)
                                                || testCell.call(this,x,y+1,w)
                                                || testCell.call(this,x,y-1,w)) return true; // если нашли путь вернем карту пути
                                }
                        }
                }
        }
        while(w<1000) // Ограничем ее на всяки случай
        {
                if(waveItem.call(this,w)) return tempMap;
                w++;    // Увеличим волну на еденицу
        }
}
 

Карту сайта мы получили теперь нужно проложить путь. Делается это очень просто. Начиная с финишной точки, проверяем соседние клетки и переходим в клетку, в которой номер волны меньше чем в текущей, и повторяем это пока не достигнем старта, по пути сохраняя координаты.


/**
*       Прокладывает путь
*       @param Координата начала пути по оси X
*       @param Координата начала пути по оси Y
*       @param Координата конца пути по оси X
*       @param Координата конца пути по оси Y
*       @param Массив индексов ячеек пути
*/

searchTreck:function(x0,y0,x1,y1)
{
        var map = this.getTraceMap(x0,y0,x1,y1); // построим карту пути
        if(map)
        {
                var x=x1,y=y1; // Начнем прокладывать путь с конца, из финиша
                var t=[[1,0],[-1,0],[0,1],[0,-1]]; // Четыре направления для просмотра соседних клеток
                var i = this.getIndex(x,y); // Получим индекс
                var track = [i]; // Здесь мы будем хранить индексы пути и начнем с финиша
                while(map[i]!=1)        // Проходим путь пока не достигнем начала (ячейка в карте с еденичкой)
                {
                        var wc = map[i];        // Номер волны в текущей ячейке
                        for(var j=0;j<4;j++) // Найдем ячейку, у которой номер волны меньше чем у текущей
                        {
                                var p = t[j]; // Направление
                                var i2 = this.getIndex(x+p[0],y+p[1]); // Получим индекс соседней клетки
                                if(i2>=0) // Проверим находится ли она в зоне поля
                                {
                                        var w = map[i2]; // номер волны соседней ячейки
                                        if(w>0 && w<wc)
                                        // Проверим чтобы поле было свободно и номер волны меньше чем в текущей тогда переходим в эту ячеку
                                        {
                                                x = x + p[0]; // Новые координаты
                                                y = y + p[1];
                                                i = i2; // Новый индекс
                                                track.push(i);  // Запомним его в пути
                                                break;
                                        }
                                }
                        }
                }
                return track; // Вернем путь по нему мы будем строит анимацию
        }
        return false
}
  Пример, попробуйте переместить элемент.

Путь мы нашли, карту пути мы построили теперь можно перемещать шарик. Для большего эффекта мы шарик переместим на финиш постепенно, из клетки в клетку, делая при этом задержку. Сначала изменим функцию выбора ячейки selectCell .


/**
* Функция выбора ячейки
*/
selectCell:function(cell)
{
        if(!cell.isBall() && this.seletedBall) // Если в ячейке нет шарика и есть выделенный
        {
                // Найти путь
                var track = this.searchTreck(this.seletedBall.cell.x,this.seletedBall.cell.y,cell.x,cell.y);
                if(track)
                {
                        this.startMoveAnime(track); //  Начать перемещение
                }
                else
                {
                        // если путь не нашли то сообщим об этом
                        alert("Ход не возможен");
                }
        }
        return false;
}
 

Добавим теперь метод перемещения startMoveAnime. В ней будет локальная безымянная функция которую мы сразу запустим. Она будет выполнять сама себя, через интервал времени speed, пока мы не пройдем весь массив, и в конце выполнит метод stopMoveAnime.


/**
* Начало анимации перемещения
* @param Массив пути
*/
startMoveAnime:function(track){
        var ball = this.seletedBall; // Получим выдиленный шар
        this.seletedBall = false;       // и снимим выдиление
        ball.unselect();
        var cell = this.cell;   // Запомним массив
        var i=track.length; // Путь мы запомнили наоборот по этому будем перемещатся с конца массива
        var _this = this;               // и this в локальную переменную чтобы использовать их в замыкание
        (function(){
                if(i--) // Пока не достигнем конца
                {
                        cell[track[i]].addBall(ball); // Переместим шарик в следующюю клетку
                        setTimeout(arguments.callee,_this.speed); // Повторим через некоторое время для замедления перемещения
                }
                else
                        _this.stopMoveAnime(ball); // Достигли конца остановим перемещение
        })();
}
 

Функция stopMoveAnime будет проверять собралась ли линия то удалять, а если нет то добавлять на игровое поле новые шары.


/**
* Завершение перемещения шара
*/
stopMoveAnime:function(ball)
{
        var lines = this.searchLines(ball); //  Найдем собранные линии
        if(lines.length>0)
        {
                this.clearLines(lines);         // И удалим их
        }
        else
        {
                this.newBall(); // Если не одна линия не была собрана то выбрасываем на поле новые шарики
        }
}
 

Сейчас у нас при добавление новых шариков не проверяется собралась ли линия, давайте изменим метод newBall и добавим проверку.


/**
*       Помещает на игровое поле новые шарики
*/
newBall:function(){
        this.emptyCell = []; // Обнулим массив свободных шариков, и заполним его заново, он мог изменится.
        var lines = []; // Массив собранных линий
        for(var i=this.cell.length;i--;)
        {
                if(!this.cell[i].isBall()) this.emptyCell.push(i); // Если ячейка пустая добавим в массив
        }
        /*
                Создадим новые шарики количеством, указанным в переменной this.countNewBall
                Но так как свободных мест может не хватить, поэтому мы выберем минимальное значение
        */
        for(var i=Math.min(this.countNewBall,this.emptyCell.length);i--;)
        {
                var ball = new Ball();
                ball.addEvent('onclick',this.dSelectBall); // Подпишемся на событие
                this.addRandBall(ball); // Добавим шарик
                lines.concat(this.searchLines(ball)); // Найдем собранные линии и добавим их в массив линий
        }
        if(lines.length>0) // Если по чистой случайности совпали линии, то удалим их
        {
                this.clearLines(lines);
        }
        // Дальше проверим если количество свободных мест меньше чем добавляемые шарики то конец игры
        else if(this.emptyCell.length<=this.countNewBall) this.gameOver();
}
 

Что у нас получилось можно посмотреть здесь, исходники скачать здесь.

Заключение.

Как можно улучшить игру? Во первых нарисовать красивые разноцветные шарики. Сделать красивый шлейф, тянущийся следом за шариком. Показывать шарики, которые будут выброшены на поле следующим ходом. Сделать систему рейтинга, на каком-нибудь серверном языке. Если вы хотите, чтобы я описал, как это сделать, пишите в комментариях.