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 PHP Code:
Usage example: PHP Code:
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.
|
Quote:
|
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).
Quote:
|
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. |
Quote:
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). |
Quote:
Quote:
|
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. |
Quote:
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: Quote:
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? |
Quote:
|
Quote:
|
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 |
Quote:
|
All times are GMT +2. The time now is 04:19 AM. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.