Algo : the simplest things are always the more complex ones

[sam000qc]

Hello. I'm currently developping a game (language doesn't matter for the question) with, at first view, a simple feature: user move from tile to tile on a grid. Each tile he passed on turn into his color. The feature is that if the user draw a square on the grid, I need to detect it and fill it. Easy no?

But it can be really tricky 'cause it's a multiplayer game so; more than 1 color (4 for now). And, since it's the server that keep the grid's info, the check need to be really optimized 'cause it will be called really often (at each move of every players * nb of games running on the server).

I don't know if i'm enough clear? The concept remember me this old pinguin game that were skating on the ice and we needed to draw square too, but in this case we cannot keep in memory the last 4 move of each player since a player can connect with tiles he marked his own 2-3 minutes before....

For example; A will be tiles in one color and B tiles in another color:
AAAAAAAABBB
ABBAABBABBB
ABBBABBABBB
ABBBABBBBBB
AAABABBBBBB
AAAAABBBBBB

So, if you follow the A, will see a square of 5x5 that I should entirely fill with A color (filling isn't the issue here). So, how can I detect this square, since I cannot just follow the A color until I get another color? The last move of a row isn't always the square corner like in this exemple.

Is there something somewhere that already exist?
Does somebody have any idea or link?

I'm really in the dark right now. I have written something that seem to work, but it's 3 huge function of 300 lines each that are recursive so; the server will probably die if there's more than 4 games running... :S

Thanks a lot,

sam

[tomcant]

I'm a bit confused! Do you mean to say that you need to find the last 4 or so positions of the player? If so, then just store them in some player class somewhere.

[sam000qc]

Well, I need to be able to scan a 2d array like the one I draw on my last post. The array only contain the color of the tile (0 for a free tile, 1 for the color red, 2 for the color blue, etc). What I need is a function that will scan the array, detect every square that the players formed during the game and fill those squares with the good color.

I cannot store the last pos of the player, since the square he forms can be with tiles that he has marked a long times ago... And since this function will be perform on the server and not the client, I need a really good optimized function.

But for now, I'll he really need is an algo; a way to detect squares...

[tomcant]

I'm still not quite sure what you're asking for, but perhaps this will answer your question: set the array up so that it stores the colour of each square, i.e. 0 for none, etc. Then, when looping through the array, you can check the value of each square and fill it in as you like.

Is that what you mean?

[Alvaro]

Tomcant, I don't think you understood the problem. I'll put it in other words, to help you understand and to see if I understood:

AAAAAAAABBB
ABBAABBABBB
ABBBABBABBB
ABBBABBBBBB
AAABABBBBBB
AAAAABBBBBB

Can you see the `A's forming a square? Well, me neither. That's a rectangle. But I guess that's what he meant.

The function should detect any such rectangles being formed.

I think we should be able to use the information of what is the last letter that was changed to an `A', since only rectangles containing that letter can possibly be all `A' (other rectangles would have been detected earlier).

If this is actually what the problem is, then I need to think about a good solution, but understanding the problem at hand is a first step.

[t i l e x]

I think this is what he meant. Can you come up with a one-liner ?

[tomcant]

Ah ha! Yes, I mis-understood the problem.

[Alvaro]

This is not an easy problem. Maybe a two-liner...

How big is the grid on which we are playing?

[Darryl]

here's what I might do: track the corners:

Code: Select all

AA  AA
A    A


A    A
AA  AA

Every time a corner is created, scan horizontally/vertically for matching corners, if those are found then extend from these to find if matching diagonal exist. So if all four exist, you have a potential for a square. Now just check the space in between corners. if they are filled then you have a square, if not, just store the frame and check with every new move added. If one of other player overwrites the corner, then remove that frame from the list to check. That way if no frame exist you won't be wasting time checking for a square(rectangle(quadrangle??))

[Emery]

I don't think there is any way of avoiding taking every combination of 4+2*n A's possible and checking if it makes a rectangle. So just iterate though, push every combo on a queue, and analyze it for rectangularity until you get to the diameter of the containing matrix (4+2*n > width*height). Easy as 3.14...

And note that analyzing for rectangularity is as easy and making sure you have opposites of all x and y values so just cancel out and when all the As are gone if you have 0 it is a rectangle.



Example: (using struct for clarity)
Actually... this is probably way over complicated.
(Untested -- written in notepad, I probably made a typo, sorry)

Code: Select all

struct point
{
   int x;
   int y;
}

bool IsRectangular(point *points, int num)
{
   int left=0, right=0, top=0, bottom=0;
   int num_top=0, num_bots=0, num_lefts=0, num_right=0;

   // Find the dimensions
   for(int i=0; i < num; ++i)
   {
      if(left > points[i].x)
         left = points[i].x;

      if(right < points[i].x)
         right = points[i].x;

      if(top > points[i].y)
         top = points[i].y;

      if(bottom < points[i].y)
         bottom = points[i].y;
   }
   
   // Find residing sides of As
   for(int i=0; i < num; ++i)
   {
      bool found = false;
      if(points[i].x == left)
      {
         ++num_lefts;
         found = true;
      }
         
      if(points[i].x == right)
      {
         ++num_right;
         found = true;
      }
      
      if(points[i].y == top)
      {
         ++num_tops;
         found = true;
      }
      
      if(points[i].y == bottom)
      {
         ++num_bots;
         found = true;
      }
      
      if(!found) // Wasn't on the boundary as it should be
         return false;

   }
   
   // Make sure the sides cancel out
   if(num_top != num_bots || num_lefts != num_rights)
      return false;

   // Eliminate something like this:
   // AAAA
   // ABBA
   // BBBB
   // AAAA
   if(bottom-top != num_lefts+2 || right-left != num_tops+2)
      return false;
      
   return true;
}


[GiovaMaster]

My algorithm, gives like result a clearer map, from where you can gain your rectangle more easy..
The algorithm is perfectly working and finds all the rectangles, if it agrees like rectangle also:

AA |
AA |---->Something like this is a rectangle with area=0? If "yes", you could color the 'A'.. .
AA |

However: Here is the code..ask me for whichever thing ..

Code: Select all

#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
   int j,i=0,c=0,Count;
   bool a=false;      
   char mat[6][12]={"AAAAAAAABBB",
                    "ABBAABBABBB",
                    "ABBBABBABBB",//To be more clear
                    "ABBBABBBBBB",
                    "AAABABBBBBB",
                    "AAAAABBBBBB"};
   for(i,cout<<'\t';i<6;cout<<'\n'<<'\t',++i)
      for(j^=j;j<11;cout<<mat[i][j],++j){}//Output the original matrix
   for(c;a==false;c++){
      a=true;
      for(i^=i;i<6;i++)
         for(j^=j;j<11;j++){   
            if(mat[i][j]=='A'){
               Count=0;
               if(i>0)if(mat[i-1][j]=='A')Count++;
               if(i<5)if(mat[i+1][j]=='A')Count++;
               if(j>0)if(mat[i][j-1]=='A')Count++;
               if(j<10)if(mat[i][j+1]=='A')Count++;
               if(Count<2){mat[i][j]=' ';a=false;}//Change here,to leave
            }                            //the "wrong" 'A'
            else mat[i][j]=' ';//Delete the 'else' to leave the original matrix
         }
   }
   cout<<'\n'<<"---> After "<<c<<" cycles : "<<endl;
   for(i^=i,cout<<'\n'<<'\t';i<6;cout<<'\n'<<'\t',++i)
      for(j^=j;j<11;cout<<mat[i][j],++j){}//Output the modified matrix
   cout<<'\n';
   system("pause");
   return 0;
}

P.s : If you have problem to understand the algorithm (that is very simple), ask me..


[EDIT]: My algorithm, isn't so perfect...eheheh...you can use it only to remove the 'A' that are very useless into the map...so, this algorithm sucks...I'll post another one soon...and the idea of corners is right also for me.

[GiovaMaster]

Dear moderators: what do you think about making a new beginner (perhaps intermediate) contest on this topic idea??I believe it would be nice..
This is a dead topic..make it live as contest!
I'm asking that before posting my final code..

[Darryl]

Ahah, that might be a cool contest, especially for a code brevity.

But I think a point you guys are missing, based on Ritz's comment and Giova's code is that the players are taking turns, and so the code requirement isn't to search a "completed " grid for squares which is the harder task, it only has to see if the last square added created a square, if it did then you fill that square, but as you are filling you would have to check each fill to see if ithe fill created squares as well. Therefore the contest would have to be:

Create a framework for a four player game ( Human or computer players), that take turns moving from square to square (horizontal or vertical), filling them if a square is completed.

After someone creates a winning framwork, then we can hold a contest for a winning AI player

[GiovaMaster]

I'm in!
But well... I've never been writing a framework..(perhaps I can't translate it properly, so that I can't understand what does it really mean..)..is it a structure?a simple program? Or something else like dll, library or ...what?

Guys..what do you think about this contest idea?

[Corsix]

AFAIK, token contests do better than AI contests