PathFinder

Right, following the lost of all RTS-X source code, I'm back to square one with anything everything I ever done with path-finding. Despite the fact that the one I have before was not very robust, or performance friendly, or flexible in different terrain.

Anyhow I have tried my hand at A* path-finding again. I plan to put it in TDTK for open field tower deployment mode. Figure I would need it in rebuilding RTS-X as well. Only this time I'll do it properly and make a complete path-finding project that would be useful in a variety of other future project I might have. Or at least that's the plan...

So this is what I manage so far:

• auto grid-graph generator on the terrain.
• height-consideration for connecting neighbouring node.
• somewhat optimised standard A* path-finding algorithm.
• post searching path-smoothing.

The performance for this one is not perfect but it's a big improvement from my last attempt some months ago. At least it works alright in this simple demo with 5 agents searching simultaneously without noticeable drop in the framerate. As seen in the image below.

Searched path (start from green dots to red dots) for five agents in blue color

.

The path seraching involves node with different height doesn't quite work yet, especially when the path smoothing comes in. But the path smoothing works just fine. So instead of going through all the nodes in a path like being shown in the image above which make the grid-based path very obvious, the agent only need to traverse through minimal number of path. Hence a more natural path. Just like the image below, a big improvement indeed!

Path smoothing which reslut in much fewer node to go through in each path.

So the next plan would be more optimization to cut down the processing time and get the height difference of the grid to work. I might look into navigation mesh implementation. Something that sound brilliant in theory! But to be honest I myself have been struggle to derive it's implementation from all the material I've look into. This will be interesting...