My problem with my movement system was that it did not take detours around obstacles into account.
Here’s another example:
And here I was trying to calculate such things, with a brute-force experiment (see post):
It looks ugly and takes something like 10 seconds to compute.
I realized that to do what I want, I will really have to put a grid in the map. But the idea is that grid will only be used for calculating move range. Characters will still not move by the grid.
So here’s the grid:
So with this, I can run a plethora of algorithms for calculating paths.
Now what I did, was to use Dijkstra’s algorithm without specifying an end goal. So I’m letting it run on all directions, but imposing a limit on how much squares it can go to.
It’s similar to displaying the movement range in square grids of games like this:
It’s sort of like doing a flood-fill. But here I need to take into account the slope of terrain: steeper angles cost more to move. And with Dijkstra’s algorithm, it was easy to put that in.
So what I get is this:
So far there’s nothing really remarkable about this.
But now that I’m using a proper pathfinding algorithm, it will take obstacles into account properly.
For example, this is my movement range in top view. If you add an obstacle (like a building) within the perimeter, the movement range will adapt properly.
My next step was to collect all those points and connect them to each other, forming the perimeter:
Now obviously, it’s looking ugly. The curves are jagged. So the next step was to apply some sort of smoothing to the points’ x,y,z positions.
And then we get this:
Which is quite nice and exactly what I want.
All I’m doing here is a simple average (i.e. mean) filter: for each point, you average its x,y,z position, and that of the point next to it, and the one before it.
Now actually, I’m applying the filter 4 times, to get a good smoothened out look.
For comparison, here’s the top view of the unsmoothed border:
And here it is, smoothed:
And here it is, super-imposed:
It follows the original path fairly well.
And as a nice bonus to all of this: it takes about 0.1 seconds to compute this movement range, so it really is far better than my old code.
As a final comparison, here’s what it looks like before and after: