GSoC Smarter pathfinder: Difference between revisions
More actions
imported>Brain damage New page: = GSoC idea: Smarter pathfinder = == Why == Current pathfinder is rather inflexible and inefficient. == Background == Spring's pathfinder uses a 2d grid and is somewhat limited in functi... |
imported>Abma No edit summary |
||
| (7 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{deprecated|deprecated: kloot is already working on this}} | |||
= GSoC idea: Smarter pathfinder = | = GSoC idea: Smarter pathfinder = | ||
| Line 4: | Line 6: | ||
Current pathfinder is rather inflexible and inefficient. | Current pathfinder is rather inflexible and inefficient. | ||
== | == What == | ||
Spring's pathfinder uses a 2d grid and is somewhat limited in functionality. A partial/full rewrite should be introduced to add support for navigating using more than 8 primary directions and selectively ignore certain unit types for performance reasons. | Spring's pathfinder uses a 2d grid and is somewhat limited in functionality. A partial/full rewrite should be introduced to add support for navigating using more than 8 primary directions and selectively ignore certain unit types for performance reasons. | ||
| Line 12: | Line 14: | ||
== Required skills == | == Required skills == | ||
* | * Knowledge of graphs and pathfinding (particularly navigation graphs) | ||
* C++ | * Knowledge of C++ | ||
* Knowledge of Lua API/C bindings | |||
== Difficulty == | == Difficulty == | ||
Estimated: hard | Estimated: hard | ||
== | == Technical details == | ||
The pathfinder is one of the better encapsulated subsystems in spring; generally, there will only be minor changes required in the rest of the engine, if any. There's a lot of algorithmic work to do under the hood, though: | |||
* Cooperative pathfinding exists in a very scant form and could be greatly improved | |||
* Navigation mesh could be introduced for better paths and faster searches - at the cost of generating the mesh and updating it online due to terrain modification | |||
[[ | [[Category:GSoC]] | ||
Latest revision as of 19:23, 7 March 2012
| File:172px-Symbol comment vote.svg.png | deprecated: kloot is already working on this |
GSoC idea: Smarter pathfinder
Why
Current pathfinder is rather inflexible and inefficient.
What
Spring's pathfinder uses a 2d grid and is somewhat limited in functionality. A partial/full rewrite should be introduced to add support for navigating using more than 8 primary directions and selectively ignore certain unit types for performance reasons.
Spring's Lua API should be extended to allow game developers to push new nodes/links and be able to alter or delete existing ones. (for pathfinder-aware tunnels/teleporting/etc.)
Preferably this all should also be faster then the current system, or a compelling argument/experiment should be made that shows there can not be a faster system with the same features.
Required skills
- Knowledge of graphs and pathfinding (particularly navigation graphs)
- Knowledge of C++
- Knowledge of Lua API/C bindings
Difficulty
Estimated: hard
Technical details
The pathfinder is one of the better encapsulated subsystems in spring; generally, there will only be minor changes required in the rest of the engine, if any. There's a lot of algorithmic work to do under the hood, though:
- Cooperative pathfinding exists in a very scant form and could be greatly improved
- Navigation mesh could be introduced for better paths and faster searches - at the cost of generating the mesh and updating it online due to terrain modification