Village the Game: Play it. Love it. Live it.

AI Pathfinding Write up

We need to create a lightweight pathfinding algorithm to support 100 villagers running around on one map that ranges in size from 64x64 tiles to 128x128 tiles. This pathfinding algorithm should be written in C, or C++. The map on which villagers are moving contains heavily trafficked routes as well as completely untrafficked areas such as river or forest. The AI should be able to handle basic collision between two villagers and reroute them efficiently. A typical map will have a town center which is a very common destination for the villagers and 20 to 80 huts which are another common destination but more spread out. The edges of the map do not wrap around like PAC-man. The map just ends there. The villagers can move in 8 directions only. up, down, left, right and the 4 diagonals in between.
Further requirements:

1. For weighting tiles on ease of traversing, use the scheme: 0 = impassible, 5 = open grassland, 10 = well-paved road. Conditions of a tile can change over time, for example dirt roads (6) can be improved to well-paved roads (10).
   
2. Destinations for some paths are multiple tiles. For example, a villager can complete a walk to Kickstart store by arriving at any tile adjacent to the Kickstart store.
   
3. Pathfinding has to allow for interruptions. For example, the player avatar can walk up to a villager and the villager must stop to converse and then resume walking after the conversation.
   

This code will be incorporated into a realtime strategy game built on Torque Game Builder. We'll be testing at the minimum system specs that GarageGames recommends on Windows.
Windows Minimum: 500 MHz processor, 256 MB RAM, Windows 98, OpenGL or DirectX compatible accelerated 3D video card.

Here is a sample map where villagers will often be walking:

Labels: design