A* pathfinding in javascript

Discussion and feedback on Construct 2

Post » Thu Aug 18, 2011 4:01 pm

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.
Scirra Founder
B
359
S
214
G
72
Posts: 22,952
Reputation: 178,610

Post » Thu Aug 18, 2011 4:26 pm

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

This code seems cleaner than the previous one though.
I'll make some test to use this one instead.

Thank you Ashley
New to Construct ? Where to start

Image Image
Image Image

Please attach a capx to any help request or bug report !
Moderator
B
247
S
85
G
40
Posts: 7,000
Reputation: 57,795

Post » Thu Aug 18, 2011 5:21 pm

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 !
B
46
S
17
G
18
Posts: 847
Reputation: 13,802

Post » Thu Aug 18, 2011 7:44 pm

I'd certainly like to see A* platforming, that's for sure - if it could be done with that Mario game, well...
B
94
S
37
G
11
Posts: 404
Reputation: 11,275

Post » Fri Aug 19, 2011 2:24 am

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)





EDIT2 : The PathFinder Behavior topicKyatric2011-09-28 03:43:17
New to Construct ? Where to start

Image Image
Image Image

Please attach a capx to any help request or bug report !
Moderator
B
247
S
85
G
40
Posts: 7,000
Reputation: 57,795

Post » Fri Aug 19, 2011 7:21 am

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.Kyatric2011-09-28 03:42:32
New to Construct ? Where to start

Image Image
Image Image

Please attach a capx to any help request or bug report !
Moderator
B
247
S
85
G
40
Posts: 7,000
Reputation: 57,795

Post » Fri Aug 19, 2011 9:48 am

Great demo, really cool!
Image Image
Scirra Founder
B
125
S
37
G
25
Posts: 3,945
Reputation: 44,922

Post » Fri Aug 19, 2011 1:57 pm

Nice!

[QUOTE=Kyatric]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.[/quote]
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.

[quote]It seems that the minifier has a file size limit, or something.[/quote]
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?
Scirra Founder
B
359
S
214
G
72
Posts: 22,952
Reputation: 178,610

Post » Fri Aug 19, 2011 3:59 pm

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. :/Candescence2011-08-19 16:10:04
B
94
S
37
G
11
Posts: 404
Reputation: 11,275

Post » Fri Aug 19, 2011 5:39 pm

I also think you should leave the movement of the object to the person making the game.
Moderator
B
88
S
32
G
33
Posts: 3,005
Reputation: 27,432

Next

Return to Construct 2 General

Who is online

Users browsing this forum: No registered users and 11 guests