The problem is similar to rat-maze problem. I have given an 2-d array MxN. each cell of an array is either 1 or 0 ,where 1 means blocked. I have given 2 points (starting point and ending point). I have to go from start index to end index. But the catch is 1) Path should be random. 2) There should be some parameter which allow me to decide how much random it can be. (i.e how crazily it should wander before reaching to its destination.) 3) Path should not intersect itself.(like a snake game).
This algorithm is needed to create population (randomly) which will used as input for genetic model for further optimize it. For now i have used bfs and created one solution. But the problem is i cannot create any no of random path with this (which i will later use as population) + i'm unable to formalize the idea of how much random it should be.
This is my code that only produces min path by using bfs
def isSafe(x,y,length):
if ((x<length) and (x>-1) and (y<length) and (y>-1)):
return True;
return False;
def path(room,x1,y1,x2,y2,distance):
roomSize=len(room);
if ((x1==x2) and (y1==y2)):
room[x1][y1]=distance+1
return
queue=[[x1,y1]]
room[x1][y1]=0
start=0
end=0
while start<=end:
x,y=queue[start]
start+=1
distance=room[x][y]
for i in [-1,1]:
if isSafe(x+i,y,roomSize):
if room[x+i][y]=="O":
queue.append([x+i,y])
room[x+i][y]=distance+1
end+=1;
for i in [-1,1]:
if isSafe(x,y+i,roomSize):
if room[x][y+i]=="O":
queue.append([x,y+i])
room[x][y+i]=distance+1
end+=1;
def retrace(array,x1,y1,x2,y2):
roomSize=len(array)
if not (isSafe(x2,y2,roomSize)):
print("Wrong Traversing Point");
if type(array[x2][y2])==str:
print("##################No Pipe been installed due to path constrained################")
return [];
distance=array[x2][y2];
path=[[x2,y2]]
x=0
while not (array[x2][y2]==0):
if ((isSafe(x2+1,y2,roomSize)) and type(array[x2+1][y2])==int and array[x2+1][y2]==array[x2][y2]-1):
x2+=1;
path.append([x2,y2]);
elif ((isSafe(x2-1,y2,roomSize)) and type(array[x2-1][y2])==int and array[x2-1][y2]==array[x2][y2]-1):
x2-=1;
path.append([x2,y2])
elif ((isSafe(x2,y2+1,roomSize)) and type(array[x2][y2+1])==int and array[x2][y2+1]==array[x2][y2]-1):
y2+=1;
path.append([x2,y2]);
elif ((isSafe(x2,y2-1,roomSize)) and type(array[x2][y2-1])==int and array[x2][y2-1]==array[x2][y2]-1):
y2-=1;
path.append([x2,y2]);
return path;
Aucun commentaire:
Enregistrer un commentaire