Flowfield prototype

For code related discussions and questions
Post Reply
Perl99
New user
Posts: 3
Joined: 10 Nov 2018, 20:01

Flowfield prototype

Post by Perl99 » 10 Nov 2018, 21:40

Hello,

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
Example: https://youtu.be/Bspb9g9nTto?t=113

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.
I hope someone can help me with integration or give some directions and explanations of code related to movement.

The code: https://github.com/Perl99/warzone2100/t ... -prototype
Run with

Code: Select all

--flowfield

User avatar
vexed
Inactive
Inactive
Posts: 2471
Joined: 27 Jul 2010, 02:07

Re: Flowfield prototype

Post by vexed » 12 Nov 2018, 03:34

I was looking into doing something like this years( :oops: ) ago, and just never had the time to finish anything.

We were given the source "as is", without any documentation at all, just what you see in the source, and even then, there have been times when those docs aren't actually doing what it says it is doing.

I am not sure who last touched the code, or even knows all the in's & out's of it, so, unsure who would be the best person to point you to. Perhaps Cyp or maybe Per can answer some more detailed questions, but, I think they both did the bare minimum with that side of the source.

I am not around much these days either, busy with RL stuff, so, basically, I wish you luck, WZ is really in need of these kind of enhancements to make the game more enjoyable for all!

Haven't had a chance to look at what you are doing before I leave again, but, IIRC, there are some GPL compatible flowfield (and steering) type libraries out there, unsure if you are using that or not, but I always favor stuff that has been out for awhile to get the kinks out over something home-brewed, and it needs to be deterministic, or it will cause desync errors.
/facepalm ...Grinch stole Warzone🙈🙉🙊 contra principia negantem non est disputandum
Super busy, don't expect a timely reply back.

Perl99
New user
Posts: 3
Joined: 10 Nov 2018, 20:01

Re: Flowfield prototype

Post by Perl99 » 20 Nov 2018, 18:11

All is coded by me, except for Qt stuff. I wanted to have more control over it. I have only found some simple examples on the web so far, no libraries.
I'm not sure if the code is 100% deterministic. It is divided into tasks, computed in parallel, which might get slightly different order. That could result in different times when a part of the flowfield is available to different players. So droids might take slightly different paths (maybe). That part is still missing, so that is my guess.

I just hoped there is someone who touched the code in move.cpp, maybe fixed a few bugs and has and idea what is going there.

User avatar
NoQ
Special
Special
Posts: 6197
Joined: 24 Dec 2009, 11:35
Location: /var/zone

Re: Flowfield prototype

Post by NoQ » 20 Nov 2018, 21:35

No idea how it will behave in MP games, no code for debugSync has been made.
The overall idea is to make the behavior entirely deterministic. Your code should not rely on wall-clock timeouts but should instead rely on timeouts formulated in terms of game frames, should not use floating-point arithmetic but should instead use integer arithmetic, should not use standard library's random values but should use the game's custom Mersenne Twister that yields the same result on all machines across the network, etc.

As far as i understand, the current pathfinder is implemented as follows:
  1. Clients agree on the lag value L (say, "L = 2 game-frames", which amounts to 200ms) that is computed deterministically based on mutual ping values. Not sure if this value changes throughout the game.
  2. Every order given by the player to its units is delayed by the lag value. I.e., if the order is given on frame N, units will only start moving on frame (N + L). But the pathfinder is already allowed to run in the background thread as soon as the order was given locally.
  3. Similarly, if the order for the opponent's unit is received from the network, it is timestamped with the value (N + L) on which it starts executing, but pathfinding starts immediately. Such pathfinding is guaranteed to yield the same result on all machines due to determinism.
  4. The lag value ensures that the game can run smoothly because whenever it has received full information about frame N, it can precisely predict the future until frame (N + L) inclusively.
  5. If the game has displayed everything it can predict to the user but it requires more inputs to proceed, it hangs and displays the "Zzz" icon. Such inputs may include packets from other peers on the network or results of pathfinding that are received from the background thread on indeterministic moments of wall time. In particular, if a certain peer cannot finish pathfinding in time, it will keep all other peers hanging until its own pathfinding thread yields results, because only then will it be able to send information about the next game frame.

Cyp
Evitcani
Evitcani
Posts: 714
Joined: 17 Jan 2010, 23:35

Re: Flowfield prototype

Post by Cyp » 20 Nov 2018, 23:02

I think that's almost right, except that I think pathfinding has to start at the same game time, since the result depends on the game state at the time it starts.

Per
Warzone 2100 Team Member
Warzone 2100 Team Member
Posts: 3755
Joined: 03 Aug 2006, 19:39

Re: Flowfield prototype

Post by Per » 23 Nov 2018, 03:02

Note that the generation of the path/flow only needs to be deterministic if the same computation needs to be done on each peer. If the droid owner does the path/flow computation and then sends it to the other peers over the network, and they can follow this path/flow deterministically from a common point in the future, then that will also work. This would also likely reduce the CPU load a lot, since not everyone then needs to do all the path/flow calculations, but only their own.

Forgon
Code contributor
Code contributor
Posts: 172
Joined: 07 Dec 2016, 22:23

Re: Flowfield prototype

Post by Forgon » 13 Dec 2018, 20:11

Perl99 wrote:
10 Nov 2018, 21:40
[...] The code: https://github.com/Perl99/warzone2100/t ... -prototype
Run with

Code: Select all

--flowfield
Unfortunately, I failed to compile your prototype.

After executing `./autogen.sh && ./configure CFLAGS='-O2 -gstabs -g -g3 -pipe' CXXFLAGS='-O2 -gstabs -g -g3 -pipe' && make -j6`, I encountered a warning about an MSVC-specific pragma:

Code: Select all

In file included from clparse.cpp:45:
flowfield.h:4: error: ignoring #pragma warning  [-Werror=unknown-pragmas]
 #pragma warning(disable: 4201)
After silencing it by adding '-Wno-unknown-pragmas' to CFLAGS and CXXFLAGS, I ran into linker errors:

Code: Select all

/usr/bin/ld: clparse.o: in function `ParseCommandLine(int, char const* const*)':
/home/x/flowfield/warzone2100/src/clparse.cpp:663: undefined reference to `flowfield::enable()'
/usr/bin/ld: display3d.o: in function `draw3DScene()':
/home/x/flowfield/warzone2100/src/display3d.cpp:902: undefined reference to `flowfield::debugDraw()'
/usr/bin/ld: fpath.o: in function `fpathDroidRoute(DROID*, int, int, FPATH_MOVETYPE)':
/home/x/flowfield/warzone2100/src/fpath.cpp:453: undefined reference to `flowfield::isEnabled()'
/usr/bin/ld: /home/x/flowfield/warzone2100/src/fpath.cpp:454: undefined reference to `flowfield::getPathFromCache(unsigned int, unsigned int, unsigned int, unsigned int, PROPULSION_TYPE)'
/usr/bin/ld: /home/x/flowfield/warzone2100/src/fpath.cpp:461: undefined reference to `flowfield::portalPathToCoordsPath(std::deque<unsigned int, std::allocator<unsigned int> > const&, DROID*)'
/usr/bin/ld: /home/x/flowfield/warzone2100/src/fpath.cpp:466: undefined reference to `flowfield::calculateFlowFieldsAsync(MOVE_CONTROL*, unsigned int, int, int, int, int, PROPULSION_TYPE, DROID_TYPE, FPATH_MOVETYPE, int, bool, StructureBounds const&)'
/usr/bin/ld: init.o: in function `systemShutdown()':
/home/x/flowfield/warzone2100/src/init.cpp:766: undefined reference to `flowfield::destroy()'
/usr/bin/ld: init.o: in function `stageThreeInitialise()':
/home/x/flowfield/warzone2100/src/init.cpp:1211: undefined reference to `flowfield::init()'
/usr/bin/ld: init.o: in function `stageThreeShutDown()':
/home/x/flowfield/warzone2100/src/init.cpp:1329: undefined reference to `flowfield::destroy()'
collect2: error: ld returned 1 exit status
Edit: Due to some forum software bug, I cannot upload the log file with the linker errors. Visit http://ix.io/1vW6 to view it.
Its name was supposed to be: "flowfield_prototype_autotools_linker_errors.log"
Its description was supposed to be: "output of `make -j6` after executing `./autogen.sh && ./configure CFLAGS='-O2 -gstabs -g -g3 -pipe -Wno-unknown-pragmas' CXXFLAGS='-O2 -gstabs -g -g3 -pipe -Wno-unknown-pragmas'`"

The error message I receive reads as follows:

Code: Select all

General Error
You are not allowed to access this file.

BACKTRACE

FILE: (not given by php)
LINE: (not given by php)
CALL: msg_handler()

FILE: [ROOT]/includes/message_parser.php
LINE: 1873
CALL: trigger_error()

FILE: [ROOT]/posting.php
LINE: 614
CALL: parse_message->get_submitted_attachment_data()
Attachments
flowfield_prototype_autotools_unknown_pragma.log
output of `make -j6` after executing `./autogen.sh && ./configure CFLAGS='-O2 -gstabs -g -g3 -pipe' CXXFLAGS='-O2 -gstabs -g -g3 -pipe'`
(163.97 KiB) Downloaded 2 times

User avatar
Berserk Cyborg
Code contributor
Code contributor
Posts: 641
Joined: 26 Sep 2016, 19:56

Re: Flowfield prototype

Post by Berserk Cyborg » 13 Dec 2018, 23:14

Forgon wrote: After silencing it by adding '-Wno-unknown-pragmas' to CFLAGS and CXXFLAGS, I ran into linker errors:
I think the flowfield.* files are missing in src/Makefile.am. I ran into some errors with the qt elapsed timers so I didn't get a successful compile yet.

Perl99
New user
Posts: 3
Joined: 10 Nov 2018, 20:01

Re: Flowfield prototype

Post by Perl99 » Yesterday, 00:45

Clearly missing from Makefile. I'm sure I have added it because I had linkage errors too. Could be that I haven't committed this file.

That pragma is because MSVC gave me error about nameless struct in GLM, so I had to disable it.
QT elapsed timer is only used for debug, you can safely comment out /remove it.

If you don't want to have debug view, undefine / comment out a flag named "I_AM_FLOW_FIELD_MAINTAINER_AND_WANT_TO_HAVE_MY_VIEW_OBSCURED" in flowfield.h. I haven't yet found a way to move this flag to Makefile with possibility to enable / disable it at build preparation.

pastdue
Code contributor
Code contributor
Posts: 128
Joined: 13 Aug 2017, 17:44

Re: Flowfield prototype

Post by pastdue » Yesterday, 02:41

Going forward, since the CMake build setup should now work on all platforms, I think the focus will be there (and the autotools / Makefile build setup, which is less flexible and more brittle, may end up going away).

Post Reply