Random path through a rectangle

Question

I want to write code to generate a random path through a rectangle of a given size.

I will start at point (0,0) and go up or right to reach xlim and ylim .

Here is my code

 y = 10; x = 10; yOld = 0; xOld = 0; figure axis([0 x 0 y]) while yOld < y && xOld < x DirectionChange = randi([0 1],1); if DirectionChange == 0 yNew = yOld + 1; xNew = xOld; else xNew = xOld + 1; yNew = yOld; end line ([xOld xNew],[yOld yNew],'LineWidth',3);hold on yOld = yNew; xOld = xNew; end line ([xNew x],[yNew y],'LineWidth',3);hold off 

The code has a while loop , and it ends when one of x or y reaches the limit.

So it works fine x = y .

However, when y > x more likely that the path will reach xlim earlier.

for 12 runs x = 10, y = 10 I get (I made it bright to look better!),

Setting x = 10, y = 20 , I get

As you can see, I lose randomness in the latter case, since the probability of reaching this limit is limited to x .

Any suggestions on how to keep randomness in case x~=y ?

Thanks.

Answer 1

You always need to take x steps to the right, and y - up. So make an array containing these steps in the form of encoded instructions (a simple array will be just fine here, we can use 0 for the horizontal step and 1 for the vertical). Then shuffle the array. This is guaranteed to hit the corner without any adjustments, and all possible paths will be equally likely (as random as possible).

 x = 10; y = 20; steps = [ zeros(1,x) ones(1,y) ]; steps = steps( randperm(x+y) ); figure hold on; xOld = 0; yOld = 0; axis([0 x 0 y]) for step = steps, if (step == 1) yNew = yOld + 1; xNew = xOld; else xNew = xOld + 1; yNew = yOld; end line ([xOld xNew],[yOld yNew],'LineWidth',3); yOld = yNew; xOld = xNew; end line ([xNew x],[yNew y],'LineWidth',3); hold off 

Answer 2

What you want to do is do P(x increases) = x/(x+y) and P(y increases) = y/(x+y) . Thus, the probability that x reaches its limit is the same as the probability that y reaches its limit.

Example:. For a given xlim of 5 and a given ylim of 10, create a random number from the continuous interval [0,1] . If this random number is less than 0.333, which is xlim/(xlim+ylim) , you should increase xOld . Otherwise, increase yOld .

Use rand , not randi .

Answer 3

One option is to specify the direction selection for the aspect ratio, for example.

 DirectionChange = rand(1); if DirectionChange < y/(x+y) yNew = yOld + 1; xNew = xOld; else xNew = xOld + 1; yNew = yOld; end 

Are there any requirements that need to be maintained? e.g. constant step size

EDIT: A better strategy to avoid hitting walls:

 DirectionChange = rand(1); % distance left to the end xLeft = x - xOld; yLeft = y - yOld; if DirectionChange < yLeft/(xLeft+yLeft) yNew = yOld + 1; xNew = xOld; else xNew = xOld + 1; yNew = yOld; end