Feedback on QTPFPS pathing

[Godde]

Tested in both 85 and latest develop 148 with Spring 1944.

This is like non-cardinal pathing. :D
And it makes units able to use small paths much more easily.

However when you draw a line draw command all units in the same square will use the same path to the square they are going to.




Infantry will sometimes make a circle when they are moving and you give them a new command. This could be because of the delay between when movement starts and pathing kicks in, if it is as it looks. Tanks are not affected. Could be because they aim further ahead with their next "waypoint" I guess.

[Kloot]

Thanks, http://springrts.com/dl/buildbot/defaul ... 34ee76.exe has a few tweaks.

[Google_Frog]

I tested briefly with ZK and 85.0. There armpw almost always reproduces the circling when the move command is given.

Aside from that it was looking good.

[Godde]

In 208 when drawing line commands units will use different paths when going from 1 square to the next square.

Small groups of infantry doesn't make circles when they are moving and you give them new commands.
However when you got large groups, some of them usually make a circle. This could propably be because the pathing is done for some of them at a time groups rather than all at the same time if I interpret it correctly.

Units start to move directly at their destination before they start following their pathing. The delay between the order given and the last units of a group getting a path can mean they move into a cliff for example.

When the unit, both tanks and infantry, have been driven into a cliff they seem to stand still if their destination is behind the close by terrain.

The tank will not move.




The tank is inside a red square caused by small features, tankobstacles, unable to move out unless you spam commands to it. No pathing is drawn from the tank. So it might not be the same thing as when the unit is right next to a cliff trying to move ontop of it like the previous picture.

Some thing that happens with regular pathing aswell:
Units with high speed, low turnRate and high turnInPlaceSpeedLimit will have trouble pathing through zigzag path but that happens with regular pathing aswell. Units that drive backwards will ignore turnInplaceSpeedLimit and move their next "waypoint" way to far away to avoid obstacles and drive into them.
If "waypoints" wouldn't be so moved away so far it wouldn't be that much trouble i guess. I think it initially were put into place to avoid "snaking".

[Google_Frog]

Here is a case of a lone unit that is stuck on the terrain while trying to navigate a steep walled passage.

85.0.1-215-g57692f0
ZK 5382

[Kloot]

http://springrts.com/dl/buildbot/defaul ... 40ff3b.exe again contains some fixes.

Here is a case of a lone unit that is stuck on the terrain while trying to navigate a steep walled passage.

85.0.1-215-g57692f0
ZK 5382

I don't even know if that should be considered a fair test, but g040ff3b has few(er) problems with it.

This could propably be because the pathing is done for some of them at a time groups rather than all at the same time if I interpret it correctly.

Yes, only a limited number of path-requests are executed per frame per team per unit-type, the rest get queued.

Units that drive backwards will ignore turnInplaceSpeedLimit and move their next "waypoint" way to far away to avoid obstacles and drive into them.

It is obeyed in reverse as well, but only if maxReverseVelocity > turnInplaceSpeedLimit.

Units with high speed, low turnRate and high turnInPlaceSpeedLimit will have trouble pathing through zigzag path but that happens with regular pathing aswell.

If "waypoints" wouldn't be so moved away so far it wouldn't be that much trouble i guess. I think it initially were put into place to avoid "snaking".

Yes.

If waypoints weren't moved (skipped, actually), such units would just start driving in circles around them. It is a direct consequence of the movement code's constraint to always stay above turnInPlaceSpeedLimit, and can only be solved with more lookahead and overriding the limit when necessary.

[Google_Frog]

217 fixes it a bit but I still had a commander stuck forever in my first test. Things with lower turn rate such as construction hovercraft (corch) are very likely to get stuck forever. I think it is an important test case for 2 reasons:
1. It is possible to get stuck on the walls of terrain in other situations, the passageway is an easy test for this.
2. The passageway can be completed with the previous pathfinding system even with hovercraft. QTPFS would be a regression.

QTPFS is better at avoiding the side of the passage but is hopeless at unsticking units when they become stuck. If you watch the old pathfinder with a hovercraft on a passage the hovercraft will become stuck often. After a second the hovercraft will then do a little turn to unstick itself.

The important thing is that the unit eventually reaches it's destination whereas with QTPFS I would have to occasionally babysit units off walls.

It is obeyed in reverse as well, but only if maxReverseVelocity > turnInplaceSpeedLimit.

In that case it should be obeyed as if turnInplaceSpeedLimit = maxReverseVelocity.

QTPFS has much smoother pathfinding so we may be able to lower turnInplaceSpeedLimit. turnInplaceSpeedLimit = maxVelocity because the old pathfinder gives units 45 degree turns over flat terrain which would slow units down too much if they were allowed to slow down.

[Godde]

Units with high speed, low turnRate and high turnInPlaceSpeedLimit will have trouble pathing through zigzag path but that happens with regular pathing aswell.

If "waypoints" wouldn't be so moved away so far it wouldn't be that much trouble i guess. I think it initially were put into place to avoid "snaking".

Yes.

If waypoints weren't moved (skipped, actually), such units would just start driving in circles around them. It is a direct consequence of the movement code's constraint to always stay above turnInPlaceSpeedLimit, and can only be solved with more lookahead and overriding the limit when necessary.

Waypoints are moved way too far ahead when the unit is turning. It seems that waypoints are only moved when the unit is turning which makes them path better in general.
You can see the turn radius that the unit have when it is moving at full speed by the tracks on the ground.

The unit isn't even facing the direction of the waypoints and its still skipping waypoints. The unit can drive in the opposite direction of the waypoints and they will still be moved further "ahead".


The unit is still turning so it keeps skipping waypoints beyond the obstacles.


The unit keeps skipping waypoints way behind the obstacles and bounce off them. Even when a new command is given the waypoints are skipped so far ahead that the unit will keep driving into the obstacles.

I advocate that waypoints shouldn't be skipped so far ahead and that they shouldn't be skipped at all if they are above 90 degrees on the sides of the unit in the direction of movement. If the unit is driving in reverse the same should apply.

[Godde]

It seems as if small features cause too much path blocking.

Large buildings and features don't seem to cause this. Could the unit be set up the wrong way or have s44 set up a special rule for tankobstacles?

The tank on the picture can't path out on its own. You can get it lose by spamming commands or giving commands closely.
Now that units can path from a red square to an adjecent green or red square the unit doesn't get stuck that easily in my testing. If tanktraps didn't have so big pathing blocking the tank might not get pathing blocked at all.

[Godde]

F2 view doesn't show where units can go.

When I have debug view and /cheat on it lags alot of me when I zoom out. Propably because of all the squares that has to be drawn.

[Kloot]

Waypoints are moved way too far ahead when the unit is turning.

They are moved only as far as required, specifically a unit will skip waypoints when they lie anywhere inside the turning circle derived from its turn-rate and current speed. Neither this nor the older logic is a panacea.

The unit isn't even facing the direction of the waypoints and its still skipping waypoints

Because direction is not what matters, distance is.

The unit keeps skipping waypoints way behind the obstacles and bounce off them

Ramming obstacles would (and did) happen even if waypoints were never skipped at all, simply because low-turnrate/high-speed units cannot follow every possible path without deviating from it unless allowed to slow down arbitrarily far below turnInPlaceSpeedLimit at any point (instead of skipping ahead). Some new path-following code I have lined up for after 86.0 will do this.

Even when a new command is given the waypoints are skipped so far ahead that the unit will keep driving into the obstacles

This is solved for 86.0 by letting units ask for new paths.

I advocate that waypoints shouldn't be skipped so far ahead and that they shouldn't be skipped at all if they are above 90 degrees on the sides of the unit in the direction of movement

You might remember what the result of that would be (point #2). I am also willing to make a special test build for you with those changes and any others you think are an improvement if you aren't convinced.


TLDR: when units did not skip waypoints they were ramming into obstacles and forever orbiting around/snaking between waypoints, now they do skip waypoints and "only" ram into obstacles.

Could the unit be set up the wrong way or have s44 set up a special rule for tankobstacles?

How is that tanktrap's yardmap defined?

F2 view doesn't show where units can go.

It's not implemented yet.

Propably because of all the squares that has to be drawn.

Actually more because of all the text, though the squares don't help.

[yuritch]

How is that tanktrap's yardmap defined?

It's a 1x1 feature, like so:

Code: Select all

[tankobstacle] {
  collisionVolumeType=ellipsoid;
  collisionVolumeScales=5 5 5;
  collisionVolumeOffsets=0 0 0;
  description=Tank Obstacle;
  damage=2500;
  energy=25;
  featureDead=Debris_Small;
  footprintX=1;
  footprintZ=1;
  object=TankObstacle.S3O;
  reclaimable=1;
}

[Forboding Angel]

The hitsphere (if too large) might be causing unseen issues.

[Kloot]

It's a 1x1 feature

Then the tank in Godde's screenshot has to be at least 2x2 (pre-scaling). The reason more squares are blocked is that obstacles are expanded by half the size of each MoveDef footprint (post-scaling), and a "QTPFS square" has a minimum size of 2x2 heightmap squares which is equal to a 1x1 (pre-scaling) UnitDef/FeatureDef footprint.

I am also willing to make a special test build for you with those changes and any others you think are an improvement if you aren't convinced.

Done, you now have a temporary branch named after you. This is your chance to evaluate your ideas live instead of just on e-paper: you present them to me, I translate them to code. Installers are here, latest at time of writing is this one. Be sure to test both pathfinders with a variety of different maps and units, and keep in mind anyone can always verify your findings. GLHF, and if no feedback for more than a few weeks then GGNORE ktxbai.

[Godde]

Nice!

[Godde]

I advocate that waypoints shouldn't be skipped so far ahead and that they shouldn't be skipped at all if they are above 90 degrees on the sides of the unit in the direction of movement

You got it backwards of what I intended. Now when the waypoints are behind the unit it will skip them.

Even when a new command is given the waypoints are skipped so far ahead that the unit will keep driving into the obstacles

This is solved for 86.0 by letting units ask for new paths.

The pathing is really alot better when going zigzag between walls of obstacles. I don't know if this is mostly due to units asking for new paths or if it is mostly because they don't skip waypoints at all.
Sometimes when they collide into the obstacles they can't path out from there with QTFPS pathing on.

They do snake alot however. My intention was that they should skip waypoints abit but far less than before if the next waypoint is within 180 degrees in the direction of motion.

I fear that I might be asked to code it myself...*gulp.

[Kloot]

You got it backwards of what I intended

That can be fixed, but it shows why you should not use natural language to communicate code ideas (they just get misinterpreted), as well as why

I fear that I might be asked to code it myself...*gulp.

you need to be more precise and complete if you want this experiment to work. "they should skip abit but far less than before" is neither, give a mathematical description (which should not be so hard for someone who has studied all facets of the problem...) of the exact set of conditions under which a waypoint should be skipped and I will take it from there.

[Godde]

Yeah... True.

So... this idea then.
When the unit is moving straight, not turning. It shouldn't skip waypoints like in 85(it propably skip waypoints abit but not much I guess).
When the unit is turning it should skip waypoints if the waypoints are within 180 degrees in the direction of movement.
Waypoints should be skipped when they are within 1.1 times the turn radius of the current speed. When the speed increases so does turn radius.http://en.wikipedia.org/wiki/Turn_radius
So a unit can max skip Waypoints that are within 1.1 turn radius range.

[Kloot]

new installer (with thanks to abma)

[Godde]

Now it doesn't skip waypoints at all when driving straight which cause them to go back and forth on the spot if they can drive backwards or making a circle everytime it passed its waypoint.

Tanks can drive through eachother in S44. In ZK they cannot. How do you make them bounce off eachother?