win checking in connect four

This is a discussion on win checking in connect four within the Game Programming forums, part of the General Programming Boards category; I am programming a game that is a rip of connect four for the GBA. The GBA isn't so fast. ...

  1. #1
    Registered User Mr_Jack's Avatar
    Join Date
    Oct 2003
    Posts
    63

    win checking in connect four

    I am programming a game that is a rip of connect four for the GBA. The GBA isn't so fast. I'm not even done with my win-checking function and there is like a 1 sec slowdown when my program checks for a winner. If you don't know what connect four is read on, if you do, skip to the asterisks...anyway it's a game where you have a 7*6 board. There are two players, each with markers of different colors. You choose a column on the board and put your piece at the bottom of the column. If there is already a piece at the bottom you put your piece one space up from that piece. Whoever gets four of their pieces in a row horizontaly, vertically, or diagnaly first wins. I hope I did a good job of explaining...

    *******************
    Anyway, my board is stored in a 1d array. Each spot has a number. Here is a picture of my board where each number is a space:

    Code:
     5  6  7  8  9 10 11
    12 13 14 17 16 17 18
    19 20 21 22 23 24 25
    26 27 28 29 30 31 32
    33 34 35 36 37 38 39
    40 41 42 43 44 45 46
    So I loop about the board checking to see if there are four of the same colored pieces in a row. This is very, very slow. I have nested loops that check for four in a row horizontaly and vertically. I have a bunch of loops that check diagonal ascending to the rightand diagonal ascending to the left. I have hit major problems checking diagonaly since every other row is a different length than any other row, so I need to have like 10 loops to check diagonaly.

    Am I going about this the wrong way?

    I would be very, very grateful if someone could help me.

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Show some code. It shouldn't be slow doing that.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    Registered User Mr_Jack's Avatar
    Join Date
    Oct 2003
    Posts
    63
    here's my checkin function so far:

    Code:
    void CheckWin()
    {
    	//Try to find a way to avoid doing a lot of this checking as it seems slow
    	
    	u8 currentplayer;
    	if (whosturn == 0)
    		currentplayer = 32;
    	if (whosturn == 1)
    		currentplayer = 64;
    	u16 loopy;
    	u16 loopx;
    	u8 inarow;
    	
    	//check hor wins
    	inarow = 0;
    	for (loopy = 0; loopy < 7; loopy++)
    	{
    		for (loopx = 0; loopx < 8; loopx++)
    		{
    			if (inarow == 4)
    			{
    				winner = whosturn + 1;
    				break;
    			}
    			if (sprites[((loopy+1)*5)+loopy*2+loopx].attribute2 == currentplayer)
    				inarow++;
    			else
    				inarow = 0;
    		}
    		inarow = 0;
    		if (winner)
    			break;
    	}
    	
    	//check vert win
    	inarow = 0;
    	for (loopx = 0; loopx < 8; loopx++)
    	{
    		for (loopy = 0; loopy < 7; loopy++)
    		{
    			if (inarow == 4)
    			{
    				winner = whosturn + 1;
    				break;
    			}
    			if (sprites[((loopy+1)*5)+loopy*2+loopx].attribute2 == currentplayer)
    				inarow++;
    			else
    				inarow = 0;
    		}
    		inarow = 0;
    		if (winner)
    			break;
    	}
    	
    	//check diag left up, right down
    	//first do the diag rows 5 and 6 because they have the same lengths
    	u8 current_spr;
    	for (loopx = 5; loopx <= 6; loopx++)
    	{
    		current_spr = loopx;
    		for (loopy = 1; loopy <= 6; loopy++)
    		{
    			if (inarow == 4)
    			{
    				winner = whosturn + 1;
    				break;
    			}
    			if (sprites[current_spr].attribute2 == currentplayer)
    				inarow++;
    			else
    				inarow = 0;
    			current_spr += 8;
    		}
    		inarow = 0;
    		if (winner)
    			break;
    	}
    }
    it only checks horizontal, vertical, and a little bit of diagonal wins.
    With just this code I get a very noticable delay.

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Well, what you could do would be to only look at the newest tile added. Check to it's left, right, below, and the diagonals for it, then you're only doing 7 checks. It's a lot less than your way.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 05-07-2009, 11:31 AM
  2. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  3. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM
  4. help with this
    By tyrantil in forum C Programming
    Replies: 18
    Last Post: 01-30-2005, 03:53 PM
  5. checking for win in tic tac toe
    By Leeman_s in forum C++ Programming
    Replies: 1
    Last Post: 04-13-2002, 01:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21