PathFinders not working correctly?

[WhatIsUp]

Hey there,
so I've been struggling to get the ShortestPathFinder as well as the DijkstraPathFinder working in many scenarios and by now I doubt that the implemented pathfinding algorithms (A* or rather based on that) work correctly. But perhaps it's just something I'm doing wrong, so here 2 examples with ShortestPathFinder (DijkstraPathFinder seems to work in even less cases for me):

I create a LineMap, then just create a ShortestPathFinder using that LineMap and call the .findeRoute() method. As the bounds Rectangle doesn't seem to work at all, I also decided to include the boundaries as 4 lines manually. This field's dimension is 100x50.

It works for a LineMap with the following Line[] array:

Code: Select all

Line[] lines = {
      new Line(  -1,  0,    101,  0),
      new Line(100,  -1,    100, 51),
      new Line(101,  50,    -1, 50),
      new Line(  0,  51,     0, -1),
      
      new Line(20, 51, 20, 20),
      new Line(45, -1, 45, 25),   
      new Line(70, 51, 70, 20)};


Start and end points of the route are these:

Code: Select all

WayPoint start = new WayPoint(10, 30);
WayPoint end = new WayPoint(90, 10);

It looks like this:


Meanwhile this second example does NOT work, as on calling the .findeRoute() method the program seems to run in an endless loop.

Code: Select all

Line[] lines = {
      new Line(  -1,  0,    101,  0),
      new Line(100,  -1,    100, 51),
      new Line(101,  50,    -1, 50),
      new Line(  0,  51,     0, -1),
      
      new Line(20, 51, 20, 20),
      new Line(45, -1, 45, 25),   
      new Line(55, 51, 55, 20)}; // this one changed
                // start end end points stay the same


As you see I already made sure the lines are intersecting oneanother so that the algorithm doesn't try to go through e.g. the corners. But still there are a lot of examples where the algorithm seems to end up in an endless loop.

I wanted to use this for a University project, where multiple teams are working on their own roboter and we're supposed to implement at least rudimentary pathfiding. Now all of the teams are struggling to get the PathFinders work.

Any help would be greatly appreciated!

[roger]

I cannot reproduce your problem. Here is my test program

Code: Select all

{
      Line[] lines = {
      new Line(20, 51, 20, 20),
      new Line(45, -1, 45, 25),   
      new Line(55, 51, 55, 20)};
      Rectangle bound = new Rectangle(-1,-1,102,102);
      LineMap map = new LineMap(lines, bound);
      ShortestPathFinder pf = new ShortestPathFinder(map);
      Pose start = new Pose(10,30,0);
      Waypoint end = new Waypoint(90,10);
      pf.setDebug(true);
      Path r = new Path();
      try {r = pf.findRoute(start, end);
      } catch (Exception e){};
      for (Waypoint w : r) System.out.println(w);         
   } 

.
The output from the println() is:
Point2D.Float[10.0, 30.0]
Point2D.Float[20.0, 20.0]
Point2D.Float[45.0, -1.0]
Point2D.Float[90.0, 10.0]

I tried including the bounding rectangle as 4 lines , and got the same output.
You might want to try with the debut flag set. I did, but did not include the output here.
Good luck
Roger

[WhatIsUp]

Thanks for the quick reply!

The output of your third point is [45.0, -1.0], which is a position that should not be allowed.

If I remove the extra 4 lines I included as bounds, those 3 lines of the line map do work for me too though:

Code: Select all

Rectangle bounds = new Rectangle(0, 0, 100, 50);
Line[] lines = {
new Line(20, 51, 20, 20),[color=#000000][/color]
new Line(45, -1, 45, 25),   
new Line(55, 51, 55, 20)}

LineMap map = new LineMap(bounds, lines);
//[...]

//output is this
Point2D.Float[10.0, 30.0]
Point2D.Float[20.0, 20.0]
Point2D.Float[45.0, 25.0]
Point2D.Float[55.0, 20.0]
Point2D.Float[90.0, 10.0]

That said, something that wouldn't work then would be this:

Code: Select all

Line[] lines = {
      new Line(35, 51, 35, 20),
      new Line(45, -1, 45, 25),   
      new Line(55, 51, 55, 20)}
// output
Point2D.Float[10.0, 30.0]
Point2D.Float[45.0, -1.0]
Point2D.Float[90.0, 10.0]

As you see it goes out of bounds this way, and if I add these lines again I end up in an endless loop:

Code: Select all

// bounds
      new Line(  -1,  0,    101,  0),
      new Line(100,  -1,    100, 51),
      new Line(101,  50,    -1, 50),
      new Line(  0,  51,     0, -1),

Overall it seems to get worse and worse the more 'obstacle' lines I add. If I do get something to work and I add one more line it often breaks again already.

[roger]

Thanks - you have found a bug in the ShortestPathFinder.
A corrected version is in the svn repository at:
http://lejos.svn.sourceforge.net/viewvc ... a?view=log

Let me know if you still have problems.

Good luck.
Roger

[WhatIsUp]

Hey, that's great. Thanks a lot.

From what I've tested so far it seems to be working well.

Unfortunately the rectangle one provides as boundaries still doesn't seem to do much so I've gotta add them as lines myself. Also it's a tad annoying that if lines meet one another exactly without intersection the PathFinder considers that point passable. But of course that's also easily delt with by lengthen all lines by 1.

I have one question though, I am working with eclipse and the plugin because it makes it easier for me to compile and upload my scripts to the NXT. Now the latest leJOS build of the Win GUI installer seems to be a bit outdated and e.g. doesn't include Path.java and others.
In short: I don't know how I could turn a projekt into a leJOS project using the latest build available (via the Eclipse leJOS NXJ plugin). It would be heavily appreciated if you could tell me how I may achieve this, especially as I'm not experienced with stuff like that :/

Thanks in Advance!

[roger]

Glad to know the pathfinder is now working.
I would be glad to help with Eclipse if I knew more about it, but I have just switched from Netbeans. Perhaps one of the Eclipse experts can answer.
Roger