2

My problem consists of finding a path from a given start to a given finish cell in a 2-dimensional array filled with obstacles (cells that I cannot access). While I think that I have found an algorithm that finds the optimal path each time given that the obstacle cells are known, the thing is that those obstacle cells are not specified beforehand and must be randomly generated each time I'm starting the program.

I'm stuck trying to find an algorithm that pseudo-randomly generates those obstacles while ensuring that each time a path from start to finish is indeed available. Anybody got any ideas? Thanks in advance.

This is what I've thought of so far for the obstacles (python):

free=N*N-4*(N-1)
obstacles=round(free*p)
#for j in (1, N):
obstacle_free_points = {S, F}
count=0
#j = j + 1
j=self.prims(N,S,F)
while count<obstacles:
    x=randrange(1,N-1)
    y=randrange(1,N-1)
    if (x,y) not in obstacle_free_points or j:
        self.grid[x][y]=1
        count=count+1

And this is my BFS for finding the path afterwards (python):

def bfs(self,N,S,F):
   previous=np.zeros((N, N),dtype=object)
   seen=set()
   q=Queue()
   q.put(S)
   while not q.empty():
       node=q.get()
       if node==F:
           path=[F]
           while node!=S:
               path.append(previous[node[0]][node[1]])
               node=previous[node[0]][node[1]]
           return path
       for n in grid.adjacent(self,node):
           if n not in seen:
               q.put(n)
               previous[n[0]][n[1]]=node
       seen.add(node)
martineau
  • 119,623
  • 25
  • 170
  • 301
Stephon_Gordon
  • 35
  • 2
  • 9
  • 1
    When creating the obstacles, you could first (randomly) define a path and only put obstacles on (random) fields apart from this path. That way you would ensure that at least one path exists. – Jonathan Scholbach Nov 27 '19 at 11:52
  • I think that if I do this, then the BFS that finds the optimal path will mostly end up with the path that I predetermined before creating the obstacles, won't it? When my path-searching algorithm starts, it's supposed to be an entirely new problem with given variables of obstacles, start cell and finish cell. – Stephon_Gordon Nov 27 '19 at 11:57
  • This entirely depends on the obstacle density. With few objects in the way it will be quite improbable that the optimal path is the same - the preliminary path will be superfluous then most of the time anyway. You could restrict your "randomness" so that there will exist a solution always but with a "blind" version like the one you implemented, there is no way around a test for the global criterion. – Vroomfondel Nov 27 '19 at 12:21
  • The obstacle density is not known or predetermined somehow. The purpose of the algorithm I am trying to create is filling the array with obstacles in a non-specified way, but even if the obstacle density ends up "randomly" being 90% of the array, still making sure that a path always exists. – Stephon_Gordon Nov 27 '19 at 12:30
  • Are the start and finish always on the edges? That makes easier. – Matt Timmermans Nov 27 '19 at 13:31
  • A maze generation algorithm might not be exactly what you want, but perhaps you can get some inspiration: https://en.wikipedia.org/wiki/Maze_generation_algorithm – kaya3 Nov 27 '19 at 14:26
  • Related: [How to generate a maze with more than one successful path?](https://stackoverflow.com/q/22305644/1639625) – tobias_k Nov 27 '19 at 14:46
  • That does not seem to be a problem to my eye. Your programme can easily "forget" the existing path. And it is not said by any means that this path will be an optimal path. If the obstacle density is low, there will probably be shorter paths. – Jonathan Scholbach Nov 27 '19 at 15:39
  • Maybe the solution is to modify your path-finding algorithm to gracefully handle the case of there not being a path from start to end. That simplifies your generation problem and also makes your code more robust. – Jim Mischel Nov 27 '19 at 21:19

1 Answers1

0

If the obstacle density is not predetermined, then this may work well for you:

  1. Start with an obstacle in every square, except the start and end.
  2. Randomly clear squares until the start square is connected to the end square.
  3. Clear as many additional squares as you want.

You can use a disjoint set data structure to determine when the start and end become connected: https://en.wikipedia.org/wiki/Disjoint-set_data_structure. Initially, each square is in its own set, and when you clear a square its set merges with the sets of all its clear neighbors.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87