0
\$\begingroup\$

I created script that generates maze or some kind of dungeons that looks like this: http://s13.postimage.org/4uify3jxj/blocks.jpg

I have problem with optimize, because when I've tried to add blockade to not overwrite existing blocks, script is executing most of times more than 60s.

So... any ideas how can I optimize this?

<?php
    class dungeon_block {
        public $left='EMPTY', $right='EMPTY', $top='EMPTY', $bottom='EMPTY', $visited=false, $action='NONE';
        public $x, $y;
        public function __construct($x, $y) {
            $this->x = $x;
            $this->y = $y;
        }
    }

    function rollDirection() 
    {
        $direction = rand(0,3);
        $dir = '';
        switch($direction)
        {
            case 0: $dir = 'LEFT'; break;
            case 1: $dir = 'RIGHT'; break;
            case 2: $dir = 'TOP'; break;
            case 3: $dir = 'BOTTOM'; break;
        }
        return $dir;
    }
?>

<div class='dungeon'>
    <?php
        $count = rand(1,10);
        $count = 20;
        $index = 0;
        $blocks = array();
        $blocks[$index] = new dungeon_block(0,0);
        $blocks[$index]->left = "BLOCKED";
        $blocks[$index]->top = "BLOCKED";
        $xy = array(array());
        $dirOK = false;
        $width = 25; $height = 25;
        $x; $y;
    echo "<div class='dungeon_block' style='top: ".$blocks[$index]->y."; left: ".$blocks[$index]->x."' id='block-".$index."'>S</div>";
        $xy[0][0] = true;
        while($count >=1 ) 
        {
            while($dirOK == false) 
            {
                $dir = strtolower(rollDirection()); 
                if($blocks[$index]->$dir == 'EMPTY') 
                {
                    $x = $blocks[$index]->x;
                    $y = $blocks[$index]->y;
                    $br = '';
                    $left='EMPTY';
                    $right='EMPTY';
                    $top='EMPTY';
                    $bottom='EMPTY';                    
                    switch($dir) 
                    {
                        case 'left': $x -= $width; $right = 'BLOCKED';break;
                        case 'right': $x += $width; $left = 'BLOCKED';break;
                        case 'top': $y -= $height; $bottom = 'BLOCKED';break;
                        case 'bottom': $y += $height; $top = 'BLOCKED'; $br = '<br />'; break;
                    }   
                    $i = 1;
                    if($x  < 0 || $y < 0) {
                        if($i > 5) $dirOK = true;
                        $i++;
                        continue;
                    }
                    $i = 1;
                    if(array_key_exists($x, $xy)) {
                        if(array_key_exists($y, $xy[$x])) {
                            if($i > 15) $dirOK = true;
                            $i++;
                            continue;
                        }
                    }
                    $dirOK = true;
                } 
            }
            $index++;
        echo "<div style='top: ".(int)$y."px; left: ".(int)$x."px;' class='dungeon_block' id='block-".$index."' >". $dir[0] ."</div>";      
            $blocks[$index] = new dungeon_block($x, $y);    
            $blocks[$index]->left = $left;
            $blocks[$index]->right = $right;
            $blocks[$index]->bottom = $bottom;
            $blocks[$index]->top = $top;
            $xy[$x][$y] = true;
            $dirOK = false;
            $count--;
        }

    ?>  
</div>

Edited code:

<?php

    function rollDirection() 
    {
        $direction = rand(0,3);
        $directions = array(
            'left',
            'right',
            'top',
            'bottom'
        );
        return $directions[$direction];
    }

    function drawBlock($b)
    {
        echo "<div class='dungeon_block' style='top: ". $b['y'] ."px; left: ". $b['x']."px;' id='block-". $b['index'] ."'>".$b['text']."</div>";
    }

?>

<div class='dungeon'>
    <?php
        $count = 10;
        $length = 25;
        $blocks = array();
        $blocks[0] = array(
            'text'           => 'S', // for tests
            'index'          => 0,
            'x'              => 0,
            'y'              => 0
        ); 
        drawBlock($blocks[0]);  // set start block
        for($i=0; $i < $count; $i++)  // draw others
        {
            $x = $blocks[$i]['x']; // get x from the previous block
            $y = $blocks[$i]['y']; // get y from the previous block
            $dir = rollDirection();
            switch($dir) 
            {
                case 'left': $x -= $length; break;
                case 'right': $x += $length; break;
                case 'top': $y -= $length; break;
                case 'bottom': $y += $length; break;
            }   
            $x = (int)$x;
            $y = (int)$y;
            // check if x or y are less than 0 - that is forbidden
            // if so, repeat roll for that block
            if($x < 0 || $y < 0) {
                $i--;
                continue;
            }
            $blocks[$i+1] = array(
                'text'           => $i.$dir[0], // for tests
                'index'          => $i,
                'x'              => $x,
                'y'              => $y
            ); 
            drawBlock($blocks[$i+1]);
        }
    ?>  
</div>

I have to think out this problems too: a) Blocks cannot overwrite themselves. (For example x=0 y=0 and 15 blocks laters, again x=0 y=0, so first blocks won't be visible). I have written this function:

function checkIsSpotFree($x, $y, $blocks, $length) // checks if spots is free and returns nearset free direction, if exist
    {
        $neighbours = array( 
                            'left' => array('free' => true,
                                            'x' => $x -= $length,
                                            'y' => $y
                                            ),
                            'right' => array('free' => true,
                                            'x' => $x += $length,
                                            'y' => $y
                                            ),
                            'top' => array('free' => true,
                                            'x' => $x,
                                            'y' => $y -= $length
                                            ),
                            'bottom' => array('free' => true,
                                            'x' => $x,
                                            'y' => $y += $length
                                            ),
                            'center' => array('free' => true,
                                            'x' => $x,
                                            'y' => $y
                                            )
                            );
        foreach($blocks as $block) 
        {
            if($neighbours['left']['x'] == $block['x'] && $neighbours['left']['y'] == $block['y'])
                $neighbours['left']['free'] = false;
            if($neighbours['right']['x'] == $block['x'] && $neighbours['right']['y'] == $block['y'])
                $neighbours['right']['free'] = false;
            if($neighbours['top']['x'] == $block['x'] && $neighbours['top']['y'] == $block['y'])
                $neighbours['top']['free'] = false;
            if($neighbours['bottom']['x'] == $block['x'] && $neighbours['bottom']['y'] == $block['y'])
                $neighbours['bottom']['free'] = false;
            if($neighbours['center']['x'] == $block['x'] && $neighbours['center']['y'] == $block['y'])
                $neighbours['center']['free'] = false;
        }
        $free_spot = null; // declare nav to next free spot, default null
        foreach($neighbours as $d)
        {
            if($d['free'] == true && $d['x'] >= 0 && $d['y'] >= 0) 
            {
                $free_spot = $d;
                break;
            }
        }   
        return $free_spot;
    }   

but there is still problem. If will be this situation ("B" refers to block, "X" proposal position):

X 
->
BX 
->
BBX 
->
BBB 
X  
 ->
BBB
B 
X  
->
BBB
B
BX   
->
BBB
B
BBX 
->
BBB
B X 
BBB 
->
BBB
BXB
BBB 
->
BBB
BXB
BBB
X = ?

There is no possible direction for new block, because it is surrounded by existings blocks. Than script runs into wall and endless loop. Any ideas how can I resolve this?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The first part of your question ("how do I optimize this") was on-topic. The rest of the question ("how to I add this functionality") was off-topic. Questions can be re-opened if they are thoroughly edited. \$\endgroup\$ – Adam Sep 19 '12 at 17:04
2
\$\begingroup\$

Begin your optimizations by not having classes for the sake of having a class. For instance, dungeon_block is not a class. You made it one, but nothing about it says that it is one. Its just a glorified data repository. OOP does not just mean instantiating a class, there's more to it. Intercommunication, encapsulation, and extendability to name a few. Maybe if this were refactored for the map and held multiple blocks, then I could almost see using a class. But even then it wouldn't follow all OOP logic and would just be a style choice. As it stands you'd be better off with an associative array, which is what I will show you in the following review.

Note: Once you've got this working, you might consider implementing some sort of cache, so that these maps don't have to be regenerated. This will greatly assist in load times. A good method might be to store these maps as JSON on some kind of database. Or maybe just directly as JSON files. I suggest JSON because it can be directly decompiled and recompiled with little effort by maintaining its structure, as well as providing JS support.

A better way to determine direction might be to use an array instead of a switch. I say "might" because I have not profiled it, I'll leave that to you. Either way, here is another way.

$directions = array(
    'LEFT',
    'RIGHT',
    'TOP',
    'BOTTOM'
);

return $directions[ $direction ];

Consider breaking up the rest of this code into functions, even if you don't end up reusing them. It will make your code much easier to maintain and so much easier to read. To help get you started, the first chunk could be a function called, init(), and could be used to initiate the map. I'll leave you to figure out the implementation and how to break up the rest.

What is the purpose of defining $count to a random number if you are then not going to do anything with it? Its not much of an inefficiency, but it still is one. Also, why count? Count usually means a dynamically retrieved length or amount, not a static number that has been hardcoded in. For such instances I would expect to see a constant named MAX_XXX, where XXX is what is being counted.

$count = rand(1,10);
$count = 20;

Since we aren't using a class anymore, or rather, I won't because I'm not going to redo all this code into a class for you, a better way to go about setting up the blocks would be to just use arrays. If you begin by setting up a template array, you can then change specific characteristics on each iteration. For instance:

$block = array(
    'left'           => 'EMPTY',
    'right'         => 'EMPTY',
    'top'           => 'EMPTY',
    'bottom'      => 'EMPTY',
    'visited'       => FALSE,
    'action'       => 'NONE',
    'x'              => 0,
    'y'              => 0
);

//for demonstration purposes
$blocks = array();
for( $i = 0; $i < $count ; $i++ ) {
    $blocks[] = $block;
    if( Perform checks to determine if changes are necessary ) {
        //make changes
        $blocks[ $i ][ XXX ] = YYY;
    }
}

Why are you reinventing a for loop? Your while loop essentially does the same exact thing, only more messily. I think at one point the while loop was faster, which is why it was sometimes preferred, but I don't think that is the case anymore. Either way, the VERY slight speed benefit is not worth the loss in legibility. Code for legibility before speed. Often times there is no difference between legible code and efficient code.

$i = 0;
while( $i < 100 ) { $i++ }
//compared to
for( $i = 0; $i < 100 ; $i++ ) { }

A single array declaration is fine for $xy. No need to do so twice.

$xy = array();

When comparing variables to their boolean value, it is not necessary to explicitly do so unless specifically checking that variables type as well.

$dirOK = "FALSE";
while( ! $dirOK ) {//TRUE because "FALSE" == FALSE
while( $dirOK == FALSE ) {//TRUE because "FALSE" == FALSE
while( $dirOK === FALSE ) {//FALSE because "FALSE" !== FALSE

If you need the directions in lowercase, why did you capitalize them? Don't use functions that you don't need.

$dir = strtolower(rollDirection());

Not that it will be an issue if you lose the class, but always avoid variable variables. These are hard to debug for and are generally considered bad smell. There are a few exceptions, but this is definitely not one of them.

$blocks[$index]->$dir 

What is the point of $br? You define it as empty, then redefine it as the HTML break tag later, but you never use it anywhere that I can see.

With the set up I showed you above, the default direction values will not be necessary, instead, in the switch statement you should just directly modify the block.

case 'left':
    $blocks[ $index ] [ 'x' ] -= $width;
    $blocks[ $index ] [ 'right' ] = 'BLOCKED';
break;
//etc...

I'm confused... What exactly is the purpose in incrementing $i in these two statements? It doesn't do anything. Every time this loop iterates $i is reset to 1, then it is used to perform a check that is always FALSE, before being incremented and restarting the process over again. The incremented version is never used.

$i = 1;
if($x  < 0 || $y < 0) {
    if($i > 5) $dirOK = true;
    $i++;
    continue;
}
$i = 1;
if(array_key_exists($x, $xy)) {
    if(array_key_exists($y, $xy[$x])) {
        if($i > 15) $dirOK = true;
        $i++;
        continue;
    }
}

Additionally, always use braces {} on your statements. It helps with legibility and ensures that there are no issues with your code. Even PHP agrees that neglecting these braces is bad because it CAN cause issues in the code. Besides, a better way would just be to set $dirOK's value to the return value of that expression.

$dirOK = $i > 5;

I'm having a lot of trouble following this code. I'm sure there's more I could help you with, such as the repetition I'm seeing. Not that I could explain it coherently enough right now. Make some of these suggested improvements and leave me a comment and I'll take another look. If you do decide to upload a revised version, DON'T delete the previous code, add it below the existing code.

UPDATE

First of all, much better. I don't feel quite so lost anymore :)

Here's something I missed yesterday: The magic number, "3", in $direction should be converted to use the count of $directions. Or, as I'll point out later, you might want to pass a maximum "roll" as a parameter.

$numDirections    = count( $directions );
$direction        = rand( 0, $numDirections );

You missed the first function I mentioned yesterday. Here's how I'd write it, you can rewrite it without compact() if you wish. Not everyone seems to like compact() or its counterpart extract() because they are hard to debug and read, but I think you can get away with it here.

function setBlock( $text, $index, $x, $y ) {
    $block = compact( 'text', 'index', 'x', 'y' );

    drawBlock( $block );

    return $block;
}

Now, the above function is the beginning of that repetition I mentioned yesterday. You manually set the first block before the loop, then you set each other block inside the loop. I understand why you are doing it, I just don't think it's necessary. If its something you think feasible, great, if not let me know why and I'll see if there is something else I can come up with. Now, a question first: Why are you jumping the x and y coordinates 25 at a time? Wouldn't these only move one at a time depending on the direction of travel? I'm going to assume so for now, if nothing else you might be able to apply this somewhere else. So first thing, let's refactor this loop a little. The incremental $i seems unnecessary when we already have two other incrementals to play with. I demonstrated using $i yesterday because I did not want to introduce the following until your code was updated.

for( $x = 0, $y = 0; $y < $MAX_Y; $x++ ) {
    $blocks[] = setBlock( $text, $index, $x, $y );

    if( $x == $MAX_X ) {
        $y++;
        $x = 0;
    }
}

$MAX_X and $MAX_Y are probably just $count or $width and $height, but I wasn't sure, so I just assigned them descriptive names so you can determine what they should be.

Now, the above loop is just for demonstration, it doesn't do everything for you. You will still have to check direction and all that other fun stuff. Speaking of, I mentioned earlier that I would show you why you might wish to pass a maximum roll as a parameter to rollDirection(). This is because you have already demonstrated that you do not want your x and y coordinates to go negative. So, if you adjust how those directions are set up in the array you can then adjust the maximum random number generated so that it excludes that index. if( $x - $length < 0 ), and the same for the y axis. This will reduce the amount of "rerolls" you have to do, which might actually be where most of your lag is coming from.

Typecasting the x and y coordinates seems pointless. They start off as integers and the only thing you ever do to them is add or subtract other known integers. So long as the variables you add to it are always integers so will be the outcome.

$x = (int)$x;
$y = (int)$y;
//In this case this is the same as $x = $x && $y = $y
\$\endgroup\$
4
  • \$\begingroup\$ First of all - thanks you for the most helpful answer. I have edited code and edited questions with new code. However I feel like I have to explain something first. The $i=1; before each loop was some kind of security mechanism that prevent endless loop - if it runs more than x, force break. With updated code maze is being generating, but there still left this critical problems: maze will be regenerating each user start a new one, it has to be saved in database to easily restored and with positions of user and blocks cant overwrite themselves, like it is right now. \$\endgroup\$ – Aylard Aug 20 '12 at 23:25
  • \$\begingroup\$ @Aylard: I updated my answer. To the best of my knowledge, the $i was not doing anything. It kept resetting on each iteration so those if statements that used them were never true. \$\endgroup\$ – mseancole Aug 21 '12 at 15:23
  • \$\begingroup\$ thanks for update yours reply! I see I forgot to explain some things. I have to have set of generated blocks, so I can later easily re-create exact same maze. $width,$height,$length are the same in value of 25, because of CSS style. Each block has 15width+10padding, so 25. $x and $y are margins of blocks as you can see in drawBlock() function. $x = (int)$x; is so, because some times $x was NULL which in CSS caused some troubles. However I agree with you for $directions[rand(0, count($directions)];, thanks! I've updated question with some other problems. \$\endgroup\$ – Aylard Aug 21 '12 at 20:49
  • \$\begingroup\$ @Aylard: I'm not sure I understand this latest problem. It sounds like you are trying to shift the screen with the player's movements? If, as it appears, you want to do this one row at a time, that will be a bit difficult. Either way, you can push part or all of the current map array into a JSON object and save it on the server, or in a local variable, until needed again. This will allow you to reuse the coordinates. However, I don't think thats a good idea as it will require a lot of new "memory" variables for saving position on each map and order. It will start getting confusing and bulky. \$\endgroup\$ – mseancole Aug 23 '12 at 13:14

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