Optimal Grid Path Finder (A Star)

Average Rating:  
X Rating Failed

Always finds the best possible path to a single or set of goals.

  • Supported Platforms
  • Supported Engine Versions
    4.17-4.18

Description


Example In-Action Video of Function Utilized in Tower Defense Game


Do you need a pathfinder that will navigate obstacles on your grid without any chance of failing? I DID TOO!

A* is state of the art in efficient and optimal path-finding; but, it's a pain to implement without support for multidimensional arrays, so I did it for you!


This function takes a grid of clear or occupied spaces in relative X and Y locations with a minimum index of (0,0), and finds the fastest route between an input set of X and Y goals. I have included an example of how to create the occupied array from a grid of tile actors, as well as how to create a grid of tile actors with X and Y location identifiers. The output of the function is the set of movements which resulted in the optimal route, and I have also included a way of converting those movements into X, Y, and Z vector locations to be used in MoveTo commands along with an array of which tiles will be traversed in which order.


I use this for my grid-based game before the player may perform any actions that might make a route impossible, and for creating the final navigation route for my AI. It features an input setting to enable or disable diagonal navigation.

Technical Details


Features:

  • A* Pathfinder (with diagonal/no diagonal option)
  • Vector Path Creation Example (from A* output)
  • Obstacle Array Creator Example (for A* Input)
  • Basic Grid System Creator Example (with normalized X/Y Identifiers Starting at (0, 0) for Obstacle Array)
  • Basic Tile Grid Example (Spawned by Grid System Creator)
  • Basic Map/Player/Controller/Game Mode Example with Obstacle Update and Path Display
  • Complete Call Sequence Example for Start to Finish Path Creation

Number of Blueprints: 7

Supported Development & Build Platforms: The core pathfinding blueprints only utilize basic 1D Unreal arrays and operators. Go crazy.

Documentation: Documentation/comments available within the Pathfinding Blueprint.

Important/Additional Notes: Click to create an obstacle in the example level. Goal tiles currently set to the 4 corners of the grid, these can be changed in the Basic Tile Grid. The one limitation is that this function assumes a square grid, you will want to fill your grid out with occupied spaces to shape it to a square grid with indices between (0, infinity) for X, and (0, infinity) for Y if it is not.

Comments

!

Previous Next
  • Edit
  • Preview
  • Help
Enter
Login to comment
X Report this Comment
Report
X Attention


close
X Edit this Comment
  • Edit
  • Preview
  • Help
Update
X Remove this Comment

Are you sure you want to remove this comment?

Remove
X Attention