Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I posted this question on stackoverflow before but received no answers so I decided to post it here and see if someone could suggest me something.

I'm working on a html/javascript game for android. It's a board game which does the following. It has tiles of different colors and user can place one tile (chosen programatically) on the board. If we get 4 or more tiles of the same color/shape we score some points and these tiles will disappear. The tiles above the removed tiles will replace them and new tiles will be added to the empty places. The image below shows how it works (this is just an example, the real board can have different dimensions):

enter image description here

The Tiles are <img> elements with their ids stored in an array which I use to check for matches and replacement.

It all works pretty well but once the new tiles are added to board I need to examine the whole board to check if new matches are avalable. And I want some advice here, because examining the whole board can be really slow. Is there a way I can do this efficiently? Here's what I thought about doing: enter image description here

Given the previous example, I thought about examining only the elements in the red area, i.e. only the elements that have been moved or added. It can be effective if the tiles move vertically, as I'll only have to check the moved/added tiles and it'll give me the new matches. But in case where I remove tiles horizontally it can be problematic, because if these tiles are at the bottom i'll have to examine the whole board and i confront the same problem.

Any advice or suggestion will be appreciated.

Note: I didn't add any code because it simply consists of checking the lines and columns for a given tile and look for matches. But if needed I can provide it.

EDIT: Adding horizontalMatchCheck function that for a given index checks for matches horizontally. It's the same thing for vertical check.

function horizontalMatchCheck(itemId) {
    hArray = new Array();
    if (rightMatch(itemId)) {
        var index = itemId + 1;
        hArray.push(itemId + 1);
        while (rightMatch(index)) {
            hArray.push(index + 1);
            index++;
        }
    }
    if (leftMatch(itemId)) {
        var index = itemId - 1;
        hArray.push(itemId - 1);
        while (leftMatch(index)) {
            hArray.push(index - 1);
            index--;
        }
    }
    //if >=4 matches found I replace the indexes with 5 (because no other tile can have this id) which'll then be removed and shifted.
    if (hArray.length >= 3) {
        hArray.push(itemId);
        for (var i = 0; i < hArray.length; i++) {
            board[hArray[i]] = items.length;
        }
    }
    else
        hArray = new Array();
}

function rightMatch(pos) 
      return (!isRight(pos) && board[(pos+1)] == current) ? 1 : 0 ;
function leftMatch(pos)
      return (!isLeft(pos) && board[(pos-1)] == current) ? 1 : 0 ;
share|improve this question
1  
Is examining a 4x4 board really that slow? Store your data as a two dimensional array, and simply run through each column, as well as each row checking for color matches. If that doesn't work, you could try storing your data by color, and checking their position data for adjacent tiles. –  Evan Mar 27 '13 at 13:53
    
Post some of your matching code, most likely it can be improved. Are you using jquery? –  petervaz Mar 27 '13 at 13:58
    
@Evan the 4x4 board was just an example as i stated. if it's a 10x10 board examining each tile can be slow. –  Anila Mar 27 '13 at 13:59
1  
Do you think that the code is too slow, or do you know that the code is too slow? It doesn't seem like something that should cause a modern phone to halt noticeably. –  eBusiness Mar 27 '13 at 14:42
1  
@Anila I'll show you a working class for gem matching game I'm creating. It is in java, but perhaps you can draw some inspiration from it >> here << –  petervaz Mar 27 '13 at 14:57
show 10 more comments

3 Answers 3

up vote 2 down vote accepted

I admit that I don't exactly understand what your algorithm is for finding matches right now, but I can tell you that there is an easy O(n) method that makes as many passes over the board as directions you want to check in if all you want to check in is straight lines. This is not what you are looking for if you want these matches to include all touching shapes of the same color or shape, this only checks for those that appear in a straight line.

Assuming you have your board in a two dimensional array where each shape has a color, shape and a property "isInRun" it is:

var shapeRun = [];
var colorRun = [];
for (var i = 0; i < boardX; i++) {
    for (var j = 0; j < boardY; j++) {
        var cell = board[i][j];
        if (i == 0 && j == 0) {
            var currentShape = cell.shape;
            var currentColor = cell.color;
            shapeRun.push(cell);
            colorRun.push(cell);
        } else {
            if (j > 0 && cell.shape == currentShape) {
                shapeRun.push(cell);
            } else {
                if (shapeRun.length >= runLength) {
                    for (var k = 0; k < shapeRun.length; k++) {
                        shapeRun[k].isInRun = true;
                    }
                }
                currentShape = cell.shape;
                shapeRun = [cell];
            }
            if (j > 0 && cell.color == currentColor) {
                colorRun.push(cell);
            } else {
                if (colorRun.length >= runLength) {
                    for (var k = 0; k < colorRun.length; k++) {
                        colorRun[k].isInRun = true;
                    }
                }
                currentColor = cell.color;
                colorRun = [cell];
            }
        }
    }
}

This scans each row for "runs" of more than runLength shapes and marks them as belonging to a group of matches by setting isInRun to true. Do this again but switch

var cell = board[i][j];

to

var cell = board[j][i]; 

To check in the other direction.

Check out this JSFiddle for an example (only tested in Chrome). This creates a random board every 5 seconds with 3 types of shapes and 3 types of colors and then highlights all the matches of 4 or more. You can play around with the parameters at the top of the javascript to change the dimensions of the board or the number of colors and shapes.

I've run this on my phone (a Galaxy Nexus) and I had to bump to board size up to 50x50 to even measure the time it takes.

share|improve this answer
    
thanks a lot! I really appreciate all the help I'm getting from here. –  Anila Mar 27 '13 at 18:52
    
thanks to your directions and those of petervaz I got what I wanted. I'm accepting this answer but the credit goes to both of you. Thanks guys! –  Anila Mar 28 '13 at 14:14
add comment

It looks to me like you're using the DOM as a general-purpose data structure. I would not recommend this approach.

You should separate the game state and rendering, into pieces of logic which are independent of each other. Don't use the DOM as a data store, and don't store references to DOM elements inside your "game state" data.

Having said that, I would also suggest that you consider using a canvas instead of DOM elements. But that's an implementation detail and may not be relevant to your problem.

If you have a simple 2d JS array, with primitive types (integers are good) as elements, it CANNOT be slow to do these lookups, even with a large grid.

In summary:

  • Store your board as a 2d array (array-of-arrays). Primitive types (integer) are best, but objects could be ok too.
  • Do not keep DOM references inside your game state (if you choose to use DOM elements to render tiles, look them up each time you need them)
share|improve this answer
    
thanks for the advice, I'm new to this (game and web dev) that's why i keep mising these things. I'll keep it in mind in future. –  Anila Mar 28 '13 at 14:17
add comment

This isn't codereview.stackexchange.com, but...

There's no obvious reason for hArray to exist. You could just use two local variables, a lower bound and an upper bound, both of which are initialised to itemId (which surely should be called itemIndex?) and expand them in different directions with simplified versions of the loops.

OTOH this method looks a bit dubious per se. A single scan through the entire row would certainly be quicker than a flood-fill from each cell.

If you really want speed above all else, I believe JavaScript's regex support is quite good...

share|improve this answer
    
thanks for the advice! –  Anila Mar 27 '13 at 18:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.