4
\$\begingroup\$

I am writing a "collision detection" in PHP and want to check if a specific "area" is still free in the two-dimensional target array.

I use the following code to do that, but I think there might be a better (= faster) solution than looping over every possible position in the array and check whether it's set or not.

public function CheckForCollision($top, $left, $size, $collision_array) {

       $possible_x = range($left, $left+$size-1);
       $possible_y = range($top, $top+$size-1);

       // Slow solution, improve this: Check every possible value in the $collision_array with our "might be"-values
       foreach($possible_x as $x)
       {
          foreach($possible_y as $y)
          {
             if($collision_array[$x][$y] == 1) { return false; break; }
          }
       }

       return true;
    }

Any ideas on this?

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! I hope you get some good answers! \$\endgroup\$ – Phrancis May 18 '15 at 23:17
  • \$\begingroup\$ Thank you very much, I´m looking forward to possible help out here. :-) \$\endgroup\$ – flomei May 18 '15 at 23:18
  • 1
    \$\begingroup\$ Not much optimization, but how about using in_array in inner loop? (it works really faster, cause it has native implementation at low level) \$\endgroup\$ – smt May 20 '15 at 10:15
  • \$\begingroup\$ Hi there! I am attempting to understand your question, but I am having some trouble. When you are using the word collision I would assume you are checking if a specific key/value already exists? Could you provide more context or a sample of the $collision_array? \$\endgroup\$ – AnotherGuy May 22 '15 at 14:13
3
\$\begingroup\$

If I have understood your question correctly you are seeking a function which can check if values of a 2-dimensional array equals FALSE. An example of such array structure could be:

$array = [
    0 => [0, 0, 0, 0, 0],
    1 => [0, 0, 0, 0, 0],
    2 => [0, 0, 0, 0, 0],
    3 => [0, 0, 0, 0, 0],
    4 => [0, 0, 0, 0, 0],
];

I have attempted to write an implementation from the context you have given. I have reduced your code down to a single for loop and opened the possibility to having any default value that evaluates to FALSE, such as false, null, 0 or an empty array. This is done through the native array_filter() function. I have also included some error checking. An example usage could be.

/*
 * Using array structure from previous example.
 *
 * Check if array elements starting at index 1 and 2
 * elements forward only contains values that equals
 * to FALSE.
 */
$valid = collisions($array, 1, 2);

Along with inline comments the code of the function should be pretty self explanatory.

/**
 * Check if the provided array has any values that does not
 * evaluate to FALSE in the given array range.
 *
 * @param array $array A two dimensional array.
 * @param int   $start An integer specifying an array index to start the check.
 * @param int   $size  An integer specifying how many array elements to check values for.
 *
 * @return bool Returns FALSE if there are collisions, TRUE otherwise.
 * @throws \OutOfRangeException
 * @throws \DomainException
 */
function collisions(array $array, $start, $size)
{
    /*
     * We ensure the outer array has only 
     * numeric array keys.
     */
    $array = array_values($array);

    /*
     * Check if starting index is out of range of the provided array.
     */
    if(!array_key_exists($start, $array)) {
        throw new OutOfRangeException('The specified starting index is out of range of the provided array.');
    }

    /*
     * Compute the upper boundary
     */
    $boundary = (int)$start + (int)$size;

    /*
     * Check if the amount of elements to check AFTER the specified starting
     * index is out of range of the provided array.
     */
    if(!array_key_exists($boundary, $array)) {
        throw new OutOfRangeException('The specified amount of elements to check exhausts the provided array.');
    }

    for($i = (int)$start; $i <= $boundary; $i++) {

        /*
         * Check if the current array value is an array.
         */
        if(!is_array($array[$i])) {
            throw new DomainException("Invalid type of array value at index {$i}. Expected an array, type of " . gettype($array[$i]) . ' given.');
        }

        /*
         * If the native function array_filter() doesn't have a second
         * argument, it will filter out any values corresponding to FALSE. I assume
         * an accepted value is 0, which evaluates to FALSE.
         *
         * Therefore of the resulting array is NOT empty there are
         * values which does not equal to 0 (zero).
         */
        if(array_filter($array[$i])) {
            return false;
        }

    }

    return true;
}

The error checking and the first line $array = array_values($array); can be removed if you are sure the provided array always has the correct structure and has numerical indexes. But I would strongly recommend to not doing so, as good error checking can help you when bugs occur.

Performance wise this shouldn't be too bad. The many if statements when checking for errors are somewhat slow, but should be negligible. As far as I know the for loop doesn't operate on a copy of the provided array as foreach otherwise would. This is only a concern if you are having huge arrays. If this is the case I would strongly recommend using an iterator.

Regarding performance. Premature optimization is almost always not the answer. I would suggest you write SOLID code. Then when you are done you can profile your application and look for the performance heavy blocks. Remember that if your application relies on a database the biggest performance gains are properly in writing highly optimized SQL queries. Of course there are exceptions. If this function is used extensively throughout your code it's always good to think about optimization.

Happy coding!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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