search

Courseplay / CourseplayPathFinding

A path finding library for Courseplay
Other
4 stars 0 forks source link

Errors in Yonaba's JPS #2

Open horoman opened 10 years ago

horoman commented 10 years ago

The function jump of Yonaba'y JPS contains some errors when allowDiagonal is false. It will then not jump at all.

JakobTischler commented 10 years ago

I noticed that as well, but I wouldn't really see this as a bug. JPS in general only works when diagonal jumps are allowed, so the "bug" for me is not that it's not working, but rather that there's no warning/error message or something like that.

horoman commented 10 years ago

You are right it works. But it works like AStar. There are no jumps. But there should be. I think I see at least three errors, whereof two are bugs in my eyes and one is just a "Unterlassung". Will write it into the lines (not right now but at least this week).

horoman commented 10 years ago

Made the comments into the initial commit. But when I have now read your comment again, I am not sure anymore if I am right with my comments.

JPS in general only works when diagonal jumps are allowed

Have to think about that again.

horoman commented 10 years ago

JPS in general only works when diagonal jumps are allowed

This is a question of definition. In case of diagonal moves are forbidden, I have to perfom a search to the left and right in case of a vertical/horizontal move (with diagonal moves this is not necessary). Then it should work again. We can just try it and see if it works.

horoman commented 10 years ago

Here the proof. Note that it really jumps at the start and the end. farmingsimulator2013game 2013-11-19 15-10-56-72

JakobTischler commented 10 years ago

Yeah. Looking at the picture, I realise two things:

  1. We definitely need allowDiagonal to be true. With a point distance of 5 metres, some tractors will have problems taking those 90° turns.
  2. How come jumps weren't performed in the "middle parts"? The last section before the final jump could/should have been one single jump as well. I'm asking because I think we should aim for as few target points as possible, to get a smoother ride.
horoman commented 10 years ago
  1. I agree
  2. I will try to explain it in a few words. But maybe we can discuss that on Skype later this week. I agree on "the less points the better".

The algorithm does not know how the map looks like, it comes from the start and searches for a path. It also does not know where the area with wheat is narrow to pass it. Therefore whenever it hits this area, this is a possible point to pass the area. Thought this is a jump point and added to the bin. If the path goes through such a point, then it shows up as a point in the path, means that it is not jumped over it.