Long/Tile Pathfinder Rewrite

[Kieran P]

For continuing Philip's pathfinder work. For the short-range pathfinder rewrite, see #1942.

See the following posts for progress so far:

• http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=80#entry230053
• http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=100#entry230217
• http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=120#entry233181
• http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=140#entry233213
• http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=160#entry233998
• http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=180#entry234910

Also pathfinder.pdf​ for some concepts of the new pathfinder design.

[Kieran P]

From Philip (2012-12-11)

[Jonathan Waller]

Rough merge with svn 13111

[Jonathan Waller]

I did a crude merge with the latest svn. There were some conflicts which were not dealt with properly but it will now compile and run, though the AI breaks and I got an assertion failure while testing.

[Badmadblacksad-]

Another merge (based on quantumstate's patch), using trunk as it was on March 8th.

[yunta]

Apply after pathperf7.

[yunta]

pathperf7_dry1.patch: One function DRY-ied. Otherwise no added value. Not properly tested.

[tuan kuranes]

Would like to give a go there. Applied patch and started looking, and additions are huge indeed. A good start would be imho to make all pathfinding code goes in its own static libs, allowing using a small 2D test/bench test app, easier and faster for coding/testing than compiling and loading the whole app at each test/bench changes. Or is there already one ? (last post with black and white grid and blue path ?)

(single fast 2D apps are very useful, and could be declined/reused for formation, tactical ai like done here ​http://www.cgf-ai.com/products.html#tacastarexplorer )

Could a dedicated forum post be made about current state and next steps ?

[historic_bruno]

I think Philip (Ykkrosh) would have to be the one to summarize the current state of the pathfinder, but I doubt he will have time to do that. You might have better luck if you drop by IRC and try to catch him there.

What I know is:

• It mostly affects the long-range / tile pathfinder, not the short-range / vertex pathfinder. Both have performance issues, this patch is intended to make the pathfinders consistent.
• It's not intended to improve performance. In fact, the new approach uses a higher resolution map and so optimizations like JPS were required to even make it feasible. More optimizations are of course possible but the basic design should be completed first.
• It's much faster in some cases, like testing if a target is unreachable.
• It's much slower in some cases like terrain modification or placing structures, this needs to be optimized.

pathfinder.pdf​ may be a good place to learn about the design, it won't necessarily match the latest patch. Other than that, I would ask Philip in IRC, and you might find a bit more info by searching the ​IRC logs for "pathfinder".