भूलभुलैया डीएफएस का उपयोग कर पीढ़ी विफल रहता है और मैं नहीं जानता कि क्यों

Question

मैं सिर्फ कुछ आसान कलन विधि का उपयोग mazes उत्पन्न करने के लिए चाहता था, लेकिन मेरे सभी mazes के बाद एक की तरह लग रहे:

यहाँ एक टुकड़ा है जावा कोड का (एक whatVisit समारोह सही काम करता है, इस पर गौर नहीं करते हैं):

private void dfs(Point start, boolean[][] visited) { 
    Point nextCell = whatVisit(start, visited); 
    if(nextCell == null)  // if there's nothing to visit 
     return; 

    // mark current cell as visited 
    visited[start.y][start.x] = true; 
    // destroy the wall between current cell and the new one 
    borders[(start.y + nextCell.y)/2][(start.x + nextCell.x)/2] = true; 

    // start a new search from found cell 
    dfs(nextCell, visited); 
} 

private Point whatVisit(Point p, boolean[][] visited) { 
    Vector<Point>cells = new Vector<Point>(); // to store acessible cells 

    // lookaround 
    if(p.x - 2 >= 0 && !visited[p.y][p.x - 2]) 
     cells.add(new Point(p.x - 2, p.y)); 
    if(p.x + 2 < visited[0].length && !visited[p.y][p.x + 2]) 
     cells.add(new Point(p.x + 2, p.y)); 
    if(p.y - 2 >= 0 && !visited[p.y - 2][p.x]) 
     cells.add(new Point(p.x, p.y - 2)); 
    if(p.y + 2 < visited.length && !visited[p.y + 2][p.x]) 
     cells.add(new Point(p.x, p.y + 2)); 

    // instead of Random 
    Collections.shuffle(cells); 

    // returns null if there are no acessible cells around 
    if(cells.size() > 0) 
     return cells.get(0); 
    else return null; 
} 

और मुझे पता है क्यों यह काम नहीं करता! जब डीएफएस अंततः उस स्थान पर आती है जहां कोई सुलभ कोशिकाएं नहीं होती हैं, तो यह अभी शुरू होने के लिए बाहर जा रही है।

इसे कैसे ठीक करें और सही काम करने के लिए मजबूर करें?

धन्यवाद।

Answer 1

वास्तव में मुझे अभी भी यह नहीं मिलता है कि आप जिस भूलभुलैया को उत्पन्न करना चाहते हैं उसका उद्देश्य क्या है। लेकिन मैं आप के लिए कुछ सुझाव हैं:

1. , समन्वय ताकि भूलभुलैया नीरस नहीं होगा randomize करके अपने DFS एल्गोरिथ्म के 2 या 3 प्रारंभ बिंदु बनाएँ।

2. आपके एल्गोरिदम में, आप केवल प्रत्येक चाल में 1 पहुंच योग्य सेल का प्रयास करते हैं। प्रत्येक चाल में अधिक सुलभ सेल तक पहुंचने का प्रयास करें ताकि पथ समाप्त करने के लिए 1-रास्ता पथ न हो। (ऊपर अपने कोड से संपादित) (और यह भी कारण है कि अपने डीएफएस के बाद यह सुलभ सेल नहीं मिल सकता है शुरू करने के लिए वापस जाने के लिए)

यहाँ ऊपर मेरी 2nd विचार के अपने कोड है:

private void dfs(Point start, boolean[][] visited) { 
    ArrayList<Point> nextCell = whatVisit(start, visited); 
    if(nextCell == null)  // if there's nothing to visit 
     return; 

    // mark current cell as visited 
    visited[start.y][start.x] = true; 

    for (Point next : nextCell) // try new accessible cells 
    { 
     // destroy the wall between current cell and the new one 
     borders[(start.y + next.y)/2][(start.x + next.x)/2] = true;  
     // start a new search from found cell 
     dfs(next, visited); 
    } 
} 

private ArrayList<Point> whatVisit(Point p, boolean[][] visited) { 
    Vector<Point>cells = new Vector<Point>(); // to store acessible cells 

    // lookaround 
    if(p.x - 2 >= 0 && !visited[p.y][p.x - 2]) 
     cells.add(new Point(p.x - 2, p.y)); 
    if(p.x + 2 < visited[0].length && !visited[p.y][p.x + 2]) 
     cells.add(new Point(p.x + 2, p.y)); 
    if(p.y - 2 >= 0 && !visited[p.y - 2][p.x]) 
     cells.add(new Point(p.x, p.y - 2)); 
    if(p.y + 2 < visited.length && !visited[p.y + 2][p.x]) 
     cells.add(new Point(p.x, p.y + 2)); 

    // returns null if there are no accessible cells around 
    if(cells.size() > 0) 
    { 
     ArrayList<Point> tmp = new ArrayList<Point>(); 
     // randomize how many cell that will be returned 
     int x = (int)(Math.random()*cells.size()) + 1; 
     if (x > cells.size()) 
      x = cells.size(); 
     Collections.shuffle(cells); 
     for (int i = 0; i < x; i++) 
      tmp.add(cells.get(i)); 
     return tmp; 
    } 
    else return null; 
} 

आशा इस में मदद मिलेगी;)

Answer 2

ऐसा लगता है कि तुम सिर्फ बाहर प्रति सहिष्णु रहे हैं और छोड़ने जब भी आप एक अंत में मृत्यु तक पहुंचने लग रहा है। इसके बजाए, आपको तब तक बैकट्रैक करना चाहिए जब तक आपको कोई ऐसा सेल न मिल जाए जो अभी भी सुलभ पड़ोसियों के पास है, और वहां से एल्गोरिदम जारी रखें। ऐसा करने का सामान्य तरीका एक ढेर के साथ है: जब आप उन्हें देखते हैं तो आइटम दबाएं, बैकट्रैक पर पॉप करें। कुछ इस तरह:

if (nextCell == null) { // You've reached a dead-end 
    if (stack.empty()) // base-case, bail out 
    return; 

    dfs(stack.pop(), visited); // backtrack 
} else { 
    stack.push(nextCell); 

    visited[start.y][start.x] = true; 
    borders[(start.y + nextCell.y)/2][(start.x + nextCell.x)/2] = true; 
    dfs(nextCell, visited); 
} 

इसके बजाय शुरू करने के लिए वापस जाने के