A* (Star) Pathfinding (AS3) - Example

17 posts

Flag Post

The past few days I have been working very hard to get a ‘clean’ version of A* pathfinding working.

I have looked online and found many useful tutorials (this one being the biggy http://www.policyalmanac.org/games/aStarTutorial.htm) that helped me finally wrap my head around the concept and get to my end result located here http://www.fastswf.com/9tenFt4

However in my searches I could not come across any flash source code that fit what I wanted.
- 1 Class
- Tile array used to build the level is 1D

So I’v figured it out and am just sharing in case anyone was interested.

The code can be found here http://pastebin.com/akZp6HWP and is HEAVILY commented for your convience.

If anyone has worked with A* before and knows of some optimizations or if anyone wants to give some feedback on my method I would like to hear it :D

 
Flag Post

I found out a very big flaw that I neglected to fix. The enemy would always be hugging the wall and moving diagonally even if it was not the best path. If you want to see what I mean make a triangular dip and see how the enemy follows it along the wall all the way down in the first swf.

With just a few lines I fixed this problem.

New swf:http://www.fastswf.com/01W7maI
New paste bin:http://pastebin.com/Xi4n5acZ

(I’v also allowed it to partially go through walls but in the code I commented how you can turn this on or off if you never want the enemy to touch the wall ever)

 
Flag Post

Not sure what’s going on here:

 
Flag Post

Or here

:D

To be precise, starting loc is the bottom right corner square, destination is the top left square. Made 2 paths apparently, and in the pic it is proceeding on the bottom-most one.

 
Flag Post

Haha

Good work with the interface by the way

 
Flag Post

… UnknownGuardian and Dealmaster13 I have no idea how that happened… I tried the same set up and got these paths.
http://gyazo.com/38a778ccf7d95d907f51fc72863adbd6
And
http://gyazo.com/2090c2a24f37f24c11a0e7d39104dc07
(It did not make 2 paths for me. The second path is made if you add a tile and it recalculates. I’ll fix that.)
I have no idea how thats possible

Edit: The visual showing of 2 path is fixed here but thats just visual and had nothing to do with the calculation so i have no idea how I have a different path than you guys.
http://www.fastswf.com/l_VHRg4
http://pastebin.com/Lv3Q7m30

 
Flag Post

It crashes when you click on the same point as where the character is. I suggest just testing if walk node is walkable at the beginning of the algorithm, and if it’s not, return an empty pathway array.
Also, try to make the least amount of function calls you can. I find that calling multiple functions in the algorithm rather than just one function is significantly slower.

Your function names are also extremely long, haha: checkIfThisCurrentSurroundingTileIsOnOpenListAndIfNotAddIt I don’t know if that affects performance but it’s probably not very practical :P

 
Flag Post

Hah I never pressed the same point as where the enemy was… Well yes thats a easy fix no big deal.

Also where are you talking about to many function calls?

Lastly the length of the name of functions or variables don’t affect performance at all any more. I think its very practical as well as it tells me exactly what the function does. I find it useful but it could really be anything.

 
Flag Post

I believe that long function/variable names did cause an impact in AS2, but do not in AS3.

 
Flag Post

That is correct

 
Flag Post
Originally posted by evan999333:

That is correct

Even if it were incorrect, it’s still impractical. What if you had no code completion, would you want to type that each time?

 
Flag Post
Originally posted by RTL_Shadow:
Originally posted by evan999333:

That is correct

Even if it were incorrect, it’s still impractical. What if you had no code completion, would you want to type that each time?

What do you mean “code completion?” I do type my functions out… Like I said I find they help me organize my code.

 
Flag Post

Maybe try really messing up the grid, placing blocks and taking them away and see if you get any weird paths

 
Flag Post

Hrm I just fiddled around with it for a good 10 minutes doing everything I could think of and always getting a proper path. I have no idea how it can sometimes make a incorrect path like what you guys found. This is going to bug me. If anyone has any ideas I’d love to hear em.

 
Flag Post

I couldn’t make an incorrect path either, maybe you’ve accidentally fixed it.

Originally posted by evan999333:

Also where are you talking about to many function calls?

Well, I’m not sure if you care about speed, but if you do, calling multiple functions in the algorithm will slow it down more than just running the algorithm once without calling any functions. I know it’s more organised but I found it to be a lot faster running just the algorithm without calling any other functions.

 
Flag Post

How could I run the algorithm without making the function calls I make? Do you mean I put the code from my functions into the 1 function that finds the path?

 
Flag Post

Yes.
So instead of doFunction();
You have this++;that—;if(this>that)…something+=7;