Name: Navigation for Groups
You will learn: Path-finding algorithms, Max-flow algorithms, Search in general
Difficulty: moderate
Excitement: Create cutting edge algorithm for group path-finding
Description: Navigation of single agent is relatively easy. Navigate the whole group is not. Many games struggles with group navigation as it cannot be decomposed to finding N separate paths for N agents using existing path-finding mechanism. You need to take a movement of other characters into account, which should not stack in narrow passages if there is a viable (not so long) detour near by!

Thesis steps:
  1. formulate group path-finding and path-following problem
  2. come up with constrains that might be required as input for the path-finding (e.g. max. detour)
  3. create several (from stupid to interesting ones) grid-based algorithm for the group path-finding
  4. use database of 100k+ maps as a benchmark for your algorithm

theme/path-finding_for_groups.txt · Last modified: 2016/02/09 17:47 by jakub.gemrot