How It Works: A-Star (Pathfinding) Part 3/3

[nakedburrito]

I must say, that was quite helpful in helping to make my understanding lucid; doubly so given that visualizations are a lot like taste - sometimes you need just the right one to make you full. Thank you kindly for taking the time to make this. It's a testament to your clarity that you still get views years after this video's creation :)

[mdsalmaniqbal]

megaupload is inaccessible... it would be nice if you could share the source code for reference...

[wvanderp1]

can you reupload the code? megaupload is down!!!

[BrandonBlanchard]

This was astoundingly helpful thank you

[Chirmaya]

Thanks a lot for the set of three videos. This helped me get the A* concept into my head more firmly.

[iglor]

great stuff

[KoffeeAddikt]

Dude, do you have a video for D-Star?

[Julz333666]

woah, nice optimisation man! so quick.

[jeanfrg93]

Assign diaginal paths with a 7 score and str8 paths with a 5... it will solve the bugs

[NeilRoy65]

Very nicely done, thanks, you explained that very clearly. Clear enough that am confident I can recreate it without seeing any source. :) (at least I'll try)

I done my own simple pathfinding a while ago which basically starts at the end, marks that with a ZERO, then marks all surrounding walkable locations with 1, marks all movable locations surrounding the 1s with a 2 and so on until you reach the start. You then can move from start to finish moving to the path with the lowest number.

[yonifra2]

nice vid dude, thanks a lot for this series :)

[Dooobs]

@PaganSteve The links to the source are in the info section to the video. Click the down arrow thingy to view all the video info.

[Marein86]

Why do you say it's un-human-like to 'zag across'? If a human would want to move to their friend behind a wall, they would take the shortest way from where they were around the wall, not first bump into the wall and only then start moving around it (as the program does at 3:48), right?

[Dooobs]

@Marein86 Not really, in my opinion humans are slack and if you couldnt walk diagonally you would take straight lines...

[MrShubh16]

@Dooobs its a rat/hamster path...

[VaikoIndelev]

This is just what I've been looking for, thank you so much!

I'd love to use this in my programming assignment, is that ok with you?

Can I credit you as "Doobs@Youtube" or you'd rather be credited by name?

[jamesbarbosa500]

hi, can u help. I need to convert A* algorithm to IDA* is it possible?

[ppardee]

Thanks for this. It helps a ton!

[MrPAULMUNTEAN]

hi there

[MrPAULMUNTEAN]

i need source code,links,book etc

[HackingHarvard]

Very nice tutorials.

Shame it's written in C# though =P

five stars

[nastey86]

Dooobs, i need to make a program that uses the A* algorithm. For start i need to find the shortest path from 4 nodes. For example, from node A to node D (nodes between B and c), defined with 2D system (all nodes have coordinates between them). How can i write that? Will you help me with the code in C#?

Thanks

[igalEpshtein]

looks interesting

where i can find this source code ?

[Dooobs]

Read the sidebar....

[igalEpshtein]

didnt find any...

[BinaryReader]

Hi, quite enjoyed your video's on A Star, you should explore some other search algorithms too :) and where to use them.

Good work.

[Cambesa]

im not english so don't blame me for this question. what is c-sharp actualy? is that c# or c++?

[Dooobs]

C-Sharp is C# and C++ is C Plus Plus.

[firesofmay]

Excellent Bro..

[Dooobs]

Cheers mate.

For anyone wanting the code that I haven't got back to, sorry about that I've been really busy.

I'll host it somewhere...

[SoftGeekProductions]

Doobs, can you send me the code, with some comments or something? :-).

[Dooobs]

Yep, send me a PM with your MSN or email or something and Ill send you it.

MSN is preferable, becuase then you can talk and ask questions directly.

[buk09]

yo dooobsy bro,

I happen to be likeing you pathfindings.

i would like to be aquiring you pathfingings ablities.... i did send you a message b4 but lyke u didn't respond. i'm nao lyke resorting to video comments and typing lyke a dick. could you plz get into contacts w/ me so i can has a look at your pathfindings cos mine likes to spit in my face. i have got like 90% of the way but it dun work. anyways cheers btw where you from cos me and a mate are arguing your either from aus or nz cheers

[Dooobs]

Im australian, and I never got any of your messages. So, what exactly are you having problems with?

[buk09]

well i was having a lgic problem but tis k now cos i fixed it.... though i would like to know... what are some good Hx formular's? cos atm i know the:

Hx = sqrt( (endx-currentx)^2 + (endy - currenty)^2)

Hx = (endx-currentx) +(endy-currenty)

then i got bored and made my own one which kinda works well. tis a fusion of the last two

Hx = sqrt(absolute((endx-currentx) +(endy-currenty))

so yeah i wanna know what others are and what you believe is best

your vids helped me out alot!

cheers

[Dooobs]

Hey mate, sorry about the late ass reply, I think the H calculations need the 'Tie Breaker' that I spoke of. Theres a good website in the description of these videos on Huristics and I suggest you read that.

Here is a snippet of code for some of my algorithms.

(See next comment)

[Dooobs]

So, you need to fiddle with the Tiebreaker value, which can be done by:

H *= (1.0 + p)

The factor p should be chosen so that p < (minimum cost of taking one step) / (expected maximum path length)

I just used a fixed constant of 0.001 which seems to work fine for me, you may want to fiddle.

Four Direction:

H = Math.Abs(StartX - EndX) + Math.Abs(StartY - EndY) * m_tieBreaker;

Eight Direction:

H = Math.Sqrt(Math.Pow(StartX - EndX, 2) + Math.Pow(StartY - EndY, 2)) * m_tieBreaker;