Support for multicore in pathfinding?

[TradeMark]

Since i have 4 cores,

Would it be possible to make Spring's path calculations support multicores?

Would make the map loadings much more faster.

[AF]

90% of the pathfinder is illegible, almost all of it is undocumented, nobody wants to even look at it for fear of spontaneous combustion, and what little we pretend to know about it is arcane superstition at best.

[Tobi]

Shouldn't be too hard to make it use multiple cores during pathing I think. No priority though, most people have better things to do.

(just calculate the payback time and you'll see it shouldn't have priority => 2 cores average => 1/2 the pathing time, 1000 ppl playing spring (assume all C2D), on say, 5 different maps. Pathing time normally on C2D is like? 10 seconds? That means it'd save 5 seconds * 1000 ppl * 5 maps = only 7 hour available to get to know the pathfinding code, research possible implementations, implement one, test and bugfix it.)

[imbaczek]

yeah, the pathfinder is one of those /* code below is sacred, you must not touch it */ places.

that, and it works, no need to make it faster tbh.

[MadRat]

yeah, the pathfinder is one of those /* code below is sacred, you must not touch it */ places.

that, and it works, no need to make it faster tbh.

The guy that gets it to work on more than a dual core should honestly get the Nobel Peace prize.

[rcdraco]

Have a ball.

https://spring.clan-sy.com/svn/spring/t ... /Sim/Path/

[jcnossen]

My guess is that ObstacleAvoidance in https://spring.clan-sy.com/svn/spring/t ... vetype.cpp
and the similar realtime stuff for aircraft is actually more expensive than the code in Sim/Path (= selecting which precomputed path to use...)
But it should first be properly profiled before anyone starts working on multithreading...

90% of the pathfinder is illegible, almost all of it is undocumented, nobody wants to even look at it for fear of spontaneous combustion, and what little we pretend to know about it is arcane superstition at best.

Sim/Path stuff precomputes ideal paths on the map for moving squares of various sizes (16 and 32). It's really not magic, just everyone has different priorities and the pathfinding code 'just works' well enough. IMO the pathfinder has quite a decent design compared the other old code.

OT: Might be nice to add path precomputing for size 64, so spring can have krogoths and other large stuff that actually works well. I'm not sure if the obstacle avoidance would be able to handle that though..

[MadRat]

jc-

Is that measured by pixels?

[Neddie]

If anybody touches pathfinding, please, insert some documentation. I've lost two potential contributors I was trying to lure in due to the sheer... well, the wall of code effect.

[jcnossen]

Is that measured by pixels?

Pixels have no meaning in a 3d world where you can zoom in..
It's probably in the same dimension that all the units use for positioning etc..

[MadRat]

The only real way to probably improve pathfinding is by introducing yet another map mask layer so that map makers could hardcode optimal places for the units to use. This could be applied post-optimizing in the pre-game (this keeps the current state of the pathfinding code static in this sense) and done during a game on the fly. Perhaps someone could take the premise of the pre-game optimization code, make it run at intervals large enough to not be too hard on the overall system, allow it to see battlefield obstacles as it scans the map anew, and then lays that new view down over the old so it alters how the unit pathfinding is being used. It would be like it really does see and navigate around problem areas when in reality it is only using a freshly provided move map and won't see the problem areas removed until a new scan. Of course the fix would have to always work on processor>0 (or whichever processor the game code is running on) so that it doesn't affect game performance.

[AF]

madrat, that could fall apart as soon as you introduced a second mod with nonidentical slope tolerances.

Especially if the map distorts during game due to gaia units or terraforming.

[MadRat]

Why? All obstacles would be constantly re-computed during the game.

[AF]

And AI wisdom 1,2,and 3 would strongly disagree with you there. Pathfinding is an inherently slow problem, and everywhere you're told to cache the data or put it in the world as prebuilt markers and waypoints. The latter system falls apart when the word terraforming and dynamic terrain appears. And there's a reason the vast majority of all pathfinding calculations are precalculated and cached, or why so much research ahs gone into such solutions as navigation meshes.

I suggest you go read up on pathfinding Madrat before you post again.

[MadRat]

You're not making sense AF. Your preconceived notions are plain silly.

[tombom]

You're not making sense AF. Your preconceived notions are plain silly.

Can you please point out what exactly is silly? Pathfinding is the most expensive operation in RTS games pretty much always.

[Felix the Cat]

Indeed.

I just took a look, and it doesn't appear that the pathfinder is as incomprehensible as everyone says it is. True, there's no comments, and one would probably have to commit a whole afternoon to studying the code in order to really understand it. Probably less if one is familiar with some of the concepts and data structures used by Spring already.

[MadRat]

You're not making sense AF. Your preconceived notions are plain silly.

Can you please point out what exactly is silly? Pathfinding is the most expensive operation in RTS games pretty much always.

This is in the context of AF's argument that recompiling pathfinding during the game would be unworthwhile. Add in the original context of using multiple processors. The processing would then not have to affect gameplay performance other than tying up the related memory bandwidth.

[Peet]

This is in the context of AF's argument that recompiling pathfinding during the game would be unworthwhile. Add in the original context of using multiple processors. The processing would then not have to affect gameplay performance other than tying up the related memory bandwidth.

• Not everyone has a dual-core processor..we don't want to screw over people with slightly outdated hardware (and everyone playing with them who would have to wait twice as long as their own recalculations)
• The memory used during pathing is often up to 800mb (more for bigger maps of course), which in addition to spring's ram usage during gameplay would cause severe swapping for people with less than 2gb of ram or so

[MadRat]

But the purpose of the thread was to talk about what multicores could be tasked with, not the effect it would have if you tried to do the same on a single cpu system.