A* Movement System
 

With this code, you can tell an NPC to move from point A to point B, and it'll calculate the best path using the Manhattan method. If you want to learn how this system works, I recommend reading this.

The only parts you might need to customize can be found in the onCreated() function. The system can be used both serverside and clientside.


Class: aStar

Usage example:

Here's a video showing an example of usage. Note that in a lot of cases, it's better to split up the movement sequence in several shorter routes than one big, especially when your target position is close to the start from a birds eye point of view but still so far away.

The movement looks a bit choppy in the video, but it's not in-game.

Wow Awesome!

Looks good, the movement just looks unnatural particularly when it's going through the diagonal sections but that's probably because of the level also being out of the ordinary.

Yeah, it's really not a level where you normally would use it, I just wanted to test the limitations of it. Due to the nature of the level, the loop limit is easily reached if I were to only use 1 path to get from the start to the end, but it shouldn't be a problem in normal levels.

Nice work, but it looks like your final path has some unnecessary nodes in it (such as at :25 when the npc goes in the wrong direction for a few tiles and then turns around).

You can avoid the loop limit by counting the number of loop iterations and adding sleep(.05) whenever you reach this.maxlooplimit. That way you'll still find a path, it just might take a little longer.

Sales, you made something similar once, didn't you?

Edit: http://forums.graalonline.com/forums...hp?t=134256443
The diagonals seem smoother in Sales' thread, but I'm not sure if it'd be of much use in your project for study, Ziro.

I was using an npc with one direction in my movement.

I did find a few solutions to fix the the choppiness, though. The first was to just make the NPC always face the final node, so it will look like it's strafing. The second was to strip out unimportant nodes and just use the nodes where the path changes direction (in my thread, I gave the "important" nodes a different color so you can see what I'm talking about).

The problem with those nodes is that they're technically closer to the target, thus have a lower F score. I'm not quite sure what I can do to change that.



Good point, I'll try it out.

Hmm, I haven't done much pathfinding but... what if you ran a scan after you created a successful path and did a raycast between each node and te player. Whenever a node can no longer reach the player because of an obstruction, add the node before it to a new queue. Then, run this same check between the last position in the new queue. Use this much smaller array to create a smoother movement?

Give me a bit and I will draw out a diagram.

There's a problem with your algorithm. With the way A* works, it will try those nodes first because of their low score, but will eventually correct itself once it realizes that they are not actually part of the "best" path.

It's been a while since I've done any pathfinding work, but I'm guessing that your problem has to do with fixing parent nodes as you find better paths. I actually used the same guide as you when creating my version of A*...this line sums up what I'm talking about pretty nicely:
It could be something else, but I had the same problem with not correcting parent nodes.

edit: It helps to see the path that it's creating visually. Try drawing the nodes of the final path, so you can see where it's adding nodes that it shouldn't be adding.

Now, this is just a drawing, it isn't representing a node set-up a real pathfinding has created. Just portrays the kind of path pathfinding will create: hugging the walls. Very unnatural.

http://i.imgur.com/is5kT.png

Red Circle = start
Blue Circle = end
Cyan circles = nodes
Red lines = ray cast that encounters a wall between last successful path and node check.
Yellow line = when above check encounters wall, designate previous node as optimal path and the last path chosen.

Like I said, I've dabbled very little in pathfinding, but couldn't this work?

A good A* implementation should give you something closer to the yellow lines not the dots anyways.

My idea would cut back on the unnatural movements though, wouldn't it? I'm talking about the 45 degree movement, specifically, which even your A* ends up having.

Unfortunately without preset nodes, natural movement becomes incredibly taxing. For paths, I put preset nodes into the paths. These nodes contain information about which direction goes where.

So, a NPC was off path (chasing a rabbit) and needs to get back on. You work possible route(s) to the node, go back through path, always choosing lowest cost and then travel that cost effective path (this should eliminate that weird part where his NPC walked backwards randomly).

As soon as you start requiring things like 'must be 2 tiles from nearest walls' and such it just becomes far too taxing on the server.

Once I was going to set up communication so i could offload these calculations to a dev server :D

I was thinking Bezier Curves combined with my above method O.o though I imagine that would be just as taxing.

It's not so taxing if done right. For known paths between things, you put preset nodes. That way, you only have to A* to get to one of the nodes. After that, you can put preset paths in place for NPCs to follow to their destinations.

Example: you have a road between two towns. A NPC gets distracted by a bunny and gets lead of the road a bit. The NPC only needs to A* (if necessary) to get onto the nearest node on the road. Once on he is set.

Can use a quick tool online to put all these node paths in easily enough. Depending on the realism you want, may need the occasional diversion around a player /object but other than that it's nice enough.

Interesting! Pardon me, but I have a noob question...

how difficult would it be to have an 'if interrupted on the path' condition? The guy plots out the path, the guy tries to move along the path, and if for some reason he's blocked along the way, he takes a certain action?

Shouldn't be a problem.

Don't disregard my post actually! Lol. For some reason, when I try to make an NPC move, it always returns error: blocking, no matter the x/y input or it's origin x/y.. Anyone know the cause of this? Could it be because I'm trying to place it on a gmap? Also, it doesn't only work with pics1 type tiles, does it.. ?

Come to the conclusion that it's neither of the things I mentioned. Anything else it could be.. ?

Posting my class code for reference:

Also, note that I am placing these NPC's using a class spawner, and not actually adding them to the level via level editor. Could this be what's wrong?

You need to configure either newtilesetlevels or newtilesets in serveroptions to let the server know which levels are using type 1 tiles.

Not sure how to configure either of the things you mentioned Ziro. :P

Example:

If your entire server is type 1, you can just set newtilesets=true though.

Oh okayy.. well played good sir! But, apparently this is not the problem as the NPC is still returning "Error: Blocking!"

Try it in a type 0 level and see if it works.

You should use A* with waypoints and a navigation mesh instead of tiles, it's less intensive and looks better, although it creates some manual labor for the person creating the level. Maybe you could fall back to tiles if there are no waypoints in the area.

awesome xx