Pathfinding

Over the weekend I was working on pathfinding. I'd already done some research and A* (A-star) pathfinding sounded to be exactly what I needed.

The code was fairly easy to design a basic solution and from the word go I had included a weighting system for squares I wanted bots to prefer. Such as near to cover.

Modifying the map file to include the weighting values took me longer to implement than the pathfinding.

The bad news. Even on the PC pathfinding took much longer than I had anticipated. At first I thought it wasn't working but when I left it 5 minutes it did calculate the paths. The problem was the first path I had given it was very long and it exceeded the 90,000 iterations I had set as my limit. I always add a limit when I use a while() to avoid endless loops!

I added some quick fix optimisation to my code. The first being to remove the closed list because it is unnecessary. A closed marker is more efficient.

At the moment I have also limited how many items it will check on the open list. The disadvantage is that on longer routes I may not get the best path, just any path!

I had also made some errors with the weighting levels I had set. These took some experimentation to sort out. Initially I had made the weights far too high and the paths got driven in to the wrong areas making them unnecessarily long!

At the moment on the PC, all my test paths now calculate quickly enough that you cannot notice unfortunately on the XBox 360 there are short pauses whenever a new path is needed! I'm already using a dedicated hardware thread on an otherwise unused core, just for the pathfinding!

That's where I'm at. I intend to pre-calculate as many paths as I can and I expect that will be sufficient but I am still researching and thinking, more than coding, on this bit.