A* Pathfinding Behavior

Meestar

  • Posts: 652
Hey there everyone!  I am new here to the Stencyl community.  I don't have too much Stencyl experience but I want to help where I can.

I was wondering how many of you would be interested in an A* Pathfinding behavior made without any AS3 code?  I currently have just that.  It works fine, but crashes a lot presently.

Just wondering if enough of you would be interested in it to warrant my going back and fixing it.
PM me if you require help.  I'm always glad to help out!

MyChairHasALooIn

  • Posts: 310
I made an a* with behaviours, but found the real trick was making it into an exportable behaviour which would be useful, something I never anywhere near finished:( so good luck dude.

My version has an interactive demo here http://www.stencyl.com/game/play/15597, all you can do is place 'towers' to change the route the monsters take (click in game window).

Meestar

  • Posts: 652
Well, it all depends on the purpose that the behavior would be used for.  I could always make multiple versions for different game types.  Already, I have it set up so that you can enter the names of the collision groups that you want the game to include in the pathfinding, which just as easily can be converted to detecting just actors, which is perfect if someone is working on a Tower Defense game type.  Just modify it to include constant movement and to switch the actor's animation that the behavior is attached to.  With a little tweaking, it can be used for a Final Fantasy Tactics-esque game or some similar Strategy game.

Simply put, if someone wants to use it, then I'm glad I could help them out.  I definitely really don't plan on making a purely "noob" friendly behavior, just something more for a more intermediate user.  I also plan on releasing a bunch of other behaviors for Strategy games.
PM me if you require help.  I'm always glad to help out!

Red Frostraven

  • Posts: 23
I'm currently working on making a universal 2d pathfinding behavior for all my monsters regardless of "intelligence"...

I would LOVE to see some more work (from other people) on the matter, because my coding tends to be more "brute force", sometimes bordering to voodoo-coding, than finesse.

I am always more surprised when my code actually works then when it fails, and this project is kind of overwhelming -- especially when I have an obsessive-compulsive NEED to KNOW *what*, exactly, makes my code work, and I die a little inside whenever I don't understand what others have coded.

jihem

  • *
  • Posts: 161
while (!success=retry());

Red Frostraven

  • Posts: 23
Alright... I now have my head wrapped around the basic idea of how that stuff works:
By probing and a clever use of arrays.

*Sigh* top down coding  is damn annoying; I should have learned to build this stuff from the ground and up.

Current plan:
Make coarse, fine and close pathfinding.
-Coarse uses 4x grid-size to determine pathfinding routes (and is without limitations)
-Fine uses 1x grid size but is limited to 5 tiles radius (120 blocks)
-Close only searches within a 7 tile diameter (48 blocks)

Going to sleep on the matter:
Once this behavior is boxed, the rest of the game is easy as pie (except all the other future coding and animation challenges I never saw coming).

==============

Update:

The lack of actual 2-dimensional arrays (without using imported code) makes this absurdly complex.

...

Thoughts:
I can simplify this behavior once I manage to wrap my head around EVERYTHING that is going on.
The need to use one-dimensional arrays is... suboptimal and it has taken me hours to try to create a proper array for the task.

ALL we need is a two-dimensional array for this to work.

Project data:
-We need a 2dimensional array to represent coordinates of the maps
-We need to create that 2d array on the creation of each map to avoid lag
-We need an array/list to represent the path
-We need a function to check the path and set the variables in the 2-dimensional array
-We need a function to evaluate the path from the end to the start
-We need at LEAST 5 different terrain codes / or two different pathfinder scripts: Open, tough, hard, tall and blocked -- / or replace Tall with different behaviors for flying and walking

...

Gridchecking "AI":
-It must always try to build a path from at least one open position.

And that is where I have trouble right now.
Data-collection is my cup of tea -- but... data evaluation...
That is where I fail miserably right now. How can I make the script go back and find the next best position on the grid?

Project 10% completed.

=============

Update:

Pathfinding/gridchecking "AI":
-It must always continue with the path with the lowest cost; When it hits rough terrain, it must try to build from other paths until the current cost equals the cost for the rough terrain.

I think I'm starting to understand how to make the script find the best position to continue evaluation;
-I need each position to have a cost value, and that cost value is the essence of intelligent pathfinding.
-For an intelligent pathfinding, going away from the target must cost more than going towards the target.

(This is exactly like kids walking to school:
Where there is 10 seconds to save on the road to the school by crossing through the grass field -- there's a muddy path in the grass field right there.)

Problems in the horizion:
-What is the resource cost of this on the system?
-Will I manage to do this without going insane?
-How will we make the actors evaluate wheter or not to continue their path?
-Espresso really does not help for concentration. At all.

Wisdom learned:
-ALWAYS break down stuff and understand the function of each component: Building an engine in one go is impossible.
-Espresso really does not help for concentration. At all.

Making the grid at the creation of the area:
-For coarse pathfinding to work, we need to return "blocked" when even one area within the path is blocked. We need to be careful to always leave large ways open.
-Eventually, the coarse pathfinding will include sub-paths for partially blocked areas -- with separate values (that allows medium-sized creatures and objects to pass by having the coarse pathfinding return the path through that block as 1x1 grid coordinates) -- but that is for the future versions.

« Last Edit: March 24, 2013, 03:51:24 am by Red Frostraven »

Meestar

  • Posts: 652
Tell you what, I'll upload what I have now.  It doesn't always work 100%, but maybe it will help you out.
PM me if you require help.  I'm always glad to help out!

Meestar

  • Posts: 652
Search for "PAthfinder" under games.
PM me if you require help.  I'm always glad to help out!