Path finding

The first problem I wanted to solve before I even started to think about how to structure the AI was path finding. If I can’t solve this, I thought, there is no need to start an AI side project at all… I’ll start discussing the AI structure in the next AI post but today I intend to focus on the path finder.

I did, as many of us self-made programmers do, start with a google search on path finding. One site I must recommend highly is ‘Amit’s A* Pages’. He goes through the theory behind path finding very well.

I decided to create an A* algorithm where the heuristic is set to always find the best path regarding total movement points. Diagonal movement is allowed and cost the same as straight movement (movement cost to enter a sector is only decided by what terrain type the sector has and not if you enter it straight or diagonally). This means that armies will move around obstacles like forests and hills, cross rivers where it cost the least movement points in a similar fashion to what I believe our players will do. The path finder also takes into account special racial and company abilities, for example a cavalry army will have to move around a high mountain but a wyvern rider can fly above it.

Before we look at the code for the path finder I would like to explain how our map is built up. We’re not using arrays as I understand is very common in 2D games. Instead we use maps where the key is a Sector and the value is a Location object:

Map<Sector, Location> maps

An empires memory is stores in corresponding memory classes:

Map<MemorySector, MemoryLocation> memoryMap

Here is an example of how the map looks in our editor:

In the code you’ll notice objects with names like Empire and Army. These are simply objects that contains data about an empire and its assets. I’ll not discuss these any more than just mention that they represent stuff in the game…