Create a random coordinate path in the grid

Question

What I need?

I want in PHP a function or class / method that returns an array of the generation path in a grid (9x9), see (code: grid with path). This condition:

• The block cannot overlap
• There is a directional path (see below: What did I have? ). This path may be random and guidance is required.
• You can exit on the right / top and continue the path on the left / bottom (see example below). It is also possible and vice versa.
• The number of steps is variable and cannot overlap with each other.
• Returns an array (code: grid with contour). I need the coordinates from the orange dots in the example image below. In fact, these are the coordinates in the sequence in the array (from orange). But if it’s easier to use a full grid of 9x9 arrays, that's all right.

What did I have?

• Array of an empty grid (code: empty grid):
• Starting position random (see "Start" in the example image)
• The direction in this case is 1234123 (it can be different) (1: up, 2: right, 3: down, 4: left)

Need more info?

If you need more information or something is unclear? please ask me. Thanks!

code: empty grid:

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), ) 

code: grid with contour (1 = start, 8 = end):

 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), ) 

Answer 1

This should get you started (posted demo @ http://tinker.bit-nibble-byte.com/grid.php )

Please forgive the alternative syntax, I hate parentheses.

 <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>"; } 

Answer 2

@Wranorn Thank you for your reply! I am testing it and it works. In the meantime, I also created a script that generate a grid. I hope one of these scenarios helps other people with the same question. Here is my snippet:

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