Playmaker Forum
PlayMaker News => Work In Progress... => Topic started by: Flying Robot on May 22, 2013, 07:44:54 AM
-
Well, as you all now Unity pulled out one of my kit 'Corel Reef PlayMaker Kit' from the asset store because it used Astar pathfinding FREE of arongranberg.com. They advised me to develop my own pathfinding before hitting the store.
We already have a wonderful Astar suite by Kiriri (http://hutonggames.com/playmakerforum/index.php?topic=2540.0) encompassing everything you need for A* pathfinding.
Then why this thread?
Though I was engraged at the Asset Store guys, but on second thought I wondered if this is possible in any way. At least in a small scale for academic purpose only.
So, I'm starting this experiment to implement Astar with default/factory made PlayMaker FSMs only. No custom actions. Let's see if it's possible or not.
I'm posting this thread for another reason. If anybody wants, can get involved in making this. I'll be posting the assets as attachments of this thread.
-
Woo! thanks a lot that would be great!!!
-
I think it will be pretty complex to integrate into other projects with any flexibility if we're using no custom actions or scripting. We'll see.. Got a few ideas floating through my head for it but I moved away from projects requiring heavy pathfinding simply because its a hassle until I can get a better grasp on it.
Let me know if I can help, I'll pitch in where I can.
-
Yes,
I'm guessing it'll be real hard to do this. Let's give it a try and see.
Some reference links from google
http://en.wikipedia.org/wiki/A*_search_algorithm
http://www.policyalmanac.org/games/aStarTutorial.htm
-
First version : Setting up the arrays and Calculating F score of Top middle cell.
Path Scoring :
The key to determining which squares to use when figuring out the path is the following equation:
F = G + H
where
G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there.
H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don’t know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.). You are given one way to calculate H in this tutorial, but there are many others that you can find in other articles on the web.
Referring to Astar Manhattan Algorithm
http://www.policyalmanac.org/games/aStarTutorial.htm (http://www.policyalmanac.org/games/aStarTutorial.htm)
The project package attached for the interested...
-
This looks like a nice start, you've got the cell's dropping and defining as walkable/unwalkable nice and clean
This is all new to me, definitely looking into it more. I'm surprised at the density of the system already, didn't realize it would be this heavy.
I don't really understand how building the path works, do you get all the nearest squares, then the lowest value, then build toward the target and continue picking the lowest value? That would be weird if the start was in a U shape and the end was right outside the U shape, the most expensive route would be the actual cheapest and it would have to calc all of the possible routes until it got to the successful one. The manhattan method I guess is what throws me off.
-
Let us get a little further with the logic and see. I'm worried about the algorithm too.
Especially when more than one adjacent cell scores the same lowest. Which path to take?
-
There are so many variant ways to approach it though...
(http://upload.wikimedia.org/wikipedia/commons/8/85/Weighted_A_star_with_eps_5.gif)
(http://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif)
It seems like its in phases, if we project toward the target and begin scanning in some direction for a way around obstacles until we eventually get a solution we have to build the optimal path separate from the pattern we used to scan for it.
I found these:
http://www.youtube.com/watch?NR=1&feature=endscreen&v=uIVu7ViLaZo
They mention Open List and Closed list. It seems like we need to calculate nodal pattern based on Manahttan so it can choose the lowest available H score, store the scores in each node while its running the path scan, but when it gets to the destination node it builds needs to build a path based on the tile scores?
They get into parenting and some stuff, but I didn't have time to really dig into it, looks like you can use it to build a line of cheapest node costs and then build the actual path backward from the destination through the cheapest connecting parents after one of the nodes makes contact with the "destination" node.
-
I'll see if I can mock up something tonight.. Need to figure out how to get into ArrayMaker for the lists though, never used it until now.
If you have Skype, you can buzz me on there: zer0bounds
-
Here's the next version. It's working for non diagonals. But there's a bug somewhere for the diagonals.
Working on it.
-
Another version, discard the last one.
This one is also not working properly. But at least has GUIs setup to monitor the score.
-
Another version, please discard the last one.
In this version, its closer to getting solved. But still one more check to do.
-
hot diggity damn, this is some serious work :o can't wait to see if you pull it off!
best of luck buddy :)
-
hot diggity damn, this is some serious work :o can't wait to see if you pull it off!
best of luck buddy :)
Thanks! Yeah, this stuff can really mess with your brain :D
So, here's the first working solution. Check it out. Just reposition the target, or start point, etc.
Come on everyone, try this out!
-
Man, I'm genuinely impressed. I applaud your accomplishment here!!
I did some harder routes and stuff for it. It blew right through them with no issue. I suppose next you need to encapsulate it into kit form so you can define the grid area and build the route with an input and destination of choice.
Are the final waypoints dumped into an array that you could use to have something follow them? Planning on working in any local avoidance or rebuilding partially?
Man.. It's so great to see this all in FSM form. I wonder how the load is on larger grids and with multiple paths being built during gameplay. Wish I had more time to look into it, just been swamped lately.
-
Hey thanks, I got great help from the links you posted.
Yes, seeing this working gives a level of satisfaction. The algorithm seems to be tricky, until you solve it.
I began this as an academic experiment to understand Astar, also see if it's possible with PlayMaker and to what extent. Also, I really want a dig at the algorithm and build a system which I understand inside out and can exploit to the fullest in different games. I really not fond of black boxed systems.
Now that this is showing some promises, I'll continue work on this and see if it can be made into a flexible, reusable system, which is also open and easily understandable. I'm still not sure how fast this is. On a larger grid, and especially if the target is dynamic, and it has to recalculate the heuristic continuously. But as I understand the system now, I can see there's multiple ways of doing this. And it be custom made for the type of gameplay. TBS can have different implementations than point and click. Also, the heuristic itself can be replaced completely, the heuristic is separated from the system, so, you are free to try different heuristics for different purpose.
PS: The waypoints are already dumped in the Waypoints array attached to the Gamecontroller. The array is reversed and trimmed and ready to use for movement. :P
-
My client crashes every time i click run =(
-
My client crashes every time i click run =(
Did you install ArrayMaker?
-
This is working out great! It also introduced me to the array system which is double bonus. The more work on playmaker the better, thanks for this!