1
\$\begingroup\$

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 :)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Vaillancourt Nov 24 '15 at 14:51
  • \$\begingroup\$ (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.) \$\endgroup\$ – Vaillancourt Nov 24 '15 at 14:59
  • \$\begingroup\$ Although my examples use grids, my A* code on my page is written to use any graph, not only a grid. \$\endgroup\$ – amitp Dec 27 '15 at 19:29
-1
\$\begingroup\$

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)
        ClosedSet.Add(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
                OpenSet.Add(neighbor)
            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)
    return total_path
\$\endgroup\$
2
\$\begingroup\$

A* is a graph based algorithm. The only thing that would change between a grid-based algorithm and a graph-based algorithm is that when you're determining neighbors, your algorithm changes from picking neighboring squares to picking nodes that are connected to the current node.

You can basically think of a grid like a graph, which each square being a node, and each square having a connection to its neighbors.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.