In his terrain reasoning masterclass in October, William van der Sterren presented a simple yet effective algorithm for creating areas from an underlying graph of waypoints. The algorithm uses a variety of factors, and can be tuned to provide very useful areas depending on these factors. These areas provide a simplified yet sufficiently accurate representation of the terrain that can be used to speed up most algorithms that don’t require point perfect information.
An implementation of this algorithm was just released as part of the AiGameDev.com Sandbox. The result of processing a 32×32 grid looks like in the following video:
Creative solutions to problems often come from trying to reproduce algorithms that already work well (without necessarily knowing how they are done). So, here’s your chance to brainstorm how to solve this problem. The requirements are:
The algorithm should not require too much processing time, and provide sensible results very quickly.
If more time is available, the algorithm should be able to find good areas from the input graph.
The algorithm should be able to take into account various area criteria specified by the programmer.
Get those problem-solving juices flowing, and post your ideas below in the comments. (If you’re a member, please try to post different ideas than were described by William or implemented in the demo.)