Computer Science Canada

BFS algorithm in grids/mazes
Author:  Panphobia [ Sun Nov 18, 2012 11:03 pm ]
Post subject:  BFS algorithm in grids/mazes
Ok so I know the concept of a BFS, but the thing is I still do not know exactly how to implement it. I am just asking how would I lets say with a BFS, in either java or python, doesnt matter really, get the shortest path from A-B with this grid/maze and the # are walls
code:
A.........
##....##..
.####...##
..........
.......###
B.........
####...###
..........
#...#.###.
..........
If you could explain it in laymens terms, or a code example would be great!
Author:  DemonWasp [ Mon Nov 19, 2012 1:15 am ]
Post subject:  RE:BFS algorithm in grids/mazes
A Breadth-First Search works like this:

code:

nodes-to-search = {node A}
while nodes-to-search is not empty, do:
    get closest from nodes-to-search
    if closest is B, then
        return the path stored in closest
    else
        add neighbours(closest) to nodes-to-search (ignoring nodes which have already been searched or are duplicates


There's some complication to computing the path, but it works like this:
- when you add neighbours(closest), assign "closest" as the "parent" of each neighbour
- then the "parent" of each node points to the node it was discovered from
- by following one parent to the next, you can get from B to A
- reverse that path to get from A to B
Author:  Panphobia [ Mon Nov 19, 2012 1:18 am ]
Post subject:  RE:BFS algorithm in grids/mazes
So node-to-search is a set?
Author:  mirhagk [ Mon Nov 19, 2012 9:11 am ]
Post subject:  RE:BFS algorithm in grids/mazes
Hey DemonWasp, I think you're confusing dijisktras with BFS. Breadth First Search is nearly identical to Depth First Search, the difference being which node you check next. With DFS you check the last node you discovered whereas with BFS you check the first one you discovered.

Essentially you get a queue (which is something that you add items to the end, but get items from the front, so the items you get are the first items you get out. It's FIFO unlike stacks which are LIFO).

Every time you discover a new node you add it to the queue, and each time in the while loop you grab the first thing from the queue, and check if it's the end, and if not you add new neighbours to the queue.
Author:  mirhagk [ Mon Nov 19, 2012 9:31 am ]
Post subject:  Re: BFS algorithm in grids/mazes
Python:

def DFS(x,y,Map):
    if (Map[x][y]=="exit"): #check if we're at the exit
        return [(x,y)] #if so then we solved it so return this spot
    if (Map[x][y]!="path"): #if it's not a path, we can't try this spot
        return []
    Map[x][y]="explored" #make this spot explored so we don't try again
    for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]: #new spots to try
            result = DFS(i[0],i[1],Map) #recursively call itself
            if len(result)>0: #if the result had at least one element, it found a correct path, otherwise it failed
                result.append((x,y)) #if it found a correct path then return the path plus this spot
                return result
    return [] #return the empty list since we couldn't find any paths from here

from collections import deque
def BFS(x,y,Map):
    queue = deque( [(x,y,None)]) #create queue
    while len(queue)>0: #make sure there are nodes to check left
        node = queue.popleft() #grab the first node
        x = node[0] #get x and y
        y = node[1]
        if Map[x][y] == "exit": #check if it's an exit
            return GetPathFromNodes(node) #if it is then return the path
        if (Map[x][y]!="path"): #if it's not a path, we can't try this spot
            continue
        Map[x][y]="explored" #make this spot explored so we don't try again
        for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]: #new spots to try
            queue.append((i[0],i[1],node))#create the new spot, with node as the parent
    return []
           
def GetPathFromNodes(node):
    path = []
    while(node != None):
        path.append((node[0],node[1]))
        node = node[2]
    return path
       
def GetMap():
    return [
        ["wall","wall","wall","wall","wall","wall","wall","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","wall","wall","path","wall","path","path","wall"],
        ["wall","path","path","path","wall","wall","path","wall"],
        ["wall","path","wall","path","path","path","path","wall"],
        ["wall","path","wall","wall","wall","wall","path","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","wall","wall","exit","wall","wall","wall","wall"]
            ]

def DrawMap(Map,path):
    for x in range(0,len(Map)):
        for y in range(0,len(Map[x])):
            if ((x,y) in path):
                assert Map[x][y] in ("path","exit")
                print("-",end="")
            elif (Map[x][y]=="wall"):
                print("#",end="")
            elif (Map[x][y]=="exit"):
                print(".",end="")
            else:
                print(' ',end="")
        print()

print("unsolved")
DrawMap(GetMap(),[])
print("\n")
print("solved with DFS")
print("path is ",len(DFS(1,1,GetMap()))," spots long")
DrawMap(GetMap(),DFS(1,1,GetMap()))
print("\n")
print("solved with BFS")
print("path is ",len(BFS(1,1,GetMap()))," spots long")
DrawMap(GetMap(),BFS(1,1,GetMap()))


As you can see from this updated example (from the one I sent you). BFS is very similar to DFS, with only the order you check nodes changed.

The example map has been changed to show that DFS and BFS often find very different solutions, and that BFS allows finds a path that has the shortest number of nodes, whereas DFS does not.

You could also create many optimizations from this, but you need to make sure you understand the algorithm before you do so.
Author:  Panphobia [ Mon Nov 19, 2012 9:51 am ]
Post subject:  RE:BFS algorithm in grids/mazes
so this is a BFS right? not a DFS because your method tells me its DFS O:
Author:  Panphobia [ Mon Nov 19, 2012 9:53 am ]
Post subject:  RE:BFS algorithm in grids/mazes
never mind lol, i will try to convert the bfs to java Very Happy
Author:  mirhagk [ Mon Nov 19, 2012 9:54 am ]
Post subject:  RE:BFS algorithm in grids/mazes
The code includes both a BFS and a DFS for comparison. The 2nd method is BFS, the first is DFS
Author:  Panphobia [ Mon Nov 19, 2012 10:20 am ]
Post subject:  Re: BFS algorithm in grids/mazes
This is my current code edited from yours, how does it not work
code:
import collections
def BFS(x,y,Map):
    queue = collections.deque( [(x,y,None)]) #create queue
    while len(queue)>0: #make sure there are nodes to check left
        node = queue.popleft() #grab the first node
        x = node[0] #get x and y
        y = node[1]
        if Map[x][y] == "B": #check if it's an exit
            return GetPathFromNodes(node) #if it is then return the path
        if (Map[x][y]!="*"): #if it's not a path, we can't try this spot
            continue
        Map[x][y]="explored" #make this spot explored so we don't try again
        for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]: #new spots to try
            queue.append((i[0],i[1],node))#create the new spot, with node as the parent
    return []
           
def GetPathFromNodes(node):
    path = []
    while(node != None):
        path.append((node[0],node[1]))
        node = node[2]
    return path
       
def GetMap():
    return [
        ["#","#","#","#","#","#","#","#"],
        ["#","A","*","*","*","*","*","#"],
        ["#","#","#","*","#","*","*","#"],
        ["#","*","*","*","#","#","*","#"],
        ["#","*","#","*","*","*","*","#"],
        ["#","*","#","#","#","#","*","#"],
        ["#","*","*","*","*","*","*","#"],
        ["#","#","#","B","#","#","#","#"]
            ]

def DrawMap(Map,path):
    for x in range(0,len(Map)):
        for y in range(0,len(Map[x])):
            if ((x,y) in path):
                assert Map[x][y] in ("*","B")
                print("-")
            elif (Map[x][y]=="#"):
                print()
            elif (Map[x][y]=="B"):
                print(".")
            else:
                print(' ')
        print()

print("solved with BFS")
print("path is ",len(BFS(1,1,GetMap()))," spots long")
DrawMap(GetMap(),BFS(1,1,GetMap()))
Author:  mirhagk [ Mon Nov 19, 2012 10:28 am ]
Post subject:  RE:BFS algorithm in grids/mazes
Change A to * in your map. The starting point should be determined by the caller, not the map. If the starting point isn't * then it stops searching instantly.

You've also really messed up the DrawMap part. It should look like
code:

            if ((x,y) in path):
                assert Map[x][y] in ("*","B")
                print("-",end="")
            elif (Map[x][y]=="#"):
                print("#",end="")
            elif (Map[x][y]=="B"):
                print(".",end="")
            else:
                print(' ',end="")
Author:  Panphobia [ Mon Nov 19, 2012 10:38 am ]
Post subject:  RE:BFS algorithm in grids/mazes
Yea but its an error at print(end=) and i had to take it out
Author:  DemonWasp [ Mon Nov 19, 2012 10:50 am ]
Post subject:  Re: RE:BFS algorithm in grids/mazes
mirhagk @ Mon Nov 19, 2012 9:11 am wrote:
...confusing dijisktras with BFS...


Nope. Dijkstra's algorithm is completely different. For one, it uses edge weights, which BFS ignores. The pseudocode I wrote out is almost exactly identical to what's displayed on Wikipedia: http://en.wikipedia.org/wiki/Breadth-first_search
Author:  Panphobia [ Mon Nov 19, 2012 11:19 am ]
Post subject:  RE:BFS algorithm in grids/mazes
I got it to work, now the problem is, it takes like 5 seconds to execute, is there a quicker algorithm because dwite it needs to be less than 2.5 seconds
Author:  mirhagk [ Mon Nov 19, 2012 11:54 am ]
Post subject:  RE:BFS algorithm in grids/mazes
Oh yeah there are lots better algorithms. Both DFS and BFS are brute force solutions. Depending on your problem Djikstras or A* could be very beneficial. Basically if you can come up with an estimate of how close something is to the answer you can use A*.

In general most of the problems require semi-unique solutions, because brute forcing is very easy in some languages (imperative languages especially), and they are meant to require at least some thought.

@DemonWasp Sorry I was confused by your variable names, nodes-to-search and closest. It seemed like you were doing some sort of sorting of the queue, which I now see you aren't.

Your pseudo-code isn't really specific on what node to grab next, which is the only difference between many of these graph searching algorithms (In fact djikstras is just that pseudo code where you grab the node that has the least sum of the edge nodes, and A* is just the same except you add a heuristic to the calcuation etc etc). The pseudo code is really more suited to a generic method for searching.
Author:  Panphobia [ Mon Nov 19, 2012 12:11 pm ]
Post subject:  RE:BFS algorithm in grids/mazes
hmmmm i just searched dijkstra on wikipedia, and the pseudocode is making me very sad lol. Could you code up a quick example using dijkstra or A*, and also is Lee's Algorithm good for this situation?
Author:  mirhagk [ Mon Nov 19, 2012 3:15 pm ]
Post subject:  RE:BFS algorithm in grids/mazes
If the edge sizes are the same then Dijkstra is the exact same as BFS. If A* has a heuristic of 0 (ie you don't have a way to estimate how close you are) then it's the same as Dijkstra.

Because of the above 2 properties neither A* nor Dijkstra helps any with the example I've been using. We can't guess how far away we are from the end because we don't know where the end is. Therefore our A* is Dijkstra. Every movement we make is the same distance (it takes just as long to go left as it does to go right etc). That means that every edge size is the same, so any Dijkstra would just be BFS.
Author:  Panphobia [ Mon Nov 19, 2012 3:53 pm ]
Post subject:  RE:BFS algorithm in grids/mazes
So if dijkstra just be BFS would it execute any faster? If not which algorithm would execute faster, and is lee's algorithm good?
Author:  mirhagk [ Mon Nov 19, 2012 4:59 pm ]
Post subject:  RE:BFS algorithm in grids/mazes
since the algorithms operate equivalently, the simplest one would be the fastest, so BFS would be the fastest.

Lee's algorithm looks interesting, but it just looks like a different (maybe more inefficient) way to do BFS. I don't really see a difference in the algorithm itself, but I don't know (I'm just going off of the wikipedia page)
Author:  Panphobia [ Mon Nov 19, 2012 5:23 pm ]
Post subject:  RE:BFS algorithm in grids/mazes
thing is, the BFS runs in 4-5 seconds when it needs to be < 2.5s, soooo which algorithm would you recommend
Author:  mirhagk [ Mon Nov 19, 2012 5:41 pm ]
Post subject:  RE:BFS algorithm in grids/mazes
what is the exact problem?
Author:  Panphobia [ Mon Nov 19, 2012 6:32 pm ]
Post subject:  Re: BFS algorithm in grids/mazes
So here is my code for a bfs from A to B in a grid,I checked some other code and edited it to fit mine, is it alright, and is it efficient enough?
code:
package bfs;

import java.util.*;
import java.io.*;

public class BFS {

    public static void main(String[] args) {
        int c = 0;
        String text = "A........."
                + "##....##.."
                + ".####...##"
                + ".........."
                + ".......###"
                + ".....#...."
                + "####...###"
                + "B........."
                + "#...#.###."
                + "..........";
        char[][] maze = new char[10][10];
        for (int x = 0; x < 10; x++) {
            for (int y = 0; y < 10; y++) {
                maze[x][y] = text.charAt(c);
                c += 1;
            }
        }
        System.out.println(bfs(maze, 0, 0, '#'));
    }

    public static int bfs(char[][] maze, int x, int y, char wall) {
        Queue<int[]> queue = new LinkedList<int[]>();
        int[] start = {y, x, 0};
        queue.add(start);

        while (queue.peek() != null) {
            int[] array = queue.remove();

            if (array[0] - 1 > -1 && maze[array[0] - 1][array[1]] != wall) {

                if (maze[array[0] - 1][array[1]] == 'B') {
                    return array[2] + 1;
                } else {
                    maze[array[0] - 1][array[1]] = wall;
                    int[] temp = {array[0] - 1, array[1], array[2] + 1};
                    queue.add(temp);
                }
            }

            if (array[1] - 1 > -1 && maze[array[0]][array[1] - 1] != wall) {

                if (maze[array[0]][array[1] - 1] == 'B') {
                    return array[2] + 1;
                } else {
                    maze[array[0]][array[1] - 1] = wall;
                    int[] temp = {array[0], array[1] - 1, array[2] + 1};
                    queue.add(temp);
                }
            }

            if (array[1] + 1 < 10 && maze[array[0]][array[1] + 1] != wall) {

                if (maze[array[0]][array[1] + 1] == 'B') {
                    return array[2] + 1;
                } else {
                    maze[array[0]][array[1] + 1] = wall;
                    int[] temp = {array[0], array[1] + 1, array[2] + 1};
                    queue.add(temp);
                }
            }

            if (array[0] + 1 < 10 && maze[array[0] + 1][array[1]] != wall) {

                if (maze[array[0] + 1][array[1]] == 'B') {
                    return array[2] + 1;
                } else {
                    maze[array[0] + 1][array[1]] = wall;
                    int[] temp = {array[0] + 1, array[1], array[2] + 1};
                    queue.add(temp);
                }
            }
        }
        return 0;
    }
}

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy