Maze Generator

Me too. I obtain this:

| _ _ | | _||_ | | | | | | | | | | |_ | _ _|

Sorry:

| _ _ |
| _||_ |
| | | |
| | | | |
|_ | _ _|

Yes that is.

I'm sorry about before. I've been reading about markdown.
I try to paste my result for 6 2

 _ _ _ _ _ _ 
|  _ _   _  |
|  _  |_ _|_|
|  _|_ _ _ _|
|      _   _|
| | |_ _|  _|
|_|_ _ _|_ _|

Thank you! And sorry again. This is my 6 2

I've only just started looking at this one. However, I can confirm that I agree with Rodion's 3x3 but not the 5x5. I also agree with the 5x5 posted above by Mathias and with the 6x6 from Sergio.

Some part of Rodion's algorithm description does not match with the algorithm that he is actually using.

As Mathias suggests, a list of the order in which the cells were chosen for the 5x5 example would provide the possibility of deducing what is happening to create the difference.

I've tried to deduce as much as I can from the evidence available for the 5x5 maze. The first 15 rooms included in the maze agree between my algorithm and the example. For the 16th room my algorithm picks room (0,0) and extends it to the new room (1,0). The example appears to pick room (1,1) and then extends this to join to a new room at (1,0). I hope this is of some help.

Hi Friends! I'm very sorry for supposedly here is some inconsistency which I currently fail to spot.

Here is the "trace" of how the given 5x5 is generated, it runs like this:

    rnd(5) = 700446: 1
    rnd(5) = 2017459: 4
    rnd(1) = 880924: 0
picked 1:4
    rnd(3) = 540578: 2
connected: 0:4
    rnd(2) = 82776: 0
picked 1:4
    rnd(2) = 1883448: 0
connected: 1:3
    rnd(3) = 2063930: 2
picked 1:3
    rnd(3) = 588829: 1
connected: 2:3
...

e.g. we see every call to random generator and wherever every node is picked in the maze, added to it or removed from the further consideration.

Same with rows 119, 120:

picked 1:0
removed 1:0

(2,0) is free at this time.

However from (3,0) it does find the neighbor (2,0). Rows 140-142:

picked 3:0
    rnd(1) = 277993: 0
connected: 2:0

Where my program check if the cell on the east is free, I have added as a condition that 'y' must be different from zero, I have executed it and it is considered correct. The problem must be there, for some reason if y=0 it doesn't see the neighbor to the east.

Hi and thank you for detailed investigation, it really helps!

Hopefully now the code is fixed and could be retried.

The issue is somewhat curious - I thought myself too clever and instead of creating typical "neighbors" array like this:

[[0, -1], [1, 0], [0, 1], [-1, 0]]

I tried to wrote a very clever function using two school-like formulas:

$dx = round($x + sin($dir * M_PI / 2))
$dy = round($y - cos($dir * M_PI / 2))

also I was using associative array with keys constructed as strings from two coordinates, e.g. "$x:$y".

somewhat surprisingly PHP allows negative zeroes as result of rounding, which led to keys like "-0:1" instead of "0:1" - so sometimes cells were lost as Sergio explains :(

Please sorry for such a mistake and inconveinence, but as you see there was a little chance I could spot such bug without you :)

I didn't know there was such a thing as a negative zero. I don't have much knowledge of PHP, but I'll take note. Thank you!