A* pathfinding in javascript

Came across this link today:

http://www.matthewtrost.org/projects/astar/

Might be an interesting one for any plugin devs looking for a project. I think it would make a good behavior - you could use it to get any object to navigate through a maze and such.

Interesting.

I've been working on such a behavior for the past few weeks (learning JS at the same time) and had found an implementation of the algorithm (with multiple heuristic formulas too, a few more than in this one) but this example uses far less code.

My behavior already "scans" the layout and translate it to a map where obstacles are marked.

At the moment, I'm having trouble with making the instance travelling the found path <img src="smileys/smiley4.gif" border="0" align="middle" />

This code seems cleaner than the previous one though.

I'll make some test to use this one instead.

Thank you Ashley <img src="smileys/smiley2.gif" border="0" align="middle" />

One thing that could worth adding to this A* implementation is "teleporters". Special walkable tiles from which a path to other non-adjacent tiles can be found. Especially useful in creating wraps and warps alike !

I'd certainly like to see A* platforming, that's for sure - if it could be done with that Mario game, well...

The problem with such algorithm is that there are lots of ways to apply it.

Making the most common behavior possible, answering all needs will be quite hard. (and tbh is not really my concern. I needed a pathfinder for one of my project. When my own needs are fulfilled, I'll release the behavior. If you have specifics you want to add, you'll then have to add it to the code yourself). (We'll see)

For now, I'll let you with this little demo of the behavior WIP.

The start is the sprite in the top-left corner.

The destination is the bottom right corner.

Click on any case to make it an obstacle. (Avoid making Start and Destination an obstacle though)

When you're done conceiving your maze, click the top-left sprite.

it should show a path of arrows, and give you a message once the sprite has reached the destination square.

As said, really work in progress.

The heuristic formula for this example is Euclidean.

I have more work on this before making it publicly releasable.

This demo is based on the code Ash pointed out.

Edit:

Known bug:

+ The sprite doesn't move up. Instead it stays in position/stucked.

I'll have a look into why later (can be after the r51 release though, as I'm intending to participate ludum dare this week end.

Let's make a bit of promo for C2, join me there (jam rules allows for teams and a 72 hours deadline)

<img src="smileys/smiley20.gif" border="0" align="middle">

EDIT2 : The PathFinder Behavior topic

I just edited the demo with my last version of the behavior.

So the "up" bug has been corrected. The sprite seems to be "floating" a bit, compared to the straight "glued to grid" style it had previously.

Right clicking an obstacle will delete it.

You can make pretty elaborate mazes.

Strange thing happens on export though. I wasn't able to minify it, directly from C2, when I tried, the output file was 85 octets, and only contained the header "// Generated by Construct 2, the HTML5 game and app creator :: http://www.scirra.com".

It seems that the minifier has a file size limit, or something.

Still not done with the behavior, but it is taking form steadily.

EDIT: Those posts are old and were Work In Progress only.

The actual topic for the PathFinder Behavior is one click away.

Great demo, really cool!

Nice!

So the "up" bug has been corrected. The sprite seems to be "floating" a bit, compared to the straight "glued to grid" style it had previously.

I wouldn't make the behavior move the object. No matter what you do, for the majority of games it's probably not quite what is needed. For example tile games just want to step a whole cell at a time, and an RTS might use a steering vehicle style. IMO the behavior should just return the list of waypoints by expressions and then the user can make the movement via events... that seems to hit the right balance between "taking care of it for the user" and "not telling the user what they want", which is the balance all of C2 has to strike just right.

t seems that the minifier has a file size limit, or something.

There's definitely no file size limit. I guess there is a mistake in your script the minifier doesn't like. Did you read the section on Google Closure Compiler in the SDK docs?

By the way, here's that Mario A* thing I was talking about.

Yeah, unless you want to do specific behavior functions for every type of movement, it may be best to leave the movement to the user. Platforming A* might be a bit trickier, though, since I imagine you gotta work out how to account for gravity and jumping in how to get from Point A to Point B, not to mention stuff like platforms.

Edit: Honestly, that's something that might require behavior functions to make life easier for the user. Speaking of which, in C2 right now, you can't make the platforming behaviour move left/right and jump via events, which makes platformer behavior enemies impossible right now. :/

I also think you should leave the movement of the object to the person making the game.

Great demo, really cool!

Thank you <img src="smileys/smiley16.gif" border="0" align="middle" />

I also think you should leave the movement of the object to the person making the game.  

Nice!

I wouldn't make the behavior move the object. No matter what you do, for the majority of games it's probably not quite what is needed. For example tile games just want to step a whole cell at a time, and an RTS might use a steering vehicle style. IMO the behavior should just return the list of waypoints by expressions and then the user can make the movement via events... that seems to hit the right balance between "taking care of it for the user" and "not telling the user what they want", which is the balance all of C2 has to strike just right.

Well I strongly inspired myself of the rts behavior from CC (which I've had a lot of fun with, but also saw some of the limits).

I was aiming at proposing the maximum options/settings. (as proposing two type of walk: straight in the cell, as previously, and also the current floating one which I see potential in ^^)

Well, I'll just put more options, as well as the "don't move parent" and "return pathlist".

If I had knew this a few days ago, I wouldn't have hurt myself getting it to work <img src="smileys/smiley17.gif" border="0" align="middle" />

But in the same time this has been very taughtful.

There's definitely no file size limit. I guess there is a mistake in your script the minifier doesn't like. Did you read the section on Google Closure Compiler in the SDK docs?

Yep I took a look at it, I'm not sure what have "broke" it though. My runtime went above 1000 lines and the minifier just stopped working, with seemingly no output message (that's frustrating)

Anyway, I'll make sure to clean all the code before releasing the behavior and make it "closure" compliant.

I've read from all the websites and sources you pointed me to and learnt a lot quickly and quite easily.

the demo with my last version of the behavior.

Hi Kyatric,

The page you link to doesn't seem to work for me. It just shows a thin black frame with nothing in it.

Can you update the link?

Thanks!

Loathian

The correct topic is there:

(Behavior">PathFinder.

I'll take down those old links, they seem to provide some confusion.