Thread: Connect 5 Algorithm in C

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    43

    Connect 5 Algorithm in C

    Hi,

    I'm making a connect 5 kind of game with a two-dimensional array. I have the board all set up but I'm trying to figure out the best way to check if there is 5 in a row up,down or diagonal. It should start checking with the chip that was just placed on the board. Any suggestions?? Thanks.

  2. #2
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Assuming you check each time a chip is placed, and start with an empty board, yes just checking from the chip that was placed will reveal if a win is present.

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Well, you have a 2D array - lets call them X and Y, so the dim is (X,Y).

    When a chip is placed, first look at X. See how many chips are to the left of the chip. Something like
    start_of_run = chip.x ;
    for (i = chip.x-1, i >= 0 && (i,Y) == a_chip ; i--) start_of_run = i ;

    Then go to the right
    end_of_run = chip.x ;
    for (i = start_of_run ; i <= max(X) && (i,Y) == a_chiip ; i++ ) end_of_run = i ;

    To see if 5 in a row,
    if (end_of_run - start_of_run >= 5) winner!

    and so on.

    For the diagonal, you'll have to increment x & y, AND, decrement X & Y to check bottom left to top right. For top left to bottom right, you'll have to decrement x & increment Y, AND, increment X and decrement Y.

    Get it?
    Last edited by Dino; 09-01-2009 at 08:56 PM.
    Mainframe assembler programmer by trade. C coder when I can.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    So you're writing a Gomoku game then?
    To check for 5 in a row you just need some loop. For each of the 8 directions set up some deltas between -1 and 1 for each of the x and y directions, then loop in that direction until you hit an edge or you've iterated overy 5 pieces.
    Something roughly like:
    Code:
    static const int xdirs[] = {0,1,1,1,0,-1,-1,-1};
    static const int ydirs[] = {-1,-1,0,1,1,1,0,-1};
    for (int i=0; i<8; ++i)
    {
        int x = startx, y = starty, numInARow=0;
        for (int j = 0; j < 5 && IsWithinBoard(x, y); ++j)
        {
            // *** Test this cell here, maybe increment numInARow ***
    
            x += xdirs[i];
            y += ydirs[i];
        }
    }
    Just give it a shot and see how you go.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 06-06-2005, 05:45 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Is there a bug in this part of my algorithm for connect 4?
    By Nutshell in forum Game Programming
    Replies: 8
    Last Post: 04-28-2002, 01:58 AM