Assignment A4

A*

Description

Implementation

Basics For this assignment, we implemented a basic pathfinding algorithm, A*. In it we have two heurstic cost estimate functions that are available to use. Manhattan Distance and Euclidean Distance. The two testcases used are very simple, so it is a little difficult to see the difference between the two.

Assignment Breakdown

  1. Part 1
    2. Part 1 was the bulk of the assignment. We implemented A*, and the manhattan and euclidean distance heuristic cost functions here.
    Click here
  2. Part 2
    3. For part 2, we had to implement a tie-breaker for nodes with the same smallest f-value by determining based on the g-value. We used the (higher or lower) g-value.
    Click here
  3. Part 3
    4. For part 3, we had to implement an increase in the cost to the diagonal neighbors. Initially, all the neighbors had the same cost.
    Click here
  4. Part 4
    5. For part 4, we had to implement an increase to the weight of the hueristic cost. Essentially, to create weighted A*. We considered the bigger g-value for setting the tie-breaker between f-values.
    Click here
  5. Extra Credit
    6. For extra credit, we merged A* search with the social forces AI.

Github