Java- Maze Breadth First Search Shortest Path -


i seem having problem understanding how retrive shortest path discovered breadth first search algorithm implementing. algorithm works can find exit of maze if can reach it. in post mentioned keeping tack of parent after node marked visited. have tried simple implementation of trying keep track of parent including parent point inside point structure when mark path on grid marks paths has traveresed far, believe may have messed keeping track of parent somehow.

any 1 have clue have gone wrong. maybe missing simple? code included below reference.

the maze 2d integer grid. assume 1 wall , 0 movable path.

the point class contains: point parent int x, y; , nothing more. 

public point bfs(int x, int y){     queue<point> path = new queue<>();      path.enqueue(new point(x,y));//push current on queue      point cur = path.front();//make current point     //test code recursive backcall of path         cur.setparent(null);     //test code recursive backcall of path       point end = new point(mwidth-2, mheight-2);//set goal      while((!path.isempty())){         point old = cur;          cur = path.dequeue();         cur.setparent(old);          if(cur.compareto(end)){             return cur;//return point traverse here calling cur.parent path.         }         else if(maze[cur.getx()][cur.gety()]==1){//enque possible paths              maze[cur.getx()][cur.gety()] = 2;//mark visitied             if(cur.getx()-1>=0)                 if(maze[cur.getx()-1][cur.gety()]==1)                     path.enqueue(new point(cur.getx()-1,cur.gety()));              if(cur.getx()+1<mwidth)                 if(maze[cur.getx()+1][cur.gety()]==1)                     path.enqueue(new point(cur.getx()+1,cur.gety()));              if(cur.gety()-1>=0)                 if(maze[cur.getx()][cur.gety()-1]==1)                     path.enqueue(new point(cur.getx(),cur.gety()-1));              if(cur.gety()+1<mheight)                 if(maze[cur.getx()][cur.gety()+1]==1)                     path.enqueue(new point(cur.getx(),cur.gety()+1));         }      }     return null; }

looks oldis no longer parent after multiple iterations. can set parent when adding point queue instead, example:

point next = new point(cur.getx()-1,cur.gety()); next.setparent(cur); path.enqueue(next);

then when find end, should able path beginning calling getparent() until it's null.


Comments

Post a Comment

Popular posts from this blog

python - How to create a legend for 3D bar in matplotlib? -

Image
given ax = plt.subplot() : ax.bar()[0] can passed plt.legend() . however, ax.bar3d() returns none . how create legend displayed bars? update: passing legend="stuff" ax.bar3d() , calling ax.legend() raises /usr/lib/python2.6/site-packages/matplotlib/axes.py:4368: userwarning: no labeled objects found. use label='...' kwarg on individual plots. warnings.warn("no labeled objects found. " you need use proxy artist legends not supported. this code: from mpl_toolkits.mplot3d import axes3d import matplotlib.pyplot plt import numpy np fig = plt.figure() ax = fig.add_subplot(111, projection='3d') x, y = np.random.rand(2, 100) * 4 hist, xedges, yedges = np.histogram2d(x, y, bins=4) elements = (len(xedges) - 1) * (len(yedges) - 1) xpos, ypos = np.meshgrid(xedges[:-1]+0.25, yedges[:-1]+0.25) xpos = xpos.flatten() ypos = ypos.flatten() zpos = np.zeros(elements) dx = 0.5 * np.ones_like(zpos) dy = dx.copy() dz = hist.flatten() ax...
Read more

java - Multi-Label Document Classification -

i have database in store data based upon following 3 fields: id, text, {labels}. note each text has been assigned more 1 label \ tag \ class. want build model (weka \ rapidminer \ mahout) able recommend \ classify bunch of labels \ tags \ classes given text. i have heard svm , naive bayes classifier, not sure whether support multi-label classification or not. guides me right direction more welcome! the basic multilabel classification method one-vs.-the-rest (ovr), called binary relevance (br). basic idea take off-the-shelf binary classifier, such naive bayes or svm, create k instances of solve k independent classification problems. in python-like pseudocode: for each class k: learner = svm(settings) # example labels = [class_of(x) == k x in samples] learner.learn(samples, labels) then @ prediction time, run each of binary classifiers on sample , collect labels predict positive. (both training , prediction can done in parallel, since problems assumed ...
Read more

php - Dynamic url re-writing using htaccess -

how can rewrite http://mydomain.com/test/master.php?catid=2&subcatid=8 http://mydomain.com/test/master.php/catname/subcat using .htaccess file. once rewritten, how can access these parameters in master.php? note: untested, let me know if doesn't work. rewriterule ^master.php/([a-za-z0-9_-]+)/([a-za-z0-9_-]+)$ /master.php?catid$1&subcatid=$2 [l]
Read more