Frequently asked questions about Project 2


1) I have no idea how to implement the GoalBoundsDijkstraMapFlooding algorithm! Help!


There are just two main changes to a traditional Dijkstra

  •  When a child node is processed and added/updated to the Open List, you need to update for that node what was the initial StartNodeOutConnection that was used to reach it. This can be determined by the node's parent. This is the "flooding" part of the algorithm. 
  • When a node is extracted from the Open List for expansion, due to A* and Dijsktra properties, it is guaranteed that there is no other shortest path to reach that node. Therefore, the saved StartNodeOutConnection for that node is the optimal initial connection to take to reach the node optimally. This means that we need to update the bounding box for the saved StartNodeOutConnection to include the new node. 

2) What should the GoalBoundsDijkstraMapFlooding algorithm return?

  • You don't need to return anything. Just update the received NodeGoalBounds with the bounds information described above. Take into consideration that the NodeGoalBounds has an array of Bounds. This array must be updated with the bounding box information. Use the StartNodeOutConnectionIndex as index for this array.
  • Do not create a new NodeGoalBounds. Update the one received. 

3) How do I access the GoalBoundingTable in the GoalBoundingA*?

  • Once the offline calculation of the GoalBounds finishes, Unity will create a new Asset file with the GoalBoundingTable. Move this asset to the Resources folder of your Unity Project.
  • In the PathfindingManager, you can load the GoalBoundingTable by performing the following instruction in the initialization:
    • var goalBoundsTable = Resources.Load<GoalBoundingTable>("GoalBoundingTable");
  • Use the loaded GoalBoundingTable to initialize the GoalBoundingA*.
  • The GoalBoundingTable has exactly the same ordering as the NodeArray. So you can use the Index used for accessing the NodeArray to access the GoalBoundingTable. It will return a NodeGoalBounds for the node whose index you specify. Then you can use the OutConnectionIndex for the connection you want to check the Bounds, as a way of accessing the corresponding connectionBounds.
  • There are some nodes who do not have NodeGoalBounds. For those, you process them as standard A*.
  • There may also exist some nodes that have a OutConnectionIndex that does not appear in the connectionBoundsArray. This likely means that this Connection did not exist when the Dijkstra was executed. Here you can apply the same rationale used in the previous point. Process a connection that does not have a connectionBound as standard A*.


4) When is the deadline for submission?

  • Monday night, 23:59:59, or Tuesday in the early morning 0:00. You can deliver it later with the corresponding penalties.