Programming: Pathfinding Pt. 3 (A-Star Function)

 With the tile collision and tile artwork laid out, now I only need the enemy objects to follow them. Currently, they are just following a straight line from their current position to the target position, with no regard for any "Walls".  

Principles of Pathfinding

The A-Star Search is the backbone of pathfinding. There are many resources online that describe it in better detail, but I'll summarize it here for my own learning. It is used for finding the optimal path between two coordinates based on the weighted movement options. Based on the tile setup in previous posts, the screen can be summarized as a weighted grid of nodes.

The movement between each nodes is a directional vector (ex: moving one node right is a [1, 0] vector). The cost of each movement is weighted, either based on distance (an orthogonal movement is weighted as 1, while diagonal is weighted as 1.41) or special conditions (slowing effects on certain nodes increase cost value). From the start position, the cost value of each neighboring node is assessed. A heuristic calculation is performed to sum the movement's cost and the remaining required distance for each node. The neighboring node with the lowest heuristic value is considered the best move. The neighboring nodes from that position are then calculated. This reiterates until the goal node has been reached.

Apparently, this algorithm was published in 1968 for use in graph traversal. I'm not certain where that is used; perhaps it's something like Google maps, which generates multiple paths to a destination based on distance, traffic, and cost,  but I'm certain if they didn't think it'd be used for programming AI for fun little games. 

The Pseudo-Code

  1. Convert the "Start" and "End" coordinates to tile vectors
  2. Input "Grid", "Start", and "End" values into A-Star Search function
  3. A-Star Search function:
    1. Create a "PriorityQueue" object with heap functions 
      1. Heaps are data structures similar to lists, but always sort items based on value (smallest to largest). This will be used to determining the shortest route between two nodes, based on the weighted "Cost" value of movement.
    2. Inputs the "Start" node into the "PriorityQueue"
    3. Create empty "Path" and "Cost" dictionaries
    4. Create "Check" node equal to "Start" to start iterating through nodes
    5. For each neighboring node ("Neighbor"), determine if:
      1. "Neighbor" is available (not in "Walls" list)
      2. If so, check if "Neighbor" has already been added to the "Cost" list, or
      3. if so, check if the "Cost" value is less than existing value
    6. If "Neighbor" passes the check:
      1. Assign cost value to the "Neighbor" key in the "Cost" dictionary
      2. Calculate "Heuristic" value from the sum of: 
        1. Cost value of movement to "Neighbor"
        2. Remaining distance from "Neighbor" to "End"
      3. Set "Heuristic" value to the "Neighbor" key in the "PriorityQueue"
      4. Calculate directional vector from "Start" to the "Neighbor"
        1. Assign the directional vector to the "Neighbor" key in the "Path" dictionary
    7. Update the "Check" value to the lowest "Heuristic" value in the "PriorityQueue"
      1. This decides which node is the optimal choice for efficient 
      2. Additional neighboring nodes are assessed per Steps 5-6 from the updated "Check"
      3. Reiterate until "Check" equals "End"
      4. The A-Star Search returns a dictionary of vectors, with node keys
      5. See below for the visuals of the A-Star search. 
Interestingly, the algorithm tried going from the left (8, 10), but then realized it would take too long in the next iteration. This evident from the Iteration 2 nodes on the bottom left. Also interestingly, the algorithm starts at the end, and walks backward to the beginning
  1. Create vector list from A-Star "Path" dictionary: 
    1. Create "Temp" node equal to "Start"
    2. Create empty "Directions" list
    3. Input "Temp" as key to "Path" dictionary to get vector
      1. Add vector to "Directions" list
      2. Update the "Temp" node with vector
    4. Reiterate until "Temp" equals "End"


With the directional vectors created, now I only need to apply it to the enemy object. The vectors will need to be translated back into coordinates for updating the enemy.x and enemy.y values. Some additional work will need to be done to iterate through each vector properly.


Comments

Post a Comment