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....

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

[RoboTact]

What is the square? Not rectangle (sides equal)? Only 'border' cells required, no limitation on length of side and contents of other cells? What is the size of board? What happens when several squares are produced?

[Yves M]

Is it only about squares that need to be filled in or any closed shape? For squares it's much simpler. For closed shapes, the simple way is to run a floodfill and test whether the shape is closed or not. But that takes too much time. So one optimization would be to only run floodfill whenever a player has just touched an existing colored square with his "cursor". Then, in order to optimize the floodfill, you can keep a pre-filled array with the convex parts of the board that have only one direction open. For example:

[sam000qc]

Hi!

Thanks for the fast answer. Yes, it's only about close shape, square to be more precise (it would be nice to have detection on rect. too, but it would take more processing time and I can't afford it). To explain miself better, I did a small .jpg to show you. In blue are the tiles where 1 user has passed, the white ones are still free (no one touched them). So, if I give to the algo i'm looking for this grid (an 2d array 0 == free, 1 == player one, 2 == player 2, etc), it should fill the sqaures A, B and C...

One of my problem if the length of the side; it's possible that they're not all the same, but still form a square, like I tried to show with the red circle...

(size of board is pretty small right now, but will be bigger)

[RoboTact]

With squares it's O(length of board) with simpliest optimization I think of, if that's enough nothing more is required (it's O(length^2) anyway for found square). If players are people, frequency of moves is low. There are also various heuristics possible, like keeping lists of angle pieces and looking up in such lists for intersection - may in fact reduce time, but information about typical board contents is required for selecting such things.

[RoboTact]

Saw your last message.
You really need to decide about numbers. What is the size of board? How many players will play simultaneously on single server? How frequently one player moves?
AFAICS, there is little if any difference in performace you can get of moving from rectangles to squares, so you should make sure decisions you make are based on solid facts.

[sam000qc]

I'm not sure i'm following you RoboTact. What I meant was; I cannot just do an algo that take the first tile (0,0) and checking at his right if the next tile has the same value until the next one isn't, and then check at the last tile I found If the next tile under it is at the good owner, etc etc etc until I come back to the first one (0,0). It would be the easiest way to check if the square is close, but it doesn't work in my case...

[sam000qc]

For now, the numbers I have:

Board of 20x20, 4 players, 1000 games per server....

A move between 2 tile can take 1 seconds. So we can expect 4 moves per second per game, so 4000 moves/seconds...

[RoboTact]

I'm not sure i'm following you RoboTact. What I meant was; I cannot just do an algo that take the first tile (0,0) and checking at his right if the next tile has the same value until the next one isn't, and then check at the last tile I found If the next tile under it is at the good owner, etc etc etc until I come back to the first one (0,0). It would be the easiest way to check if the square is close, but it doesn't work in my case...As saying goes,
There is always an easy solution to every human problem - neat, plausible, and wrong.
It's unrelated.

For now, the numbers I have:

Board of 20x20, 4 players, 1000 games per server....

A move between 2 tile can take 1 seconds. So we can expect 4 moves per second per game, so 4000 moves/seconds...In this case number of players is insignificant as with 20x20 overhead of transmitting player's move and response may be much greater then algorithm of performing move itself. What are the means of transimtting response? Do you use your own client or generate HTML page with changed state?

[sam000qc]

The server will be some sort of xml socket. So, not a big amount of data passing between the server and all the clients... But I don't see the link with my problem??

[RoboTact]

But what amount of data? Do you pass O(size*size) anyway? My point is in this case algorithm doesn't matter.

For each cell support distance in every direction to cell of color different from that of that cell. On changing color of any cell, fix these distances in all directions (it'll take O(size)).

AAAAAAB
ABAA
ABAB
BBBB

In picture above A and B are colors, first A is the place of move. Supported information says that there are 5 A to the right and 2 A downwards.

<EDIT: just noted it doesn't solve the problem - last move isn't always corner... 'll try to come up with smth>

Now, if you trace from first A to the right and note how many A are there downwards from given A, you can check if given place can be an angle of square (that is, downwards of that cell number of A is no less then distance from place of move). This way you create boolean arrays for every direction and then AND them to determine possible complete squares (where both angles correspond to each other).

[sam000qc]

Yeah, I always tried that but like you said; last move in a row isn't always the corner of the square. So the solution would be to explore each directions that could lead to a square. In the case below, if we're searching for the A color, there would be 3 possible paths and just one leading to a square. But searching in all possible paths demultipliate the processing time, and I must avoid that....

AAAAAAA
ABBABAB
ABBBBAB
ABBBBAB
AAAAAAB


Interesting problem isn't it?

[RoboTact]

Yes, but from practical point of view you haven't yet pointed if it's required. There are many interesting problems araising in programming, resolving of many of which will do some good, but it's in many cases better to leave system as it is and move on, adding features user needs.
Possibly you can add some heuristics which will do just fine, making calculation on average just some percents of data transition (if you send O(n^2)). Only thing required to balance them is feedback repeatedly obtained using record of several (dozens) of games. Maybe it'll show you that blind straightforward algorithm already makes no considerable overhead.