Astar Pathfinding using default FSM's (Academic experiment)

[Flying Robot]

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 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.

[sebaslive]

Woo! thanks a lot that would be great!!!

[Lane]

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.

[Flying Robot]

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

[Flying Robot]

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

The project package attached for the interested...

[Lane]

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.

[Flying Robot]

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?

[Lane]

There are so many variant ways to approach it though...




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.

[Lane]

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

[Flying Robot]

Here's the next version. It's working for non diagonals. But there's a bug somewhere for the diagonals.

Working on it.

[Flying Robot]

Another version, discard the last one.

This one is also not working properly. But at least has GUIs setup to monitor the score.

[Flying Robot]

Another version, please discard the last one.

In this version, its closer to getting solved. But still one more check to do.

[KozTheBoss]

hot diggity damn, this is some serious work can't wait to see if you pull it off!

best of luck buddy

[Flying Robot]

hot diggity damn, this is some serious work can't wait to see if you pull it off!

best of luck buddy

Thanks! Yeah, this stuff can really mess with your brain 

So, here's the first working solution. Check it out. Just reposition the target, or start point, etc.

Come on everyone, try this out!

[Lane]

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.