Home Search First Look Rules Help TheDaddy.org BlogLogin/Register
By bye hackers
Finding the shortest route between two points - the simplest way! - 1 to 8
Return To Techy Corner

Demian*
Oh Lordy, Plegaleggole
Thu 23rd Oct '08 2:34PM
4678 Posts
Demian's Avatar
Member Since
7th Apr '03
After spending hours trying to wrap my head around mathematics I don't understand, I once again turn to thedaddy.org for help!

From what I've read the most efficient way to do this is with the A* algorithm. However, this is far too complex for little old me to understand. A bit of further searching led me to Dijkstra's algorithm which can, at least, be stated in english. There are also 'breadth first' and 'depth first' algorithms but I'm not sure if these are simply for traversing tree structures. Other possibilites may be the Floyd-Warshall Algorithm or Johnson's Algorithm, or Hill Climbing - but I'm not sure that does exactly what I want.

What I'm looking for is not the most efficient way to do this, but the simplest. The selected route, however, must be the shortest. Does anyone have any experience in such matters?

Bidirectional pathfinding seems useful, but looks to be a way to use another algorithm twice, once from the start and once from the end, and stopping when the two meet - so I'd still need to pick an algorithm to implement bi-directionally.

Edit: Route, not distance. Doh!
  

General*
Windows Bob - the best!
Thu 23rd Oct '08 5:32PM
4213 Posts
General's Avatar
Member Since
7th Apr '03
Path finding algorithms are proper hardcore maths based programming stuff!

Perhaps the first question is why do you need to do it?

If its for some application you are writing you might find there is a useful library someone has already written to do this for you, but if you are doing it for college or out of interlectual curiosity then you probably want to do it yourself.
    

Demian*
Oh Lordy, Plegaleggole
Thu 23rd Oct '08 5:40PM
4678 Posts
Demian's Avatar
Member Since
7th Apr '03
Well it's partly out of interest, and also I need projects to get some practice in java. I've got a few games ideas filed away but they all require pathfinding to some extent or another.

Of course, since I'm still largely stuck in the mindset of an old-school procedural BASIC programmer, I hadn't even considered that there are very likely library functions to do this for me. From what you say it sounds like this may be too advanced for a noob like myself to attempt yet anyway
  

General*
Windows Bob - the best!
Thu 23rd Oct '08 10:19PM
4213 Posts
General's Avatar
Member Since
7th Apr '03
There's no reason not to have a go if you are alright with concepts like complexity and recursion. There are lots of good books on the subject. I learned most of the hardcore stuff for uni from this book: http://www.amazon.co.uk/Foundations-Computer-Science-C-Principles/dp/0716782847/ref=sr_1_2?ie=UTF8&s=books&qid=1224796625&sr=8-2

The funny thing about programming is that when you are at university you spend a lot of time writing things like sorting algorithms, but as soon as you become a commercial programmer you spend most of your time stringing library calls together.

I must say writing games is hugely rewarding and you will learn a huge amount from having a bash not to mention it is cool making something your friends can play. If you want any tips/help let me know.
    

Spanners*
Misses his big brother :(
Fri 24th Oct '08 7:50AM
4597 Posts
Spanners's Avatar
Member Since
7th Apr '03
I remember using A and A* algorithms at university with some degree of success. Breadth first and depth first searches guarantee you finding the right answer since they will cover every possible route but they can be very time consuming as breadth first by nature cannot use any sort of fitness heuristic and depth first can find you plenty of answers but you won't know if you've found the optimum until you've searched the lot.

There is a good tutorial on A* algorithms here and a Java implementation here
    

Demian*
Oh Lordy, Plegaleggole
Fri 24th Oct '08 8:23AM
4678 Posts
Demian's Avatar
Member Since
7th Apr '03
Excellent, lots of helpful links there, cheers guys.
  

Demian*
Oh Lordy, Plegaleggole
Fri 24th Oct '08 9:35PM
4678 Posts
Demian's Avatar
Member Since
7th Apr '03
By jove, I think I've got it!

Start from point A, and draw a path to the nearest intersection, then draw an an arrow pointing the way along it. Then draw another path extending out from your current set of drawn paths, to the nearest as-yet-unvisited intersection to point A, and draw the arrow pointing along it. Rinse and repeat the last sentence until all intersections have been visited once. Now look at the endpoint you were trying to get to, and there will be a single chain of arrows leading backwards along the shortest route back to A! It takes a while to do on paper due to the huge number of path distances you'll have to measure and compare, but it seems to work! Thanks, Mr Dijkstra!
  

Agentgonzo
There's no pee in catheter!
Tue 28th Oct '08 2:38PM
811 Posts
Agentgonzo's Avatar
Member Since
8th Aug '06
A nice animation of Dijkstra's algorithm
  

Bookmark With: Post to DiggDigg   Post to DeliciousDelicious   Post to RedditReddit   Post to FacebookFacebook   Post to StumbleuponStumbleupon
Return To Techy Corner

Time Zone is Greenwich Mean Time You are Visible
Html Tags are On Smileys are On
Anonymous Posting is Not AllowedAmanshu is The Daddy