Pathfinding assistance

Question

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
– Vaillancourt ♦, Commented Nov 24, 2015 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
– Vaillancourt ♦, Commented Nov 24, 2015 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
– amitp, Commented Dec 27, 2015 at 19:29

EnemyArea · Accepted Answer · 2015-11-24 16:28:46Z

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

Kyranstar · Accepted Answer · 2015-11-25 01:26:42Z

2

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.

edited Nov 25, 2015 at 1:26

answered Nov 24, 2015 at 20:23

Kyranstar

3242 silver badges13 bronze badges

Add a comment |

Stack Exchange Network

Pathfinding assistance

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Pathfinding assistance

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions