0
\$\begingroup\$

My game is a grid in which you have to change cells color by clicking on them. When I generate a grid I have to know all the possible combinations of blue and white cells my game allows, to know the difficulty level of the grid.

Each time I create a scenario I have to update an important parameter which is groups of white cells that touch each other.

I use 3 tables in my functions :

The first contains positions of all the white cells

// example for a 3,3 grid : 
[y0 => [x0 => x0, x1 => x1], y1 => [x0 => x0], y2 => [x1 => x1, x2 => x2]]

The second one contains positions of the grouped white cells that touch each other

// same example
[ [[y0,x0],[y0,x1],[y1,x0]], [[y2,x1],[y2,x2]] ]

The third one is only one group of the second table

// same example
[[y0,x0],[y0,x1],[y1,x0]]

I created several function :

This one needs only the first table and return the second table. I use it to initialize the parameter when I create a grid.

function rec($p, $po, $t){
    // $p table containing white cases : [y0 => [x0 => x0, x1 => x1,..], y1 => [x0 => x0, x1 => x1],..]
    // $po position of the first case : [y,x]
    // $t table to record groups
    $u = [];
    if(isset($p[$po[0]][$po[1]+1]) && !in_array([$po[0],$po[1]+1], $t)){
        $u[] = [$po[0],$po[1]+1];
        $t = array_merge($t, [[$po[0],$po[1]+1]]);
    }
    if(isset($p[$po[0]][$po[1]-1]) && !in_array([$po[0],$po[1]-1], $t)){
        $u[] = [$po[0],$po[1]-1];
        $t = array_merge($t, [[$po[0],$po[1]-1]]);
    }
    if(isset($p[$po[0]-1][$po[1]]) && !in_array([$po[0]-1,$po[1]], $t)){
        $u[] = [$po[0]-1,$po[1]];
        $t = array_merge($t, [[$po[0]-1,$po[1]]]);
    }
    if(isset($p[$po[0]+1][$po[1]]) && !in_array([$po[0]+1,$po[1]], $t)){
        $u[] = [$po[0]+1,$po[1]];
        $t = array_merge($t, [[$po[0]+1,$po[1]]]);
    }
    if(count($u) > 0){
        foreach($u as $v){
            $t = rec($p, $v, $t);
        }
        return $t;
    }
    else{
        return $t;
    }
}

$p = [ // an example
    0 => [0 => 0, 2 => 2, 4 => 4],
    1 => [0 => 0, 4 => 4],
    2 => [0 => 0, 2 => 2, 4 => 4],
    3 => [0 => 0, 4 => 4],
    4 => [0 => 0, 1 => 1, 2 => 2, 3 => 3, 4 => 4]
];

$u = [[]];
$z = [];
$c = 0;
foreach($p as $a => $n){
    foreach($n as $b){
        //var_dump($u);
        if(!in_array([$a,$b], $z)){
            $o = [];
            $o = rec($p, [$a,$b], [[$a,$b]]);
            $u[$c++] = $o;
            $z = array_merge($z, $o);
        }
    }
}
var_dump($u);

You can test it here : jdoodle.com/ia/iTi

This function needs only the second table, it updates a group of white cells that I know one of it cells has become blue. I don't use it because it is too slow.

function updateGroup($group){
    // $gp is only one group a white cells : [[y1,x1],[y1,x2],[y2,x1],..]
    $groupTemp = $group;
    $allNewGroups = [];
    do{
        foreach($group as $x => $cellSearch){
            unset($group[$x]);
            unset($groupTemp[$x]);
            $cellSearchTab = [$cellSearch];
            $newGroup = [];
            $check = false;
            $index = 0;
            do{
                $cellTouchTab = [];
                foreach($cellSearchTab as $cell){
                    if($index == 0){
                        $newGroup[] = $cell;
                    }
                    foreach($groupTemp as $k => $cellTouch){
                        if((abs($cell[0]-$cellTouch[0]) == 1 && $p[1]-$cellTouch[1] == 0) || (abs($cell[1]-$cellTouch[1]) == 1 && $p[0]-$cellTouch[0] == 0)){
                            unset($groupTemp[$k]);
                            unset($group[$k]);
                            $cellTouchTab[] = $cellTouch;
                        }
                    }
                }
                if(!empty($t)){
                    $newGroup = array_merge($newGroup, $cellTouchTab);
                    $cellSearchTab = $cellTouchTab;
                    if(empty($groupTemp)){
                        $check = true;
                    }
                }
                else{
                    $check = true;
                }
                $index++;
            }
            while($check == false);
            $allNewGroups[] = $newGroup;
            break;
        }
    }
    while(!empty($group));
    return $allNewGroups;
}

To test it : jdoodle.com/ia/iU2

This function is the one I use because it is the fastest, it needs the second table and the position of cell which has become blue, it update all groups of white cells :

function rec5($allGroups, $cellDel){
    // $allGroups is the table containing all the groups of white cells that touch each other [[y1,x1],[y1,x2],[y2,x1],..]
    // $cellDel is the position of the cell that has become blue [y,x]
    $allGroupsTemp = $allGroups;
    foreach($allGroupsTemp as $k2 => $group){
        $indexCellDel = array_search([$cellDel[0],$cellDel[1]], $group);
        if(is_int($indexCellDel)){
            unset($allGroupsTemp[$k2][$indexCellDel]);
            if(!empty($allGroupsTemp[$k2])){
                $newGroups = [];
                foreach($allGroupsTemp[$k2] as $cell){
                    $check = false;
                    $cellsTouch = [];
                    foreach($newGroups as $k3 => $newGrp){
                        if(    in_array([$cell[0]-1,$cell[1]], $newGrp)
                            || in_array([$cell[0],$cell[1]-1], $newGrp)
                            || in_array([$cell[0]+1,$cell[1]], $newGrp)
                            || in_array([$cell[0],$cell[1]+1], $newGrp)){
                            $cellsTouch[] = $k3;
                            $check = true;
                        }
                    }
                    if(!$check){
                        $newGroups[] = [$cell];
                    }
                    else{
                        if(count($cellsTouch) == 1){
                            $newGroups[$cellsTouch[0]][] = $cell;
                        }
                        else{
                            $d = [];
                            foreach($cellsTouch as $bb){
                                $d = array_merge($d, $newGroups[$bb]);
                                unset($newGroups[$bb]);
                            }
                            $d = array_merge([$cell], $d);
                            $newGroups[] = $d;
                        }
                    }
                }

                if(count($newGroups) > 1){
                    unset($allGroupsTemp[$k2]);
                    foreach($newGroups as $newGrp){
                        $allGroupsTemp[] = $newGrp;
                    }
                }
            }
            else{
                unset($allGroupsTemp[$k2]);
            }
        }
    }
    return $allGroupsTemp;
}

To test it : jdoodle.com/ia/iU3

According to the size of the grid, my game allows a lot of combinations of blue and white cells (for a 5x5 grid I can have tens of thousands), and my problem is that all the functions I created are too slow, do you think I can make my functions faster?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I can see you tried your best, but I miss a clear explanation of what this code is used for. Is this some sort of game? What problem does this code solve? I cannot work on code without having any idea what the code is intended for. If you are intentionally obfuscating the purpose of this code, then this code is not suitable for review. See also: Asking Questions \$\endgroup\$ Nov 1, 2021 at 9:44

1 Answer 1

2
\$\begingroup\$

OK, I tried my hand at your first function. I haven't got time for the others. First the code, then I'll try to explain it:

$gameSize = 5;
$gameGrid = [[1, 0, 1, 0, 1],
             [1, 0, 0, 0, 1],
             [1, 0, 1, 0, 1],
             [1, 0, 0, 0, 1],
             [1, 1, 1, 1, 1]];

function touchingCells(&$grid, $y, $x, $cells = [])
{
    $grid[$y][$x] = 0;
    $cells[] = ['y' => $y, 'x' => $x];
    foreach ([-1, 0, 1] as $offsetY) {
        $scanY = $y + $offsetY;
        foreach ([-1, 0, 1] as $offsetX) {
            $scanX = $x + $offsetX;
            if ($grid[$scanY][$scanX] ?? 0 > 0) {
                $cells = touchingCells($grid, $scanY, $scanX, $cells);
            }
        }
    }
    return $cells;
}

$groups = [];
$tempGrid = $gameGrid;
foreach ($gameGrid as $y => $row) {
    foreach ($row as $x => $value) {
        if ($tempGrid[$y][$x] > 0) {
            $groups[] = touchingCells($tempGrid, $y, $x);
        }
    }
}

var_export($groups);

The result is:

[0 => [0 =>  ['y' => 0, 'x' => 0],
       1 =>  ['y' => 1, 'x' => 0],
       2 =>  ['y' => 2, 'x' => 0],
       3 =>  ['y' => 3, 'x' => 0],
       4 =>  ['y' => 4, 'x' => 0],
       5 =>  ['y' => 4, 'x' => 1],
       6 =>  ['y' => 4, 'x' => 2],
       7 =>  ['y' => 4, 'x' => 3],
       8 =>  ['y' => 3, 'x' => 4],
       9 =>  ['y' => 2, 'x' => 4],
       10 => ['y' => 1, 'x' => 4],
       11 => ['y' => 0, 'x' => 4],
       12 => ['y' => 4, 'x' => 4]],      
 1 => [0 =>  ['y' => 0, 'x' => 2]],
 2 => [0 =>  ['y' => 2, 'x' => 2]]];

I don't think this code is much faster than yours; they're both pretty fast, but I tried to make the code slightly less unreadable, although it is far from optimal in that regard.

The input grid is redefined here, so it is recognizable as a grid. The 1 means a white cell, the 0 means a blue cell.

I use a $tempGrid for checking touching cells. As soon as I detect that an used cell touches, I set it to zero, so it won't be detected again and it is stored in an array called $cells.

There are several things in this code that may be new to you.

  • This routine checks around a cell using offsets in foreach loops. Although that means I need to use two extra loops it also means I only need one if () inside the touchingCells() function.
  • Instead of using isset() first, I use the null coalescing operator to check if a cell touches. I could have even left out the > 0 from ($grid[$scanY][$scanX] ?? 0 > 0) but I always prefer clarity over brevity.
  • Also note the lack of array functions like array_merge().

Perhaps I'll try to work on the other functions later. Still I think a brute force approach is not wise, but since you won't give us all the details about this game, all we can do it play a bit with the given routines.

\$\endgroup\$
8
  • \$\begingroup\$ That's great thanks! I don't understand "&$grid". The mecanisms of your function are totally different from mine so it is a little difficult to understand it but I will test it. \$\endgroup\$ Nov 1, 2021 at 17:48
  • \$\begingroup\$ I will change the names of my variables to make my functions more readable. The second and third functions in my post have the same goal and they are used thousands of times unlike the first function. If you wanna know a little more about my game : I generate a grid with blue and white cells. Then I try to find all the possible paths whicl lead to fill the grid in blue with a minimum of moves. When I move to a cell it change its color. This a post related to my game : math.stackexchange.com/questions/4293598/… \$\endgroup\$ Nov 1, 2021 at 17:58
  • \$\begingroup\$ The &$grid means that $grid is passed by reference. I notice that if ((($scanY != $y) || ($scanX != $x)) && ($grid[$scanY][$scanX] ?? 0 > 0)) can be replace by if ($grid[$scanY][$scanX] ?? 0 > 0) without changing the functionality. I'll do that, it makes the code quite a bit simpler. \$\endgroup\$ Nov 1, 2021 at 18:21
  • \$\begingroup\$ @RomainCharles: I looked at your other question. I think I sort of understand what you're asking there. I'm not surprised nobody answered. It is a very complicated question and you ask two different things: 1. what is shortest path and 2. minimum blue cells to go through. I also still don't understand what problem the functions in this question are trying to solve. This is a prerequisite of a question in the Code Review community. \$\endgroup\$ Nov 1, 2021 at 19:34
  • 1
    \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ: No, those revisions do not invalidate my answer. They only help to clarify what the variables in the question stand for. \$\endgroup\$ Nov 1, 2021 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.