I have implemented prototype of flowfield pathfinding algorithm and I need some help. The concept is here:
http://www.gameaipro.com/GameAIPro/Game ... _Tiles.pdf
It's about generating vector field, directing to goal(s). It's strength is that we can have the same field for any number of units, moving to the same goal. It also enables further development of steering behavior and collision & obstacle avoidance, because there is no need for path recalculation each time an unit is forced to avoid something. It's more expensive to generate than A*, though.
This is my first contribution to WZ and I know maybe 1% of codebase. I have rough prototype ready, but I have trouble integrating it into existing code.
The algorithm generates both A* path and the flowfield. The path is used as approximation until flowfield is ready. Right now I only integrated the path, and droids should ignore the path as soon as flowfield is available. But WZ code seems tightly coupled to path and I don't know how to deal with it. The current direction vector from flowfield should be merged with current movement direction to make turning smooth.
The prototype has some limitations:
- It does not analyze owner side of the droids (that might be problematic)
- It does not care about danger/threat map (that might be easy)
- It assumes FMT_BLOCK (that should be easy to change, tiles blocked by structure would go into integration field)
- It does not update anything when structures are created / destroyed. (I have to write code to invalidate stuff and rebuild some, it might be tricky with already moving droids)
- Included debug draw code is very hacky, as I don't know how to draw stuff on tiles correctly (current code works acceptably only on initial zoom and rotation)
- I used some stuff from Qt, because I didn't know about plans to get rid of it. It's QElapsedTimer (for debug only), QThreadPool and QCache. I decided that first I would like to have it working and then to have it working good.
- I haven't tested it with savegames, and probably loading a save will make all moving droids to stop.
- No idea how it will behave in MP games, no code for debugSync has been made.
- I have compiled it with MSVC 2017 on Windows, and this compiler is known not to conform to standards (although it gets better).
- Currently there is only one goal - x,y where player has clicked. But the code can support an area of goals (for example, for preserving formation). It might have edge cases, but it is already used internally.
- There is no Line-of-sight pass, as described in the article. I considered it too complicated, and not-that-much beneficial. It's about ignoring the flowfield and moving directly to goal. What is WZ already doing for VTOLs.
The code: https://github.com/Perl99/warzone2100/t ... -prototype
Code: Select all