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:



Gridless Map 1

When I was still working for Red Pumpkin, my boss wanted to make a Final Fantasy Tactics style of game.

It came to a point where they were deciding between a square or hex grid for the map.

I immediately suggested a gridless system where units move like in an RTS. They didn’t like the idea at the time though.

That suggestion of mine came from me playing this old 1997 game called Return to Krondor. An RPG game where they don’t make use of a grid for movement.

The gridless map system in Return To Krondor was very simple.

Recent videogames that do this include the soon to release indie game Skulls of the Shogun, the 2007 portable console game Warhammer 40,000: Squad Command, and the console game, Phantom Brave, first released on the PS2 on 2004.

The circle surrounding the unit determines the area that he can move to.

Each green arrow consumes one Action Point for this Space Marine. However, movement is not confined to a grid, so the direction of movement can be at any angle.

The red border indicates the perimeter of how far the unit can move in this one turn.

So across indie and AAA, East and West, Console and PC, if done properly, the idea of gridless movement has been proven to work. Continue reading