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.

[Andy ONeill]

The current version of pathing now seems stable.
This is still not really as fast as I'd like though.
Calculating routes can take 2 to 4 seconds which means you can't show the path anywhere near real time and there's a tum-tee-tum delay before that arrow appears on the map.
For a route where you need to go some distance to find a crossing over a river this is  quite noticeable.
That's due to how spatial A* works. It's expanding out and checking costs for every px until it finds one that crosses that river.

In order to make it faster it needs to know in advance what sort of direction is best to head off in.
Don't bother heading straight for the goal, head off over to the bridge.
You will probably have seen the consequences of pathing in other games where you're best looking for a good route yourself and clicking (say) on that bridge as a first step in your route.

There are a few technical approaches we could take to work round this.
What I'm trying at the moment is pre calculation.
This is a process you'd use on a map which (sort of) stores good routes.
The downside of this is it's very time consuming to pre calculate a map.
There are a number of positives though which (likely) greatly outweigh that.
The processing investment in advance will save a lot of memory and processing during a game.
Or at least that is my plan.
Anyone familiar with development or who's been following the changelog will know plans don't always work out like you'd hope.
I have high hopes for this.

What I'm doing might be interesting.
Or might not - I'm kind of biased.

The map works with cells which are 1px sized.
So that map which is 1155 x 805 has a terrain and elevation value per px.
Routes per px to every other px would be way too much to pre calculate and I don't thinks is really necessary.

I'm working at a bit higher level.
A super cell is equivalent to one of those 35px x 35px squares on the map overlay.
This is small enough it's won't often hit complications like which side of cell you choose.
There are 33 x 23 of these.

Pre calculation will be for the central px of each cell to any other. So long as neither of those px is water.
To do that I loop through each cell.
Then for each of those loop through all cells, excluding the same and neighbouring cells (  there's no point pre calculating adjacent super cells).
Run spatial A* for each of these, excluding those already calculated.
Store the supercells crossed from start to goal and the nearest px on the edge of each supercell the route passes through.
The reverse is probably also a good route so long as no px is really steeply uphill that way.
Store that route as well so long as all slope between px are ok.
This is where the excluding already calculated routes comes in.

The reason It takes a lot of time is because 33 x 23 is 759. Although the reverse path thing avoids 759 squared, it's still a LOT of spatial A* pathing to run.

Once the prototype of this is working I can move it into another app. That new app will run rather like a service without UI so the process itself can max out on memory.
I could, technically, build a service does this and containerise it so it can be hosted in the cloud.
Thing is with that, each user would probably have to set up an AWS account to use a free hosting option and this is very techy stuff for consumers.

I'll also allow the game to work without this pre calculation.
All this is on the assumption pre calculation works as well as I'm thinking it will.

[Andy ONeill]

I've built the proof of concept pre calculation mechanism.
This doesn't save anything yet and the structure the data will be saved in will probably be different.
The main idea is to prove I get sensible results.
I can then port the code to a new app.

I have a few ideas floating around about exactly how this will work.

As I explained, this thing will iterate (effectively) through the set of squares you see on a map.
It works out a good route from the centre of each square to the centre of every other square.
It records the route in terms of the squares it passes through.

And to check it's not doing stupid things I plugged this into the map editor and add a spot per square.
Here the start square is the top left one with the white spot.
Blue spots are squares the route passes through and the red spot is the target.



I kind of like this display so the final version might transmit a sample of what it's doing.
The map editor could then pick that up to visualise progress.
I've (obviously) hidden the fancy background here and places so I can see the spots easier.

[Andy ONeill]

I've been beating the bugs out this thing and refining what data I want to capture.
Have to be particularly careful here because the next step will be to port the code into a new app.
This will have no ui.
It will be launched from the map editor and grind the data.
Probably with some settings you choose at launch time.
Details are TBD.
Until I've tried it, i only have a vague idea how long this thing will take to calculate a map.
It's not going to be something you'll want to sit watching though.
This'll take a while to run.