Jump to content

Image of the Day

#QuestOfDungeons is an old-fashioned dungeon crawler. #ScreenshotSaturday  #PS4share

https://t.co/1mztLegxeN https://t.co/DpYimg3MZb
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net's newsletters to receive the latest updates and exclusive content.


Sign up now

Jump point search(jps) algorithm is slow than classic AStar?

4: Adsense

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


  • You cannot reply to this topic
6 replies to this topic

#1 pandaa   Members   

178
Like
0Likes
Like

Posted 21 March 2013 - 05:12 AM

I tested the Jump point search algorithm(http://harablog.wordpress.com/2011/09/07/jump-point-search/) and the classic AStar,  and found that JPS is slow than classic AStar. The paper said jps is 2-30 times faster than classic AStar, I don't know why. The biggest comsumption is jump function, because it need visit so many tiles to find jump point, I highlight all the visited tiles in jump function.   

The dashed lines are the horizontal and vertical lines that are checked while checking the diagonal.

7XrQG.png



#2 DpakoH   Members   

1198
Like
0Likes
Like

Posted 21 March 2013 - 09:14 AM

so, you did write some code to test JPS and find out is is slower than ASTAR or you just think it is slower?



#3 Álvaro   Members   

20681
Like
0Likes
Like

Posted 21 March 2013 - 09:29 AM

"Algorithm X is faster than algorithm Y" is a meaningless statement. It should be something like "this implementation of algorithm X on this platform is faster than this implementation of algorithm Y on this platform, for this class of test cases". If you change the implementations, or the platform, or the class of test cases, the statement might become false.

Edited by Álvaro, 21 March 2013 - 09:30 AM.


#4 Ezelia   Members   

130
Like
0Likes
Like

Posted 21 March 2013 - 09:35 AM

Actually, JPS algorithm IS faster than classic A*, this can be proven by mathematics.

 

the implementation of the algorithm is another story :)



#5 Álvaro   Members   

20681
Like
0Likes
Like

Posted 21 March 2013 - 09:39 AM

Actually, JPS algorithm IS faster than classic A*, this can be proven by mathematics.

I am not familiar with the theorem you are referring to, but I doubt very much it says that. You might be able to prove something like "JPS expands fewer nodes than A*", but the cost per node is necessarily higher.

the implementation of the algorithm is another story smile.png

It's also the only thing that matters.

#6 pandaa   Members   

178
Like
0Likes
Like

Posted 22 March 2013 - 12:30 AM

o, you did write some code to test JPS and find out is is slower than ASTAR or you just think it is slower?

Yes, I wrote a demo to test the two algorithms, refer to the open source:

https://github.com/arirahikkala/astar-jps

 

I found a thread here that people discuss jps performance:

http://www.bay12forums.com/smf/index.php?topic=92732.0



#7 wodinoneeye   Members   

1682
Like
0Likes
Like

Posted 14 April 2013 - 01:38 AM

I long ago looked at some similar way to quickly traverse open space before applying a terminal (much shorter  length) search.

 

This kind of method generally require sparse terrain blockage features to work (be efficient) most of the time.

 

If your terrain is more maze like and the start+target positions are unfortunate then it will perform worse than A*  (will it work at all for a worst case possible path ???)

 

The author uses the word 'can' , but doesnt much mention cases where it 'cant'  which for a general search on ANY terrain pattern  can be very misleading.

 

It also apperas to be solver for block/not-blocked without more varying weights


--------------------------------------------Ratings are Opinion, not Fact




Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.