A^* Exercise

As before, clone and edit the World.

Click to run World: A star at Ancient Brain.

• Change the various customisable values.
• Change open and closed colours to white. It looks smarter!

• Change it to no walls at all, diagonal.

• Change it to no walls, no diagonal.
  • It looks like it is not finding the shortest path. But it actually is. Why? It is a bit counter-intuitive.
  • Even if it is shortest path, why does it take so long to find it?

• To figure out why it picks the square it picks:
  1. Write f = g + h values to console with console.log.
  2. Slow it down. Change the speed. See the "frameRate" line.

• We have diagonal / no diagonal, and 2 heuristics. Try all 4 combinations.

Change h and g

• Change the heuristic function to the following, and see (in console) what happens and why.
  • Zero
  • Constant high positive
  • Constant negative
  • Negative distance to goal
  • Negative multiple of distance to goal
  Note g compensating for an inaccurate heuristic!

• Try inaccurate g and h values:
  • Change g value to minus the correct g value, and h value to minus the correct h value.

• Note on Shiffman's code:
  • Shiffman on line 115 has the following:

     var tempG = current.g + heuristic(neighbor, current); 

  • g is being built up in a cumulative fashion, using the h value of two adjacent squares.
  • This works ok in the way Shiffman uses it. But when we try changing h to something illogical, we break g.
  • So for my code, I make g and h separate functions that can be changed independently.