Dungeon Crawler - 2D Path Finding

I've had to create a test-bed piece of code for the path finding, so this means there's been no changes to the game side of the code, all the work I've been doing on things over the last couple of days has been about the path finding and it's been in this test-bed application.

So, the application lets me see the grid (or graph if you're a mathematician), I can select the start point, the end point, set blocked grids and then ask it to calculate a route.

The algorithm I've used is an A* algorithm, but a greedy one, and then I've added back-tracing to allow it to get out of dead-ends (such as in a room with a narrow opening) and finally added simplification to the end result route.

The calculation of the route and back tracing is automatic, the simplification however, I've made a manual operation, so I can see how the routes come out of A* before I alter the list of plotted points.

Without the back tracing this is how it could get stuck:

And now, it back traces to the next best nearest grid point to continue the route without getting stuck or going over the points it's already found got it stuck:

And finally, I can apply a simplification to that solution:

I'm now pushing it further, asking the test-bed to work it's way around simple dungeon style rooms, here we see the route from inside one room, down a set of halls and into a cell within another area...

Simplify this result:

And it's quite neat.

The test-bed needs some more features, such as loading/saving the background blocks, making the start of a rudimentary map editor!

Once I'm more happy with the algorithms and heuristics I'm using, then I'll start to tidy the code and then port it into classes for use in the Dungeon game... And finally I'll start to make the movement routines take the list of points to go between...

Note: Since writing this draft, I've continued the work and testing... Only to find a strange problem, which was working, but I've somehow broke, here we see a grid... The Route can continue, but it just stops...

Hmmm, what have I done wrong?


-- Addition --

Since posting this last night at half six, I worked out the bug resulting in this dead end problem above, here's the result now:

Then simplification run on this route:

The challenge now is to simplify, clean up and better document this code.  Then to port it to clear easy to maintain C++