Создайте случайный координатный путь в сетке

Чего я хочу?

Я хочу, чтобы в PHP функция или класс/метод возвращали массив пути генерации в сетке (9x9) см. (код: сетка с путем). Это условие:

  • Блок не может перекрывать друг друга
  • Существует путь направления (см. Раздел: Что у меня было?). Этот путь может быть случайным, и требуются указания.
  • Можно выйти справа/вверху и продолжить путь слева/внизу (см. пример ниже). Возможно и обратное.
  • Количество шагов является переменным и не может перекрывать друг друга.
  • Возвращает массив ( код: сетка с путем ). Мне нужны координаты из оранжевых точек на примере изображения ниже. На самом деле достаточно ли последовательных координат в массиве (из оранжевых точек). Но если проще использовать полную сетку массива 9x9, то все в порядке.

Что у меня было?

  • Пустая сетка массива (код: пустая сетка):
  • A случайная начальная позиция (см. "Начало" в примере изображения)
  • Направление в данном случае 1234123 (может быть разным) (1: вверх, 2: вправо, 3: вниз, 4: влево)

Нужна дополнительная информация?

Если вам нужна дополнительная информация или что-то непонятно? пожалуйста, спроси меня. Спасибо!

Код: пустая сетка: 

array(
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
)

Код: сетка с путем (1 = начало, 8 = конец): 

array(
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 3, 0, 2, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(6, 0, 0, 7, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 8, 0, 0, 1, 0, 0),
    array(5, 0, 0, 0, 4, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
)

The orange dottes need to be generate

Author: Noam148, 2014-10-15
Source

2 answers

Это должно помочь вам начать (Разместил демонстрацию @ http://tinker.bit-nibble-byte.com/grid.php )

Пожалуйста, простите за альтернативный синтаксис, я ненавижу фигурные скобки.

<style>
    td {
        width: 30px;
        height: 30px;
        font-size: 15px;
        text-align: center;
    }

    td.S {
        color: black;
        background-color: orange;
    }

    td.D {
        color: black;
        background-color: #44c;
    }

    td.R {
        color: black;
        background-color: #c44;
    }

    td.U {
        color: black;
        background-color: #cc4;
    }

    td.L {
        color: black;
        background-color: #4c4;
    }

    td.E {
        color: black;
        background-color: #c4c;
    }
</style>
<?php

$data = pathField(50, 25, 50, 10);

dumpField($data['FIELD']);
dumpCoor($data['COOR']);

/**
 * @param int $width Width of the playing field
 * @param int $height Height of the playing field
 * @param null $steps Number of direction changes
 * @param int $legChange Odds of changing direction (1-99)
 * #param null $minLegLength Minimum length of a straight line (or until it hits a wall)
 * @param null $startX Start X Position
 * @param null $startY Start Y Position
 * @return array
 */
function pathField($width = 10, $height = 10, $steps = null, $legChange = 50, $minLegLength = 3, $startX = null, $startY = null)
{
    $coord = array(); // Coordinates where direction was changed

    if (!$startX):
        $startX = rand(1, $width); // Random X start position
    endif;
    if (!$startY):
        $startY = rand(1, $height); // Random Y start position
    endif;
    if (!$steps):
        $steps = $width * $height; // Will cause run until "painted in a corner"
    endif;

    $coord[] = array('X' => $startX, 'Y' => $startY); // Set First/Start coordinate

    $field = array_fill(1, $height, array_fill(1, $width, null));  // Create the empty playing field
    $field[$startY][$startX] = 'S'; // Flag start position
    $pos = array('X' => $startX, 'Y' => $startY, 'D' => null, 'L' => $minLegLength + 1); // Set current position

    while (count($coord) < $steps): // Go until we have enough steps

        $go = array (                                                 // Calculate the directions positions for
         'left' => (($pos['X'] - 1) < 1) ? $width  : ($pos['X'] - 1), // Left
        'right' => (($pos['X'] + 1) > $width) ? 1  : ($pos['X'] + 1), // Right
           'up' => (($pos['Y'] - 1) < 1) ? $height : ($pos['Y'] - 1), // Up
         'down' => (($pos['Y'] + 1) > $height) ? 1 : ($pos['Y'] + 1), // Down
        );

        $validMoves = array(); // Reset valid moves

        if ($field[$pos['Y']][$go['left']] == null):  // Check if we can move left
            $validMoves['L'] = array(
                'X' => $go['left'],
                'Y' => $pos['Y'],
                'D' => 'L',
                'P' => rand(1,$width)
            );
        endif;
        if ($field[$pos['Y']][$go['right']] == null): // Check if we can move right
            $validMoves['R'] = array(
                'X' => $go['right'],
                'Y' => $pos['Y'],
                'D' => 'R',
                'P' => rand(1,$width)
            );
        endif;
        if ($field[$go['up']][$pos['X']] == null): // Check if we can move up
            $validMoves['U'] = array(
                'X' => $pos['X'],
                'Y' => $go['up'],
                'D' => 'U',
                'P' => rand(1,$height)
            );
        endif;
        if ($field[$go['down']][$pos['X']] == null): // Check if we can move down
            $validMoves['D'] = array(
                'X' => $pos['X'],
                'Y' => $go['down'],
                'D' => 'D',
                'P' => rand(1,$height)
            );
        endif;

        if (count($validMoves) == 0):  // If there are no valid moves, it means...
            break;                     // Painted myself into a corner!
        endif;

        // Keep going in the same direction or are we changing?


        if (array_key_exists($pos['D'], $validMoves) && (($pos['L'] < $minLegLength) || (rand(1, 100) < $legChange))):
            $moveDir = $validMoves[$pos['D']]; // Get Last Direction
            $pos['L']++; // Increase Leg Length
        else:
            $moveDir = $validMoves[array_rand($validMoves, 1)]; // Get A Random Direction
        endif;

        // If we're changing directions record the point in the coordinate array
        if ($moveDir['D'] != $pos['D']):
            $coord[] = array(
                'X' => $moveDir['X'],
                'Y' => $moveDir['Y']
            );
            $pos['L'] = 1; // Reset leg Length
        endif;

        // Update our current position
        $pos = array('X' => $moveDir['X'], 'Y' => $moveDir['Y'], 'D' => $moveDir['D'], 'L' => $pos['L']);

        // Update the playing field
        $field[$pos['Y']][$pos['X']] = $moveDir['D'];
    endwhile;

    $field[$pos['Y']][$pos['X']] = 'E'; // Flag the end point

    return array('FIELD' => $field, 'COOR' => $coord); // Return the fields and the coors
}

function dumpCoor(array $coor)
{
    foreach($coor as $point):
        echo $point['X'] . ', ' . $point['Y'] . '<br>';
    endforeach;
}

function dumpField(array $field)
{
    $height = count($field);
    $width = count($field[1]);
    echo $width . 'x' . $height;
    echo "<table border='1'>";
    foreach ($field as $key => $row):
        echo "<tr>";
        foreach ($row as $key => $cell):
            if ($cell):
                echo "<td class=\"$cell\">$cell</td>";
            else:
                echo "<td>&nbsp;</td>";
            endif;
        endforeach;
        echo "</tr>";
    endforeach;
    echo "</table>";

}
 1
Author: Wranorn, 2014-10-30 04:32:05

@Wranorn Спасибо за ваш ответ! Я тестирую его, и он работает. Тем временем я также создал скрипт, который генерирует сетку. Надеюсь, один из этих сценариев поможет другим людям с тем же вопросом. Вот мой фрагмент:

<?php 
class Grid{
    //propertys to create grid path
    private $aDirections = array(1,2,3,4,1,2,3); // 1: up, 2: right, 3: down, 4: left
    private $aGridTemp = array();
    private $aGridDefinitive = array();
    private $iLastX = null; 
    private $iLastY = null;
    private $iStep = 0;
    private $aAllSteps = array();
    private $sUniqueKey = ""; //create empty Unique Key (length of each block range)    

    /* 
     * Return a grid array
     * @return $this->_generateGridPath
     */
    public function getGridPath(){
        //cal method thats generate a Path for the grid
        return $this->_generateGridPath();
    }

    /*
     * (GENERATE GRID)
     * Create a grid path
     */
    private function _generateGridPath() {
        //(Re)Set grid data
        $this->iStep = 0;
        $this->iLastX = rand(1, 7);
        $this->iLastY = rand(1, 7);
        $this->sUniqueKey = "";
        $this->aAllSteps = array();
        //set first step to steparray
        $this->aAllSteps[] = array('iCellX' => $this->iLastX, 'iCellY' => $this->iLastY);

        //create empty grid and save it to temp grid
        $this->aGridDefinitive = $this->_getEmptyGridArray();
        $this->aGridTemp = $this->aGridDefinitive;

        //set start position
        $this->aGridTemp[$this->iLastY][$this->iLastX] = 0;

        //loop trhough all direction steps
        foreach ($this->aDirections AS $iDirection) {
            $iNumberOfBlocks = rand(2, 8);

            //check the new coordinate is posible (check if there no overlapping)
            do {
                //check the new coordinate is posible (check if there no overlapping)
                $coordinateCheck = $this->_checkNewCoordinatesIsPossible($iDirection, $iNumberOfBlocks);
                if ($coordinateCheck) {
                    //if success add to unique key
                    $this->sUniqueKey .= $iNumberOfBlocks;
                    //set temp to to definitive grid
                    $this->aGridDefinitive = $this->aGridTemp;
                    $this->iStep++;
                    $this->iLastX = $coordinateCheck['iCellX'];
                    $this->iLastY = $coordinateCheck['iCellY'];
                    //add to all steps array
                    $this->aAllSteps[] = array('iCellX' => $coordinateCheck['iCellX'], 'iCellY' => $coordinateCheck['iCellY']);
                    break;
                } else {
                    //break out each if check is false
                    $this->aGridTemp = $this->aGridDefinitive;
                    $iNumberOfBlocks--;
                }
            } while ($iNumberOfBlocks > 2);
        }

        //if unique key is not complete (not the same length as the number of directions) rebuild grid
        if (strlen($this->sUniqueKey) != count($this->aDirections)) {
            $this->_generateGridPath();
        }

        //return the grid path data
        return $this->aGridDefinitive;
    }

    /*
     * (GENERATE GRID)
     * Check if Coordinate is possible 
     * $iDirection, $iNumberOfBlocks
     */
    private function _checkNewCoordinatesIsPossible($iDirection, $iNumberOfBlocksNew){
        //set check boolean
        $return = true;
        //if first step than step - 1
        $iNumberOfBlocks = $this->iStep == 0 ? ($iNumberOfBlocksNew-1) : $iNumberOfBlocksNew;
        //set new block position
        $iCurrentY = "";
        $iCurrentX = "";
        //check the direction to fill the blocks the right way
        switch ($iDirection) {
            case 1: //direction up (go positif (higher) coordinate)
                $iCurrentX = $this->iLastX;
                $iCurrentY = $this->_getCoordinatePosition($this->iLastY, $iNumberOfBlocks, false);
                break;
            case 3: //direction down (go negative (lower) coordinate)
                $iCurrentX = $this->iLastX;
                $iCurrentY = $this->_getCoordinatePosition($this->iLastY, $iNumberOfBlocks, true);
                break;
            case 2: //direction right (go positif (higher) coordinate)
                $iCurrentY = $this->iLastY;
                $iCurrentX = $this->_getCoordinatePosition($this->iLastX, $iNumberOfBlocks, true);
                break; 
            case 4: //direction left (go negative (lower) coordinate)
                $iCurrentY = $this->iLastY;
                $iCurrentX = $this->_getCoordinatePosition($this->iLastX, $iNumberOfBlocks, false);
                break; 
        } 

        //check the direction to fill the blocks the right way
        switch ($iDirection) {
            case 1: //direction up
                //check if the current block is positioning under or above the last block
                if($iCurrentY < $this->iLastY){ 
                    //Loop from last position Y to current postiont Y // ($this->iLastY-1 do not overwrite the last item)  
                    for($iPosY = ($this->iLastY-1); $iPosY > ($iCurrentY-1); $iPosY--) {
                        //check if not null
                        if($this->aGridTemp[$iPosY][$iCurrentX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iPosY][$iCurrentX] = $this->iStep;
                    }
                }else{
                    //Loop from last position Y to top row (pos y: 1) // ($this->iLastY-1 do not overwrite the last item)  
                    for($iPosY = ($this->iLastY-1); $iPosY >= 0; $iPosY--) {
                        //check if not null
                        if($this->aGridTemp[$iPosY][$iCurrentX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iPosY][$iCurrentX] = $this->iStep;
                    }
                    //loop from bottom to current pos Y
                    for($iPosY = 8; $iPosY > ($iCurrentY-1); $iPosY--) {
                        //check if not null
                        if($this->aGridTemp[$iPosY][$iCurrentX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iPosY][$iCurrentX] = $this->iStep;
                    }
                }
                break;
            case 3: //direction down
                //check if the current block is positioning under or above the last block
                if($iCurrentY > $this->iLastY){ 
                    //Loop from last position Y to current postiont Y // ($this->iLastY+1 do not overwrite the last item)  
                    for($iPosY = ($this->iLastY+1); $iPosY <= $iCurrentY; $iPosY++) {
                        //check if not null
                        if($this->aGridTemp[$iPosY][$iCurrentX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iPosY][$iCurrentX] = $this->iStep;
                    }
                }else{
                    //Loop from top to current item row // ($iCurrentY-1 do not current the current item)  
                    for($iPosY = 0; $iPosY <= $iCurrentY; $iPosY++) {
                        //check if not null
                        if($this->aGridTemp[$iPosY][$iCurrentX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iPosY][$iCurrentX] = $this->iStep;
                    }
                    //loop from bottom to last to bottom pos Y // ($this->iLastY+1 do not overwrite the last item)  
                    for($iPosY = ($this->iLastY+1); $iPosY <= 8; $iPosY++) {
                        //check if not null
                        if($this->aGridTemp[$iPosY][$iCurrentX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iPosY][$iCurrentX] = $this->iStep;
                    }
                }
                break;
            case 2: //direction right
                //check if the current block is positioning left or right from the last block
                if($iCurrentX > $this->iLastX){ 
                    //Loop from last position X to current postiont X // ($this->iLastX+1 do not overwrite the last item)  
                    for($iPosX = ($this->iLastX+1); $iPosX < ($iCurrentX+1); $iPosX++) {
                        //check if not null
                        if($this->aGridTemp[$iCurrentY][$iPosX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iCurrentY][$iPosX] = $this->iStep;
                    }
                }else{
                    //Loop from left to current item to right // ($iCurrentX-1 do not current the current item)  
                    for($iPosX = 0; $iPosX <= $iCurrentX; $iPosX++) {
                        //check if not null
                        if($this->aGridTemp[$iCurrentY][$iPosX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iCurrentY][$iPosX] = $this->iStep;
                    }
                    //loop from left to last to right pos X // ($this->iLastX+1 do not overwrite the last item)  
                    for($iPosX = ($this->iLastX+1); $iPosX <= 8; $iPosX++) {
                        //check if not null
                        if($this->aGridTemp[$iCurrentY][$iPosX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iCurrentY][$iPosX] = $this->iStep;
                    }
                } 
                break; 
            case 4: //direction left
                //check if the current block is positioning under left or right from the last block
                if($iCurrentX < $this->iLastX){ 
                    //Loop from last position X to current postiont X // ($this->iLastX-1 do not overwrite the last item)  
                    for($iPosX = ($this->iLastX-1); $iPosX > ($iCurrentX-1); $iPosX--) {
                        //check if not null
                        if($this->aGridTemp[$iCurrentY][$iPosX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iCurrentY][$iPosX] = $this->iStep;
                    }
                }else{
                    //Loop from last position X to left row (pos x: 1) // ($this->iLastX-1 do not overwrite the last item)  
                    for($iPosX = ($this->iLastX-1); $iPosX >= 0; $iPosX--) {
                        //check if not null
                        if($this->aGridTemp[$iCurrentY][$iPosX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iCurrentY][$iPosX] = $this->iStep;
                    }
                    //loop from left to current pos X
                    for($iPosX = 8; $iPosX > ($iCurrentX-1); $iPosX--) {
                        //check if not null
                        if($this->aGridTemp[$iCurrentY][$iPosX] !== null){
                            $return = false;
                        }
                        $this->aGridTemp[$iCurrentY][$iPosX] = $this->iStep;
                    }
                } 
                break; 
        } 

        //if there ar no errros (if return is true)? return the X and Y position
        if($return === true){       
            $return = array('iCellX' => $iCurrentX, 'iCellY' => $iCurrentY);
        }

        //return data (false or position)
        return $return;
    }

    /*
     * (GENERATE GRID)
     * Reset grid array
     * @return an empty grid array
     */
    private function _getEmptyGridArray(){
        return array(
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
            array(null, null, null, null, null, null, null, null, null),
        );
    }

    /*
     * (GENERATE GRID)
     * If heigher than 8? continue 0. If lower than 0? continue 8 
     * $iCurrentPosition, $iBlockLength, $bIsPositive
     */
    private function _getCoordinatePosition($iCurrentPosition, $iBlockLength, $bIsPositive = true){
        $iNewCoordinate = $iCurrentPosition;
        //check if its a positive or negative integer
        if($bIsPositive){
            //loop the number of block
            for ($i = 1; $i <= $iBlockLength; $i++) {
                $iNewCoordinate++;
                //if higher than 8 go back to 0
                if($iNewCoordinate > 8){
                    $iNewCoordinate = 0;
                }
            }
        }else{
            //loop the number of block
            for ($i = 1; $i <= $iBlockLength; $i++) {
                $iNewCoordinate--;
                //if higher than 8 go back to 0
                if($iNewCoordinate < 0){
                    $iNewCoordinate = 8;
                }
            }
        }
        return $iNewCoordinate;
    }   
}


$oGrid = new Grid;
$aGrid = $oGrid->getGridPath();

?>
<table>
<?php foreach ($aGrid AS $row): ?>
    <tr>
    <?php foreach ($row AS $col): ?>
        <td style="border: 1px solid red;"><?php echo $col; ?> &nbsp; </td>
    <?php endforeach; ?>
    </tr>
<?php endforeach; ?>     
</table>
 0
Author: Noam148, 2014-10-30 21:40:32