Opened 11 years ago
Last modified 9 years ago
#1756 closed enhancement
Long/Tile Pathfinder Rewrite — at Version 6
Reported by: | Kieran P | Owned by: | philip |
---|---|---|---|
Priority: | Must Have | Milestone: | Alpha 19 |
Component: | Core engine | Keywords: | patch pathfinding |
Cc: | davidshumway@… | Patch: |
Description (last modified by )
For continuing Philip's pathfinder work.
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.
Change History (10)
by , 11 years ago
Attachment: | pathperf5.patch added |
---|
comment:1 by , 11 years ago
Description: | modified (diff) |
---|
comment:2 by , 11 years ago
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.
by , 11 years ago
Attachment: | pathperf7.patch added |
---|
Another merge (based on quantumstate's patch), using trunk as it was on March 8th.
comment:3 by , 11 years ago
pathperf7_dry1.patch: One function DRY-ied. Otherwise no added value. Not properly tested.
comment:4 by , 11 years ago
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 ?
comment:5 by , 11 years ago
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".
comment:6 by , 11 years ago
Description: | modified (diff) |
---|---|
Summary: | Pathfinder Rewrite (Performance) → Long/Tile Pathfinder Rewrite |
From Philip (2012-12-11)