Pathfinding

Last couple of weeks I have been working to improve my pathfinding algorithm. I am planning pretty big maps for the player and I want the AI to be able to travel the whole map independent of where the player is located. I want to ad mechanics like tracking/hunting for the player and for the AI. My previous algorithm was rather slow on larger maps so i had to improve this.

It took some time to get good results for a large amount of none player characters but i am on the right track. I am implementing hierarchical pathfinding which should reduce CPU power greatly at the cost of storage. Basically I split the map up in large chunks, calculate ideal routes from one sector to another and store them. This means that I only have to calculate pathfinding for these large sectors at run time.

It is basically how Google maps route planning works. Using detailed pathfinding to get to a highway, from there just use main highways and discard detailed map information and finally get the detailed information of the exact location you want to travel to.

Since all my maps are random I have to pre-compute all these sectors while the map loads. On a static map this would be much easier. The basics are there but there are some bugs where AI get stuck into a loop. The best part of this system is that it takes into account changes to terrain. I do foresee a problem though, when the terrain changes and the system is calculating a big detour the game might stall a bit.

My girlfriend is getting surgery tomorrow and the December month is always a busy month for me. I still hope to get some work done before the end of the year but I have to see how things go.