Pathing speed

[Andy ONeill]

Recently, we noticed that the speed of pathing is quite variable from one map to another.
I was using a map had a fair few roads on it for my testing.
Didn't always seem instant but was fast enough.
I thought.
Ezra tried a different map...
And
There's a problem.

I'm investigating how best to do pathing so it runs at an acceptable speed.
I'm going to try a relatively simple approach first.
If that's good then we go with it.
If that's not so good then we'll have to see about a different and more sophisticated approach.
Turns out optimised spatial A* stuff is tricky.
Especially when the cost per cell varies.

[Andy ONeill]

I've redone A* pathing based on a different implementation.
This runs faster.
Which is good.
This version comes with a very high memory overhead and occasional error.
Which is not so good.

I need to resolve the cause of the error.
Which could be the memory use.
Reducing memory overhead would be good anyhow.

[Andy ONeill]

This new version is still not as fast as I would like.
And there is the teeny tiny matter of instability.
That means more refinement is required.

I've built a set of automated unit tests.
These allow me to load a map, run pathing for a known set of from and to points.
And see how long each takes.
I do this for several different maps and I have a repeatable benchmark mechanism.
Speed isn't everything.
So I also need to manually run some checks to ensure the paths given are still good paths.

Tweak things.
See what difference that makes.
Repeat.
EG are double types faster than float in this piece of code.
( No ).
Not a lot of fun doing this and even less interesting to read about.
I'll post more when I have something more digestible.