Pathing algorithms

[jK]

before you waste more time on crap stuff, here a somewhat old profile:

iirc it was done with a debris repathing bug that caused massive amount of repathing when enemy units rushed through solar & windgen fields (which is fixed since a while now)
Still it gives a good example where the Pather spends time in when calculating paths.

[pear]

Thanks for the profile. Three noteworthy numbers:
- 61% in CPathManager::MedRes2MaxRes (and its callees)
- 10% CMoveMath::GetPosSpeedMod
- 16% CMoveMath::SquareIsBlocked

I wonder if caching these CMoveMath results would improve performance. These computations are fairly simple but there are some loops and stuff: https://github.com/spring/spring/blob/d ... veMath.cpp .

[scrotum]

QTPFS is pretty nice, but it has two fatal flaws that prevent its use right now:

- Hideous RAM usage on larger maps, easily exceeding gigabytes.
- Quite noticeable lag between when unit receives move order and whe it actually starts moving. Spamclicking a unit to move move move to some location where you need it like right now just causes it to freeze in place, as each click resets the path-calculation delay.

ps. high pear, I didn't realize you were a dev. Thought you were a noob learning to play. Street cred ++

If you guys think this pathfinding method is the right one to pursue, let me encourage you in it. If the problem is lag preventing the unit from moving initially, then program the unit to move in the direction of the mouse pointer until computations have completed.

Not only 90% of the time is that arbitrary direction the right path to go, but as someone whos played spring for about 6 years one of the skills we developed is to first send the unit walking roughly in the right direction if we are on the wrong view and focused on another thing at the moment.

This is usually done when timing is critical ingame. We gamers would understand if a unit moves directly towards its target initially and then after a few seconds decides it went in the wrong direction. This is perfectly acceptable given 90% of the time that initial guess is 90% correct.

90% of the time our complaint is related to units not being able to pass territory at all regardless of the amount of time they sit there thinking about it.

CPU lag is a major issue and needs to be addressed. I wish maybe devs would find a very simple rough way to compute it because the MT version of spring crashes.

thanks

[regic]

Where is the function that checks the UnitDef against the terrain to know if a given square is passable? I see only the checks against obstacles (in CMoveMath)

[regic]

I think I figured it out...

The "terrain check" is done with the GetPosSpeedMod function, if it returns 0, then the square is not passable.

This gives me an idea:
The only difference between unit's check against terrain is the max slope a unit can pass. This means you can sort the units by their maxSlope property, and create a navigation mesh for the unit with the smallest maxSlope. You can be sure that every unit can pass those tiles (squares). If you go from the unit with the smallest maxSlope to the highest, the next mesh is always an extension to the previous one: the unit with higher maxSlope can pass the tiles which the previous unit could. (I'm not sure where the size comes into the picture tho.). So you don't really have to store every mesh alone, and most of the unit's mesh will be only some squares added to the previous one. This could allow us the precache pathfinding data.

Building and terraforming is not a problem either, because the modifications to the mesh are obvious, you (or me) just have to create operators that handle these in the right way. Nasty, but can be automatically debugged (mesh + operator = regenerated mesh).

There are still two things must be considered:
1.) How is the unit size alters this? Does it merely define a larger area of squares to be checked one by one?
2.) Can maxSlope be changed during the game? It would make things even more complicated.

I would really appreciate feedbacks from someone who knows more about the engine.

[Kloot]

The only difference between unit's check against terrain is the max slope a unit can pass.

Incorrect, there is also a depth restriction.

Furthermore the passability function is not simply binary, units *change speed* going up- or downhill or through water by a variable amount (depending on MoveDef parameters) which influences the definition of "shortest path".

This means you can sort the units by their maxSlope property, and create a navigation mesh for the unit with the smallest maxSlope.

Even if you could do this it would be a *bad* idea to restrict unit movement to the least-tolerant case given the wide range of tolerance values (practically from flat ground to all-terrain) in the majority of Spring games.

How is the unit size alters this? Does it merely define a larger area of squares to be checked one by one?

Size matters for checks against obstacles.

[regic]

Thank you for the answer!

Even if you could do this it would be a *bad* idea to restrict unit movement to the least-tolerant case given the wide range of tolerance values (practically from flat ground to all-terrain) in the majority of Spring games.

What I suggest doesn't change the rules of movement by a little bit. I want to use the least-tolerant mesh as a base mesh and extend it for the next least maxSlope, and extend that for the next least maxSlope, etc... It is merely to avoid creating separate meshes for every MoveDef - for a given unit, I would only store the tiles it can pass but the previous one can't (which is the previous in the list of units sorted by maxSlope, incrementing order).

Incorrect, there is also a depth restriction.

I decided to ignore that for the time being, but will have to take it in consideration as well eventually. I think I could handle depth in the same way.

[regic]

Furthermore the passability function is not simply binary, units *change speed* going up- or downhill or through water by a variable amount (depending on MoveDef parameters) which influences the definition of "shortest path".

Yes, I realized that, but atm I only want to know if this little idea of mine is viable at all. If not, such details are unimportant, if yes, I still have dozens of little problems to think about before I could even start creating such pathfinding system.

[regic]

I think I should clarify my idea a little in order you can effectively reflect on it.

I do not plan to cache routes, only passable tiles, so checks against terrain and obstacles don't have to be made on-the-fly. (I'm not even sure if that's not how the pfs works right now, I'm still learning your code.)

[Kloot]

I want to use the least-tolerant mesh as a base mesh and extend it for the next least maxSlope, and extend that for the next least maxSlope, etc... It is merely to avoid creating separate meshes for every MoveDef - for a given unit, I would only store the tiles it can pass but the previous one can't

I do not plan to cache routes, only passable tiles, so checks against terrain and obstacles don't have to be made on-the-fly.

Such a representation might save memory but would preclude random access to tiles. If you wanted to find a path for the MoveDef last (or generally higher up) in the ordering that would then effectively necessitate calculating the union of the base and every intermediate diffset at runtime. Have you considered this?

Also, while it of course is possible (in principle) to store a base set of passable tiles and let the pathfinder explore just those, you now have another problem: if this set changes (which it can many times per frame) all the diffsets derived from it need to change as well. What are your expectations for performance compared to the current on-the-fly strategy?

[regic]

Edit: where I wrote unit I really meant the UnitDef of the given unit. I only store UnitDefs in the sorted list.

Ah I realized I'm stupid. I just have to store an integer number per each tile, lets call it n. n means the unit with position smaller then n in the list (sorted by maxSlope property, incrementing order) can't pass that tile while the unit with position n can (thus units with position bigger then n can as well). If n is bigger then the number of units, then no units can pass that tile. Simple, random accessed and shouldn't be hard to maintain consistency. Will do it asap.