Pathfinding fails on some maps

[RedRaspberry]

For some reason, the algorithm gets 'stuck' in certain spots when there is a clear path from start-finish. For example, if i create a long/winding 1-width hallway, the algorithm will stop at the corners of said hall, and will move back and forth until it turns the corner.

Additionally (on rare occasions), placing an obstacle does not 'fully' work, ie the cell cost number is still visible, and the program will crash. I believe this could be the reason for the stopping mentioned above.

Thanks for all the help.

[mdeyo]

Yes, aware of this issue. I think it's because I'm doing the "move agent", "scan for changed edge costs", and "compute shortest path" operations in the wrong order each iteration, for simplicity in the interface. Feel free to experiment with them in the "Main Program Loop" of main.py and the moveAndRescan function from d_star_lite.py.

[mdeyo]

I might be able to spend more time on it later this week to see if I can come up with a solution.

[GBJim]

Hi @RedRaspberry and @mdeyo
This bug might be caused by the outdated heuristic.

I fixed this issue in my fork
I canceled the accumulating K_M variable and make sure the heuristic values are always the lastest.

[mdeyo]

@GBJim Good catch on the heuristic values and awesome improvements on the visualization! I will be sure to fix in my own code too.