Fixing the Movement System

My problem with my movement system was that it did not take detours around obstacles into account.

"Only defeat gives wisdom."

Here’s another example:

Waging wars to shake the poet and the beat

The path up the mountain should be included in the movement range, but how would that be calculated?

And here I was trying to calculate such things, with a brute-force experiment (see post):

I hope it's gonna make you notice someone like me

The brute force approach to include detours in the movement range was inefficient.

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: