A* Pathfinding with pre-existing data

So I have been reading up as much as I can on the A* algorithm, but for the life of me I just can’t seem to figure out how to implement it into our current database. Here is the setup I have:

There are 3 Functions:
void SetDestination(IntVector2 target)
This simply sets the destination of the character to ‘target’. It also calls GetRoute on that destination.

List GetRoute(IntVector2 target, int graphSize)
This is the meat of the pathfinding. It returns an ordered list of IntVector2’s that form an optimal path to the provided ‘target’. The size of the graph it uses ‘graphSize’.

void FollowRoute(List route)
This causes the character to follow the ‘route’. It starts with the first item on the list and works its way up. If the route was not fully calculated due to the destination being outside of the graph it waits until it runs out of IntVector2’s and then runs GetRoute again.

The graph actually exists before any of this is run. It is a tile based procedural world, so every element on this graph exists before pathfinding even takes place. Each tile just has a position and weight to it. The only reason I limit the graphSize is so that it only calculates a certain portion of the route at a time. That way it doesn’t have to pathfind to something a potentially infinite amount of space away. I understand this can lead to inaccuracy, but it is well within our acceptable limits and the graph size can be adjusted as needed.

So all of this is working except for, of course, GetRoute. I have read up on it quite a bit but I just can’t seem to wrap my head around it. Could anyone give me some direction with this?

Assuming you are talking about a cartesian grid of tiles, one way to get the actual graph is to make either a 4-connected grid from those source tiles, or else an 8-connected grid. That graph (nodes and connections) is what you feed into the AStar routine.

Now when I say “make the grid,” it isn’t so much that you are making anything in memory, but rather you are making a graph-access API that can query a node and tell you how many nodes it connects to, and that would be driven by the tile’s position in the array, and whether you wanted it to be 4- or 8-way connected (or some other flavor of connectedness).

The approach above maps the tile’s cost to the node element. If you are looking for something that is more route-driven, i.e., the segments have the cost, then you need to add additional “free” nodes that connect at the grid junctures, and then put in “ghost nodes” that represent each side of the original traverse from tile to tile.

It uses four way connectivity. I understand the concept, I am just lost when it comes to actually implementing it.

This is where I read up most of what I know from: Introduction to the A* Algorithm

I’ve implemented it a few times on a few different platforms.

This was my guide, and it really helped me wrap my mind around it, since I didn’t get it at first either.

He also has a more in depth treatment of the subject here, but only after you get the basics above!

Really good place and I go back to it from time to time to refresh brain cells.