Terrain Analysis Tool
This page is dedicated to explaining the process and features of the first part of my third year project which was based around terrain analysis. This first section was a terrain analysis tool that could be used to feed in a map and then do various calculations on this to come up with an analysis that could then be used by AI within a game to produce more intelligent decisions.
Starting Point / Loading the Map
The first step was loading in the map and representing the map data in a reasonable format. A decision was made early on to use a waypoint based system based on the centre point of the polygons within the map. This approach has had many downfalls throughout the development of the tool especially when it came to the map design as the maps could only be made up of a small number of polygons(Max 10,000) before the tool began to slow. A separate waypoint system could be fairly easily be put in place with the added functionality of specifying the distance between all the waypoints. This would give greater control over the analysis process and also reduce the number of nodes in highly detailed maps.
Once all the data is read in from the map, the adjacency data is generated to create links between all the waypoints(nodes) within the map. This was a bottle neck toward the beginning of the project due to the sheer number of iterations needed. After various optimisations this process is no longer an issue although it has not been extremity tested on maps with over 20,000 nodes.
Once all the data is read in from the map, the adjacency data is generated to create links between all the waypoints(nodes) within the map. This was a bottle neck toward the beginning of the project due to the sheer number of iterations needed. After various optimisations this process is no longer an issue although it has not been extremity tested on maps with over 20,000 nodes.
Height Map/ Passability Map
The next step involves creating an impassibility map using a height allowance. The height allowance can be altered and changed using the tool bar that is mentioned in the section "AntTweak Bar". The nodes in the map are represented as small sphere models and the colours represent their passability as you can see in the image. The renderer was third party code and was extremely simple which meant the tool suffered when maps had many nodes. This was due to the renderer doing a draw call for each model. Implementing a better renderer would allow for the use of larger maps within the tool.
Impassable Zone Generation
Once the Impassable nodes are all generated a flood fill algorithm was used to generate impassable zones for use with later steps of the terrain analysis process. As you can see in the image the zones are separated into different colours based on the zone that they are in. White nodes represent nodes that are passable. Using the tool bar the impassable and passable nodes can be switched on or off depending on which you would like to view. This was a way of minimising the effect of the naive renderer.
Influence Mapping / Chokepoint Discovery
This next process essentially used the impassable areas and firstly set a starting influence which was generated from the tool bar from user input. It then spread this influence across the adjacent nodes until an influence from two different areas was found. Once the influences had spread the influenced nodes were shown as blue and nodes with multiple influences were shown as purple. This particular part of the tool was where most of my time was spent, tweaking the conditions that had to be met for the influence to spread.
Chokepoint and Game Zone Generation
Once all the influences have been spread, any multiple influence nodes are then traversed backwards until they find an impassable node and these paths are used to create the choke point game zones. The rest of the game zones are then generated into game zones using a simple flood fill algorithm.
Strategy Point Generation
This next step was added later on as a feature that can be directly used for the second part of the project. It involves targeting specific nodes on either side of the choke point that are the extremities of the choke point game zone. They are used for strategic positioning within the game demonstration. A specific improvement that was noted by one of my tutors at the time was to use a line of sight algorithm in combination with this approach to ensure that the troops could not be seen directly through the choke point.
Exporting Map Data
Once all the strategy nodes have been created the next step is exporting this data for easy use with another project or game. This was done using XML, the data was exported as game zones showing the nodes that were strategy nodes along with various data such as adjacent game zones, node adjacency and passabillity.
AntTweak Bar
A third party tool was used to develop a small interactive GUI for use within the tool that allowed the user to input specific data relevant to various sections of the tool. This tool worked well although there was some issues with the communication of data with the tool bar. As you can see in the image there are various formats of data that can be used by the tool bar such as floats, booleans and buttons that can be used to add step-by-step functionality.
Looking back I think a better choice would have been C# or Windows Forms and that could be one area to look into for further development.
Looking back I think a better choice would have been C# or Windows Forms and that could be one area to look into for further development.
Update: 02/08/2012 Instancing
I have updated the Terrain Analysis Project recently to use DirectX 10 to perform geometry instancing on the sphere models. This allows the tool to perform the analysis on much larger maps without the frame rate suffering. Below is a video of the terrain analysis tool, mostly showing off the instancing of the analysis tool:
