Question on PathGraph max size

Aug 26, 2012 at 10:32 AM

Ive been playing around with pathfinding on engine nine and ive come across an issue when i try to increase the grid size of the pathgraph. The 1.2 demos use a 64x64 grid count, however if i try to increase this to say 128x128 the path search fails after a few searches and always returns no path. Is 64x64 the maximum resolution that the search can support or am I missing something?

Also I was just curious if you plan on adding more features to the navigation project or if you consider it feature complete as it stands now? There are a few modifications I would like to add for a hobby project but might hold off if you plan to add more features in the future.

i just want to add that I think you guys have done a great job with this engine so far and look forward to seeing it evolve in the future.


Aug 26, 2012 at 2:25 PM

I haven't touch that piece of code for some time, but the path grid doesn't have a limit. I guess the problem might be caused by wrong picked positions. I'm on vacation at the moment so you have to figure it out on your :(

What kind of modifications are you aiming? I won't change the navigation project in the upcoming 1.4 release, so if you'd like to add some enhancement and hopefully evolve the engine, I'll be more than glad to accept.

Aug 27, 2012 at 4:28 AM

Ok well if there is no limit imposed on the grid size I might dig a little deeper and try and figure out what is wrong. If I work it out I'll let you know.

I'm interested in adding in clearance based hierarchical path finding similar to what is outlined here - Since I want to use it for formation based movement I might even change it to allow the clearance values to modify the costs of tiles rather then completely restrict them if all units are small enough. I could then simply change the shape of the formation while moving based on which tile the leader is currently moving on. This would require some major changes to the path code as well as tweaks to the steering behaviours.

I'm still a bit of novice game developer (I work as a web developer professionally) so I'm not sure if this will be achievable but if I get something working I would be happy to share whatever I come up with.

Nov 1, 2012 at 2:52 PM

I managed to track down the issue with the large grid search. The (SAFE) FastClear extension method had a constant BlockSize of 4096 which is only large enough for a 64x64 grid. Anything bigger and the data gets corrupted after additional search calls. I just modified the method to accept a capacity which I store when initialising the queue and it seems to work fine now.

Nov 2, 2012 at 5:09 AM

Hi plebon,

Thanks for the fix !!! It turns out that FastClear is actually slower then Array.Clear. You can just use Array.Clear(Index, 0, Index.Length); inside PriorityQueue.Clear method. I've included the fix in my local source repro.