在网格中生成随机坐标路径

Question

我想要什么？

我想在PHP中编写一个函数或类/方法，它返回一个9x9网格（参见（代码：带路径的网格））中生成的路径的数组。下面是条件：

• 方块不能重叠
• 有一个方向路径（请参见下文：我拥有什么？）。此路径可以是随机的，并且需要方向。
• 可以在右侧/顶部退出并在左侧/底部继续路径（请参见下面的示例）。反之亦然。
• 步数是可变的，不能重叠。
• 返回一个数组（代码：带路径的网格）。我需要图像示例下方橙色点的坐标。实际上，从橙色点开始的坐标序列在数组中足以。但如果使用整个9x9数组网格更容易，则也可以。

我拥有什么？

• 一个空网格数组 (代码：空网格):
• 一个随机的起始位置（参见图像示例中的“Start”）
• 一个方向，在这种情况下为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),
)

- Noam148

Answer 1

这应该能让你开始（在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>";

}

- Wranorn

Answer 2

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

- Noam148

---

很高兴你能想出一些东西！希望我的也能在某种程度上有所帮助 :) - Wranorn