Path Finder Demo

Using the mp_grid_path function in irregular or changeable maps

The grid path function finds a route through a map where each cell of the map can be either clear or obstructed. The basic explanation of this is that you can use it to find a route through a room made up of equal sized blocks. The resulting route mostly consists of x-aligned or y-aligned sections with occasional diagonals.

The route returned has nodes at every intermediate grid cell. This may or may not be desirable. It is possible to assign this path to the instance, in which case the instance will simply move along the path from start to finish without reacting to other instances. A more sophisticated strategy might pause or abandon the path in response to events.

Another method is to have an instance AI that already "knows" how to move towards a point that is not obstructed and simply feed it path nodes as "waypoints" to enable it to navigate past substantial obstructions.

The following code block scans a path "pth" and deletes redundant path nodes.

m= path_get_number(pth); 
if m>2 for (n=1; n<m-1; n+=1)
{
  x1=path_get_point_x(pth,n-1)
  y1=path_get_point_y(pth,n-1)
  x2=path_get_point_x(pth,n)
  y2=path_get_point_y(pth,n)
  x3=path_get_point_x(pth,n+1)
  y3=path_get_point_y(pth,n+1)
  if (x2-x1)*(y3-y2)=(x3-x2)*(y2-y1) 
  {
    path_delete_point(pth,n);
    n-=1;
    m-=1;
  }
}

Reading the resulting path will give you a list of "waypoints" where the path changes direction.

The path finder example (Updated path Finder in GM Studio: pathdemo.gmz ) is meant to demonstrate this. The GM Studio version shows three route strategies.

Press 1,2 or 3 for different strategies. Press the left mouse button to see the path. Press the right moiuse button to see the grid.

Example 1 is normal grid pathfinding but ignoring minor obstacles.

Example 2 is 1 but with movement using mp_potential_step. The grid is configured to ignore little walls that the ghost can navigate round and only register blocking walls.

Example 3 is like 2 but the grid is coarser, it only stores the coarse detail of the map, but using potential step movement it can still navigate the irregular passages.

Updated path Finder in GM Studio: pathdemo.gmz

Old Path Finder example (GMD)