C++

Forum

 
Grid-based Motion Planning

Erain (19)
I'm looking for a simple motion planning algorithm (e.g. A*). I've tried all sorts of Google searches, but to no avail so far.

My preferred way for it to work would be for me to set up a 2 dimentional array filled with 1s and 0s, representing which squares are passable. My objects will move on the grid in full square steps, with diagonals allowed (like a 2D Dwarf Fortress). Ideally I could write a function which will take in the map array, starting coords and ending coords, and return a custom structure (or maybe just a 2 x n array) which contains a set of coordinates for the object to move using, returning null if a route can't be found.

Alternatively, any code which alludes to simple grid based motion planning which I can modify to the effect above would be helpful.

Thanks
Erain
m4ster r0shi (2201)
Last edited on
Erain (19)
I'm not good enough at coding yet to translate psuedocode into C++, which is why I posted in the beginner forum. I'm sure it must exist in accessible source already?

But yes, the algorithm I'm looking for is this one in C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
 function A*(start,goal)
     closedset := the empty set                 // The set of nodes already evaluated.     
     openset := set containing the initial node // The set of tentative nodes to be evaluated.
     g_score[start] := 0                        // Distance from start along optimal path.
     h_score[start] := heuristic_estimate_of_distance(start, goal)
     f_score[start] := h_score[start]           // Estimated total distance from start to goal through y.
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from[goal])
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)
 
             if y not in openset
                 add y to openset
                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
     return failure
 
 function reconstruct_path(current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from[current_node])
         return (p + current_node)
     else
         return current_node

m4ster r0shi (2201)
Ok, I think this will do -> http://theory.stanford.edu/~amitp/GameProgramming/

Check section 3b (Implementation notes -> Source code)
Topic archived. No new replies allowed.