Generate a random coordinate path in a grid

Question

What I want?

I want in PHP a function or class/method thats return an array of a generate path in a grid (9x9) see (code: grid with path). This are the condition:

• The block cant overlapping eachother
• There is an direction path (see under: What do I had?). This path can be random and the directions are required.
• It is possible to exit on the right/top and continued the path on the left/bottom (see example below). Vice versa is also possible.
• The number of steps are variable and cannot overlap eachother.
• Return an array (code: grid with path). I Need the coordinates from the the orange dottes in the image example below. Actually are the coordinates in sequence in a array (from the orange dotes) enough. But if its easier to use the full 9x9 array grid, its okay.

What do I had?

• An array empty grid (code: empty grid):
• A random start position (see "Start" in image example)
• A direction in this case 1234123 (can be different) (1: up, 2: right, 3: down, 4: left)

Need extra information?

If you need extra information or something is not clear? 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 path (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 (Placed a demo @ http://tinker.bit-nibble-byte.com/grid.php )

Please forgive the alternate syntax, I hate braces.

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

}