Jump to content
  • Advertisement
Sign in to follow this  
DeadXorAlive

My algorithm sucks (4 in a row)

This topic is 4839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Just finished my first game in C++. It's a '4 in a row' console game with a little help from conio.h. It works(only for 2 human players) but I'm not so happy with how I did it. Besides my terrible design I am particularly unhappy with one function. It's called CheckVictory, a member of class Bord, and it checks for a victory (duh). Maybe someones cares to give some critique or suggestions how it should be done? I'm also interested in general pointers (no pun intended) to the proper way of implementing algorithms. To parafrase (the code itself is somewhat lengthy): CheckVictory does a lot of checking on a vector of ints, where each int can represent an empty position or one that is filled by a particular player. This vector is always of size 42, and represents a bord of 7 columns and 6 rows. First row goes from 0 to 6, second from 7 to 13, etc. The checking happens in a for-loop which is nested in another for-loop, which contains 4 more loops, 18 if-statements (including boundery-checking for the vector), 6 else-statements, and a bunch of simple expressions like assignments. It is based on the fact that vector[i-7] gives the above row, similiar stuff for diagonals and (ugh) that if (i+1)%7 == 0, it means that the position (i) is on the right side of the bord. I don't like that it's so complicated. I can't even parafrase the idea well in a couple of sentences. Maybe it should not have been an vector<int> to represent the bord? Maybe seven vectors to represent the columns which can grow with .push_back? I think I lack some mathematical skills. I also think there should be a more elegant solution.

Share this post


Link to post
Share on other sites
Advertisement
First of all congratulations! I don't know how long it's been finished, but I think it's always a good idea to give yourself time to pat yourself on the back for all your hard work.

Second, if your algorithm works for all cases, then maybe there's something else that you might want to improve upon (add a computer player, port to OpenGL/DirectX/GDI).

Third, have you looked into nested <vectors> and/or recursion?

:stylin:

Share this post


Link to post
Share on other sites
Separate out the checking for rows vs columns vs diagonals.

Extract a function just for the purpose of checking contents of a row/column. To avoid special cases in the logic, you could have an out-of-bounds request return a different integer value representing 'out-of-bounds'; since it will not equal either a black piece or a red piece (I'm using the traditional Connect 4 colours here), the matching algorithms will Just Work by detecting a non-matching set of pieces. (If you get a silly result like "out-of-bounds wins!", then you need to check your loop indices. :) )

Then see if there are any other obvious simplifications to the logic. If all else fails, post it.

Note that because the dimensions are known, std::vector may not really be of any use to you. With a plain 2D array, you still have a single 'chunk' of storage, and you get obvious syntactic sugar for checking a row/column. However, you will still have to guard against out-of-bounds accesses.

Share this post


Link to post
Share on other sites
Well, first of all, you're missing a level of abstraction. Representing 2D arrays under the hood as 1D arrays is fine (and necessary) but needs to be hidden inside a class where you don't have to see it. So the first thing you should do is build a good board class, something that allows you to (among other things) find out whether there's a piece in a particular position indexed by row and column. You can have it do bounds checking for you, too... this avoids a LOT of tricky and very hard-to-find errors.

Checking for this sort of victory condition is actually a little tricky to do in an elegant manner. But here's one way to approach it. First of all, forget that your board is 7*6. Make it c*r. Next, forget that it's "connect-4"; now it's "connect-n". Make your victory checker able to find whether there's a victory, for ANY c, r, and n. This sounds counterproductive, but trust me: your final function will be much shorter, and much nicer.

Share this post


Link to post
Share on other sites
Hard to tell much from your description. Any code gets complicated as far as number of lines. The important thing is to get used to breaking your code down into functions and classes that make it more readable. You don't want 100's of lines of sequential code. I often rewrite a program as an excersize. If you can read it and find errors easily, and it works, it's good code.

Share this post


Link to post
Share on other sites
Well, if it's any help, here's how I would write it.



#define BOARD_WIDTH 6
#define BOARD_HEIGHT 7
#define GET_INDEX(x,y) ((x)*BOARD_HEIGHT + (y))

boolean CheckVictory()
{
for (int start_x = 0; start_x < BOARD_WIDTH; start_x++)
for (int start_y = 0; start_y < BOARD_HEIGHT; start_y++)
{
for (int direction=0; direction < 4; direction++)
{
boolean bFourInARow = true;

for (int check = 0; check < 4; check++)
{
int dx[] = {-1, 0, 1, 1};
int dy[] = {-1, -1, 1, 0};
int this_x = start_x + dx[direction] * check;
int this_y = start_y + dy[direction] * check;

if (this_x < 0 || this_x >= BOARD_WIDTH ||
this_y < 0 || this_y >= BOARD_HEIGHT)
{
bFourInRow = false
}
else
{
boolean bFilledIn = vector[GET_INDEX(this_x,this_y)]; // <- probably need to change this

if (!bFilledIn)
bFourInARow = false;
}
}

if (bFourInARow) return true;
}
}

return false;
}









Warning: code is untested and may or may not be pulled out of my ass

[Edited by - pinacolada on August 16, 2005 5:59:44 PM]

Share this post


Link to post
Share on other sites
Using a one-dimensional vector for the 2D board is fine. Just make a member function like getPiece(x, y) to hide this detail.

Have you tried breaking your code up into functions?

I haven't tested this code, but maybe it'll give you some ideas:



// 0 = no piece
// 1 = player 1's piece
// 2 = player 2's piece
int Board::getPiece(int x, int y)
{
assert(x >= 0 && x < getWidth() && y >= 0 && y < getHeight());
return pieces[y * getWidth() + x];
}

bool Board::checkVictory(int& winningPlayer)
{
for (int player = 1; player <= 2; ++player)
{
for (int x = 0; x < getWidth() - 4; ++x)
{
for (int y = 0; y < getHeight() - 4; ++y)
{
if (checkFourInARowRight(x, y, player) ||
checkFourInARowDown(x, y, player) ||
checkFourInARowDiagonalRightDown(x, y, player))
{
winningPlayer = player;
return true;
}
}
}
return false;
}

bool Board::checkFourInARowRight(int startX, int y, int player)
{
for (int i = 0; i < 4; ++i)
{
if (getPiece(startX + i, y) != player)
{
return false;
}
}
return true;
}

bool Board::checkFourInARowDown(int x, int startY, int player)
{
for (int i = 0; i < 4; ++i)
{
if (getPiece(x, startY + i) != player)
{
return false;
}
}
return true;
}

bool Board::checkFourInARowDiagonalRightDown(int x, int y, int player)
{
for (int i = 0; i < 4; ++i)
{
if (getPiece(x + i, y + i) != player)
{
return false;
}
}
return true;
}



Share this post


Link to post
Share on other sites
The way I usually write any algorithm is first understand completely what need to be done, then try to divide (divide and conquer stratagies) it as far as I can go for the moment. This process require working the algorithm out on board or on paper. Then it will be a simple logic to code conversion after that. Once the algorithm works and tested, then go in and optimize further, and this might involve changing algorithm for the sub portion of the original algorithm. Yes, divide the algorithm up into many smaller algorithms as much as you can, then you can code the small one easily and replace/changes to the small one.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!