# Pathfinding assistance

Here's a quick image:

I've generated a navmesh for my game that shows how an AI can get to each of its possible neighboring tiles in a map. (I followed some gamasutra article as reference, I'll paste a link if I can find it again). You can see that it calculates all possible jump, fall, and walking connections between points.

Now that I have this, I've been researching how to actually use it. I understand that A* is generally the algorithm that people use but I haven't been able to find a resource for adapting it to a non-grid based dataset. Any articles that you know of or pseudocode would be awesome :)

• A* star is for a graph, not for a grid. The simplest heuristic is on a distance base. Did you look at the pseudo code on Wikipedia? I've implemented like this lately and it's working fine. – Vaillancourt Nov 24 '15 at 14:51
• (Just to add: a grid is a subset of a graph so you can use A* for grids, but you're not limited to use grids. And a nav-mesh is a graph, no question about it.) – Vaillancourt Nov 24 '15 at 14:59
• Although my examples use grids, my A* code on my page is written to use any graph, not only a grid. – amitp Dec 27 '15 at 19:29

Have you look at wikipedia? there is this sample code: https://en.wikipedia.org/wiki/A*_search_algorithm

function A*(start,goal)
ClosedSet := {}       // The set of nodes already evaluated.
OpenSet := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
Came_From := the empty map    // The map of navigated nodes.

g_score := map with default value of Infinity
g_score[start] := 0    // Cost from start along best known path.
// Estimated total cost from start to goal through y.
f_score := map with default value of Infinity
f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

while OpenSet is not empty
current := the node in OpenSet having the lowest f_score[] value
if current = goal
return reconstruct_path(Came_From, goal)

OpenSet.Remove(current)
for each neighbor of current
if neighbor in ClosedSet
continue        // Ignore the neighbor which is already evaluated.
tentative_g_score := g_score[current] + dist_between(current,neighbor) // length of this path.
if neighbor not in OpenSet  // Discover a new node
else if tentative_g_score >= g_score[neighbor]
continue        // This is not a better path.

// This path is the best until now. Record it!
Came_From[neighbor] := current
g_score[neighbor] := tentative_g_score
f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

return failure

function reconstruct_path(Came_From,current)
total_path := [current]
while current in Came_From.Keys:
current := Came_From[current]
total_path.append(current)