When playing around with this code I have found a bit of an anomaly in regards to A*.
I have generated a Maze of size 1000x1000 and just to play around with the code I wanted to switch the remaining distance (F cost) to see how it changes run time.
Just to note, the maze generates 641967 nodes.
When I run the maze with remaining = 0 these are the results I get:
Nodes Explored: 641799
Time Elapsed: 28.96
If I then change it so that:
remaining = math.sqrt( ((vpos[0] - endpos[0]) ** 2) + ((vpos[1] - endpos[1]) ** 2) )
(Euclidian Distance) these are the results I get:
Nodes Explored: 620100
Time Elapsed: 12.91
And then I use the remaining that was originally with the code,
remaining = abs(vpos[0] - endpos[0]) + abs(vpos[1] - endpos[1])
these are the results I get:
Nodes Explored: 595880
Time Elapsed: 34.63
How is this possible? The A* with Manhattan distance obviously eliminates more nodes than the other two but somehow performs the slowest? Is it that the call to abs is slow? I haven't been able to find any evidence that this the case. Any guidance would be helpful.
When playing around with this code I have found a bit of an anomaly in regards to A*.
I have generated a Maze of size 1000x1000 and just to play around with the code I wanted to switch the remaining distance (F cost) to see how it changes run time.
Just to note, the maze generates 641967 nodes.
When I run the maze with
remaining = 0these are the results I get:If I then change it so that:
remaining = math.sqrt( ((vpos[0] - endpos[0]) ** 2) + ((vpos[1] - endpos[1]) ** 2) )(Euclidian Distance) these are the results I get:And then I use the remaining that was originally with the code,
remaining = abs(vpos[0] - endpos[0]) + abs(vpos[1] - endpos[1])these are the results I get:How is this possible? The A* with Manhattan distance obviously eliminates more nodes than the other two but somehow performs the slowest? Is it that the call to
absis slow? I haven't been able to find any evidence that this the case. Any guidance would be helpful.