OMFG, I can't believe I got this working in just four hours. And it's so fast too.

If you don't know what A* is, well, sucks to be you, huh?

In these images, a red square is an obstacle, a blue square is the path, and a green square is one that was searched.

With a heuristic of 0 -


A max-delta heuristic - max( delta_x, delta_y )


Manhatten distance - delta_x + delta_y

OMG is that JK!?

if(getThingFlags(source) & 0x8){
  do her}
elseif(getThingFlags(source) & 0x4){
  do other babe}
else{
  do a dude}

Um, yay?

Yay is right. My old implementation took upwards of 30 seconds to run on a 20*15 grid! This one is around 5000% faster!

Are you pretending to be a smart programmer again?

Can I play?

Show screens of it actually pathing around the obstacles.

What did you write it in? What language and what program are you using it in?

F***IN WOT

...What does it do?!

You spelled Manhattan wrong

OK, what am I missing?

How fast is it?

The thing I don't like about the description of A* is that it says to go over every grid you've got, and just keep recursing (as a first step of implementation), and when that works, you think it's done. You'd think so, because it works. A* technically should work across a really really large number of nodes at next to nil the cost, excepting that on such a large scale, it might return an unexpected path, because it uses heuristics. In a large environment, it's best to do at least some precomputations for your path finding, if at all possible.

Take your starting point and build lists of 'open spots' and keep branching out from them, and finding a happy point for your heuristics to cut off branches, if you get my meaning. I think the largest path I ever computed was across a 16k by 16k grid, and it would take longer for longer distances. I never got around to implementing the precomputations I mentioned earlier, because I mostly lost interest in the project and some guy I was working with kept pitching the idea of warrior slugs, which eventually ground down my will to work on it.

Yeah, splitting up the field into as-large-as-possible free squares should really help in larger maps. If you have like 100+ units doing a pathfind on a 128x128 grid, well, I think you get it...

Mbegger - manhattan is actually spelled right in the code...

I don't know what this is, but I think it needs more

You spelled MBeggar wrong

No, I spelled it right. You've been spelling it wrong all along.