Mission Accomplished: Time to Play - Programming GPS and OpenStreetMap Applications with Java - page 200

13.4 Intelligent Players

Artificial intelligence (AI) is the challenge for programmers; usually the
problem is to find a feasible environment to experiment with. Although
the ROAF was defined not to implement any intelligence, it does provide a
perfect framework to experience the effects of decision making. In the long
run, any RealObject has to have some intelligence to find its way through
the real world (applications).
Implementing a RealTrain in the ROAF is not a great challenge. The
train could easily be simulated by supplying its actual schedule and the
digital map data of the corresponding tracks. A RealBus is a little less
predictable, since it does drive according to a schedule, but also has to deal
with the trac on its route. A RealCar (or cab) has even more freedom
(unpredictability) than the train or bus. It is restricted to streets (solid,
even surface); within these limitations, it has a choice.
Artificial intelligence can only make choices within the given degrees
of freedom. In London Chase, each player has to move on the digital
map's links and only has the choice between the direct neighbors of its
current station. The chaser should choose the best path to the runner, while
analyzing the runner's behavior and predicting his next move. The runner
should basically do a similar analysis, albeit with opposing conclusions.
Depending on the size of the network and the number of players on each
side, the strategy can become complex and time consuming to implement.
Before implementing the actual decision making, the game can be defined
in terms of heuristics: a graph, a tree, search algorithms, etc. Then, each
individual player can decide how to search. AI literature provides hundreds
of approaches including Nilsson, A-star, minimax algorithms, alpha beta
pruning, by breadth, by depth with (variable) weights and functions for
nodes and edges, etc. The reader should choose his favorite algorithm!
The game of London Chase is the ideal (beginner's) environment for
intelligent and dynamic route calculations. The AI player introduced in
the following sections shows one way to interpret the game. In the long
run, the environment will get more complex and the algorithms need to be
adapted accordingly to give the RO a good orientation in any situation it
may face.
Note that a navigation system is using complex calculations for the
current position and route. Nevertheless, most people would not follow
the calculated route in their own city. People sense even more parameters
than the system.

13.4.1 Creating a New Player
Here's a quick start guide for creating a new player that we will designate
as AIRunner :