Limited Intelligence.

I am programming a bot for weewar and have thus far implemented a simplistic path finding algorithm. By simplistic, I mean as simple as a short-sighted robotic vacuum cleaner. Each unit will seek it's target (an enemy unit or base) by moving to the next closest traversable node out of a list of possible nodes repeatedly until the target is reached.

The bot could play but was too stupid to provide a real challenge. Units would swarm out of bases and rush in the direction of the enemy regardless of obstacles en route, blindly feeling their way around the obstacles at a cost of many a wasted turn.

Above: notice the red soldier has moved from the red home base to what it deems to be the closest coordinate to the blue enemy base, however a soldier is unable to traverse water and so this turn was wasted.

It was clear after many lost games that a smarter algorithm was required and I by necessity entered the realm of pathfinding algorithms.

Units must be map-aware

In order for each unit to be aware of obstacles present on the map such as that shown in the image above, it is necessary for each node to be aware of every other node on the map.

My challenge is be to first form a suitable abstraction for the Weewar map and to implement an algorithm which would allow for a best path to be calculated from a single source-target pair for a given unit type.

Building a graph representation?

A graph G consists of a set of vertices and a set of edges, so I'm told.

The vertices (in this case, hexagon tiles) are uniquely identified by a coordinate e.g. (3.4). and the edges are a pair of connected vertices with an associated weight (the cost of getting from one to the other).

Although the weight is usually the distance between the two nodes, in this case it might be more useful to think in terms of the number of turns required to reach the target, as this is the true cost of getting around, and that cost varies from unit to unit.

this very simple map has the following graphical representation.

if we now remove non-traversable nodes, leaving only the plains, we can get an idea of what nodes are available for a particular unit to edge towards the base.

The first question is: what path should the bot soldier take to get to the enemy base with the lowest path cost, that is - the least number of moves.

Each soldier is given a number of possible tiles to move to in a given turn. Below shows the possible movement coordinates for the blue soldier:

There will therefore be an edge formed between the soldier's coordinate and each of the highlighted nodes which the soldier can reach at a cost of a single turn. In the following image, the unit can move to 20 possible tiles at a cost of one turn.

Armed now with a data structure containing all node coordinates:V and a data structure containing all edges E, the graph representation in terms of data structures is now complete and in part two I will consider the algorithms for traversing the graph to discover the best path.