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

Here’s another example:

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):

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:

### Like this:

Like Loading...

*Related*

Got a question: Why use Dijkstra’s algorithm when a basic BFS or DFS traversal through the grid tree would work? Wouldn’t the latter approaches be faster since Dijkstra’s will require a priority queue to determine the shortest routes first, but in this case, there’s no need to prioritise finding shortest route first because there’s no end point destination (you’re just finding all possible directions from the start point)…so just a maximum weight accumulated across all node depths would work just fine in determining when to stop traversing deeper in?

I hadn’t considered BFS or DFS. I was merely using Dijkstra’s because I was dealing with pathfinding. I was just thinking though, if there turned out to be more than one path to reach a node (let’s say there’s obstacles along the way), Dijkstra’s will know the path that takes the least cost. But I’m not sure if that’s really important though. I’m just interested in getting the perimeter of the move range here. So, yeah, probably worth experimenting with later on.

I guess it can kill 2 birds with one stone since you also need to pathfind for yr game in particular (with the mouse cursor target destination) so Dijkstra is useful in yr case.

For a game that i’m considering for myself, i only need the move range since my movement is done Valkyria chronicles/Mordheim style (like a 3rd person shooter), that’s why i was considering just a basic BFS and DFS traversal alone.

Yes, also I made it that for some characters, moving upwards has more cost, so the Dijkstra’s algorithm was useful in this case.

If you make a blog post about your implementation, do share it! I’m curious how BFS/DFS performs in comparison.

In the end, i went with Dijkstra anyway because unless every edge is weighted consistently as “1”, then BFS can be used as a replacement (which is actually the same effect as Dijkstra with equal edged weights). DFS will not traverse the shortest path, and BFS only works for equal edged weights. The lowest cost values at each node gathered via Dijkstra is useful for determining the remaining amount of AP you have left to draw a “2nd boundary” at any given location.

I also noticed your graph arcs seem to only have diagonal edges from North-West to South-East corner. Is this a coincidence or is it because you’re basic your graph arcs uses the actual terrain mesh edge geometry (which involves only a single-direction diagonal fan). This might result in a biased, unfair result, since there’s no 8 directional arcs from a single point? Or are you just grid height sampling graph node points at deeper resolution (interpolating in-between values), so the terrain tile sizes can be of lower resolution?

The pathfinding for the movement range takes all diagonals into account. I have a separate algorithm that collects all the points and makes a shape out of them (i.e. the movement perimeter). That’s the one that’s unfairly favoring North-West to South-East diagonals. Probably something I can fix when I look into this again.

So you consider all 8 directions right from every point, right? Therefore, the NW to SE diagonals appear to be a coincidence/bug? Does the algorithm need every terrain geometry to be as high resolution as 16×16 (32×32 for a human size) just like the fine 16×16 grid or are you sampling interpolated heights over a generic height field?

Yes, the NW to SE diagonals is a bug, although since it happens only when the shape of the movement perimeter is being made, I don’t think it has much impact to the final result.

I’m sampling the heights, raycasting downwards from the top, then collecting all the points in an array. Right now, the way I’m doing it, you could consider it a form of planar mapping, because the problem is at the sides of tall mountains/hills, the distance between the nodes are too far apart. That’s another thing that could do some improvement. Also, obviously, it cannot take multiple floors into account (if a battle were to take place inside a building with many floors).

I think NE to SE diagonals might have to do with how the directional reading bias (top down/left-right) causes such a situation “naturally”. Either way, it’s a small matter and probably not much of a “bug”, more of an “incidentality” which can be overlooked.

I guess raycasting provides the most accruate way, and is least expensive because in this context, it’s just a downward ray/plane intersection. Another more performant way is to simply project an interpolated point along the 2 triangle edges from a given pivot origin vertex assuming you identified the triangle the point lies in.

I think the planar mapping is fine. It’s just that your movement system does not take into account consecutive steep down-slopes, which should probably not allow up to anything ~>=2 to 4 consecutive steep downslopes. as that would be a steep tall cliff that would require some considerable effort/distance even to get down from. …I would consider applying specific “climb down” movement regions like in Mordheim at the “entry-point” of those nodes, because right now the units can hang unrealistically in the middle of steep slopes without gravity causing them to slide down, and those nodes that lie in between ~>=2 to 4x consecutive slopes regions shouldn’t be walkable at all, regardless of whether it’s going upslope or downslope. (note: a downslope is a steep slope in which a unit cannot stably rest on without sliding down). Another way (but perhaps too arcadish) is to actually allow units to fall down such consecutive downslopes but take “falling” damage, causing one’s turn to end if gravity pushes the active unit outside of the movement turn region.

For any upslope, once the height difference between vertices reaches pass certain threshold (therefore considered as a “challenging” slope lower limit), the weight could intepolated between the lower limit to upper “steep” slope limit therefore naturally taking into consideration the “distance” associated with the slope. If it reaches pass the steep slope limit for the upslope, it’s no longer traversible at all except through climbing. I’d rather not go with actual square-root distance between points, because that’s too costly and unnecessary.

For the border-drawing, do you draw use marching squares or something to detect the edge pixels? Do you also detect any inner borders of fully enclosed obstacles/cliffs/no-go regions? If so, how did you do it?

Instead of marching squares, which would yeild inner/outer edge inconsistencies, use IsoContours modification, and it works great!

https://github.com/azrafe7/hxGeomAlgo/blob/master/src/hxGeomAlgo/IsoContours.hx

You can see how it looks like under the CCLabler implemenetation, which also allows detecting labeling inner holes as well seperately.