Author Topic: Pathing speed  (Read 284 times)

0 Members and 1 Guest are viewing this topic.

Offline Andy ONeill

  • Moderator
  • Viking
  • *****
  • Posts: 489
Pathing speed
« on: February 08, 2021, 12:21:15 PM »
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.

Offline Andy ONeill

  • Moderator
  • Viking
  • *****
  • Posts: 489
Re: Pathing speed
« Reply #1 on: February 14, 2021, 04:13:01 AM »
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.

Offline Andy ONeill

  • Moderator
  • Viking
  • *****
  • Posts: 489
Re: Pathing speed
« Reply #2 on: February 21, 2021, 05:21:37 AM »
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.