Best way to approach A* Pathfinding?

tetsu0sh0

  • Posts: 49
I've been doing a lot of reading into the A* Pathfinding, And it SEEMS like its something that can be done.

I know there needs to be a start node and an end node.
And then you need to find the neighboring nodes and get the distances, and set the parent to the lowest 'cost'

All that i can figure out eventually.

I do ask what the best way to begin organizing this is.
How do i go about setting up nodes?
How can i give a node address and a value (occupied, visited, closed, not occupied, etc etc) to a node?

« Last Edit: August 27, 2012, 04:01:06 pm by tetsu0sh0 »

coleislazy

  • *
  • Posts: 2607
I just recently wrapped up an implementation of A*.

Basically, I created a node for each tile when the scene is loaded and stored it in a (multidimensional) list. Each node is itself a list containing all of the data (G, H, parent, row, column, tile) and I created custom blocks to get/set these values to make my life easier.

When finding a path, I keep two other lists: open and closed. I add/remove them from the lists as needed, and you can easily check if something is in a list (there's a block for that).

If you don't want to base if off tiles, you could probably make actors to represent your node. You would place them manually in the scene, but when the scene is loaded, you would read them into a list and then kill them to improve performance. Each node would have to know its neighbors, since you couldn't just compare row/column to find the neighbors on-the-fly.

tetsu0sh0

  • Posts: 49
Just finished eh? Care to share some code snippets?  8) :P
So you have 2 lists (x,y respectively) and each item in the list is a list.
Mine is going to be tile based as well.
I'll start trying to get everything organized. Thanks for the quick response!

coleislazy

  • *
  • Posts: 2607
I can't share the code yet, since it was written in 3.0. When 3.0 is released to the public, I may be able to share it.

ipe 369

  • Posts: 1001
How'd you get 3.0?
Is it faster? is there more optimisation?

tetsu0sh0

  • Posts: 49
Awesome! I would really appreciate that :)
Til then I'll hammer away at my own.
Maybe I'll figure it out.

« Last Edit: August 28, 2012, 04:57:34 am by tetsu0sh0 »

tetsu0sh0

  • Posts: 49
Ok so thanks to sunflower i have a 2D array set up with a list in each index.
Now you're using tiles for the pathfinding how exactly?
I'm afraid i cant figure this out by myself :(

coleislazy

  • *
  • Posts: 2607
OK, huge file attached (this has no 3.0 code in it, so its safe!).

This is the entire pathfinding behavior, plus a line-of-sight checker as a bonus! Only two custom blocks are not contained in this behavior: one for getting a tile from x/y coordinates, and one for getting the collision ID for a given tile.

So, first, generateTileMap is called. It creates a new "master" list (tileMap, the list we will refer to in the future to get nodes), then loops by row, then creates a temporary list (tempMap) to store the column, which it then loops through. For each tile column, it creates a new node, setting default parent, G, and H scores, then setting the column and row location (so we can locate its neighbors later), and the tile at that location.

I only get the tile on my "movement mask" layer, which is a hidden layer of tiles where I draw non-moveable terrain. The tile will be null if it is walkable, since I didn't place a tile there.

Now, it adds the node to the temporary list. Once it loops through each column in that row, it adds the temporary list to the master list and moves on to the next row.

The last thing this function does is reuse the tempMap attribute by turning it into a node which I will return if the pathfinding function tries to get a node outside of the scene, to avoid null object errors.

Most of the other custom blocks should be pretty self-explanatory. They basically get or set values in the appropriate spots in a given node, although "get node" also checks if the node is in bounds, as I mentioned above.

The actual pathfinding function is pretty complicated, but was based off this tutorial.

So, when you actual find a path, it returns a list of all the nodes along the path, with the first move being the last item in the list.

Now, for a disclaimer: this is not very optimized. Since the open and closed lists are just unsorted arrays, it gets expensive trying to find the lowest F cost. I also could have eliminated a lot of duplicate code in the "find neighbors" section. The code is still fairly fast, however. You can't run it every update, but you can run it as-needed and still get solid performance.

As I said, there's plenty of room for optimization, so I'd love to hear of any improvements anyone makes!

ShivaFang

  • Posts: 248
Thanks cole.  I was just about to start implementing something like this and this saves me a lot of time.
Justin "ShivaFang" White
Aquamentos Games - The origin of challenging Strategy and Role-Playing Flash gaming!
Visit our Developer Blog and Google+ Page!

tetsu0sh0

  • Posts: 49
Yes that's incredibly generous!
I cannot thank you enough for your help. :D