Question About RPG Movement

Ive been working on a SRPG for a few weeks now. I have pretty advanced code skills, but limited art skills, so generally I’m coding things and buying assets off the store for my prototype.

Anyway, I’ve come to a problem I feel should have a pretty standard answer, and yet I can’t find one. I want to be able to display the limits of how far my character can move (maybe even color code the ranges, like “move 30
Yards, but if you go more than 20 you won’t be able to act afterwards”).

If you’re trying to visualize it, think of Divinity II. Lots of screen shots out there, they basically look like they use some projector or irregularly shaped mesh from the points that the character can move to to display how far you can go.

So far, I’ve been using NavMesh to control the movement of my character, and I can get the path and display it, and the path I show is limited to the max range, but I’d like to show like an area around my guys instead of raycasting every update and drawing the renderer.

I’m close to just picking every point within 360 degrees of my character within the limit, calculating a path to each point (culling path segments beyond move range or the ones that aren’t reachable) then just smashing some borderless translucent shape onto each of those points.

I feel like there HAS to be a better way, but I can’t find it.

 

Bumping. Still trying to solve this.

 

Last time I checked theres no quick way to get that from a navmesh without iterating over it sampling positions, so my sugestion instead of that would be:

TLDR version:
Do A* and get costs of a range of movement, then color those cells based on a cost range.

Long version:
You will need to split your area up into some sort of structure like a grid and then do some sort of A* to work out what is within and outside of the movement cost, and then display only the "cells" that were within movement range. A* algorithm will determine the shortest path which you could also highlight as a different color if you wanted to further guide the player, or you could just determine cells inside area and stop there using that information for coloring the area.

The cells can be as fine grained or as big as you want, so you could have them as big as the player and the movement map will look blocky, or you could have them very small even pixel sized, and in which case you will have to do calculations on a block of cells the shape and size of your players size, in which case you will have a smoother looking range.

There is a number of A* tutorials, my favourite of which is sebastian lagues found here:

So if you follow that you should not only get to a point where you know what you need to solve this problem, but you will also be able to get rid of navmeshes and just do your own pathfinding, which ofcourse opens all sorts of doors not just the one mentioned above.

 

Divinity 2 did not use a navmesh system, they ended up using a grid system so they could solve this problem. You can also see the grid driven nature in the combat.

Divinity 1 was most likely a navmesh driven system, which is why they couldn't display movement radius.

I don't think it's practical to use a generic navmesh to display these types of limits, you either need some kind of custom hybrid navmesh or some very very use case specific logic with very specific constraints on the environment in order to calculate out movement radius with a navmesh system.

Generally though, what you really want to do for this is use a grid system and with an smoothed overlay mesh representing the area you can move to. Not a navmesh system.

 

We've did something similar for the isometric RPG demo inspired by Divinity.

It was based on the Unity's navmesh system.

How to restrict - we went for those restrictions to be based on the amount of action points, that were converted to the Unity's native units. (e.g. 1 to 1m)

And it worked quite well. OP just needs to calculate distance based on the path points and convert it to the some kind of abstraction.

As for the grid, you can form that around the controlled entity on the same base rule set. Just create grid based on the distance, and discard unreachable nodes.

 

In order to use navmesh for this though, you would need to sample the navmesh for every grid point in order to generate the potential move radius.

In which case, you're slower than just using a grid.

Grid also actually guarantees shortest pathing, navmesh will generate degenerate paths sometimes.

 

It is. That's why it was just a demo. But it was fine for even outdated PC to handle.

It would still work out with something like A* Pathfinding Project's navmesh / raycast mesh on the mobile I think.
(its way faster and has pre-cached values)

Grids are great (when you got time to implement them)

As a two week project, we didn't unfortunately

 

Also forgot, we just used a sphere with shader to draw out intersection / radius based on AP / unit distance.

Then, when the mouse is hovered over movable / unmovable location, distance / availability of the location we're sampled via navmesh api, like each 0.5 second.

So I guess that's why it wasn't that processing heavy.
As long as you don't need a grid 1 to 1 to display, you don't need to implement that sampling.

I'm pretty sure first Original Sin did something very similar to this. Albeit, I don't know the details of how they did it.

 

That is what I have suggested to OP above, with A* being used to calculate the grid costs. Should get them on the right track

 

Yeah - ideally you want to use Djsktras algo for this, which is really related to A* but more appropriate for the 'find walkable area' thing.

 

I usually use Dijkstra's for voronoi based pathfinding but yeah Dijkstra's would work here too!

 

Thank you, everyone, for the suggestions. I was hoping there would be some kind of quick fix for this, but I suppose there it is. Currently, I’m drawing a line to the cursor that is limited to their maximum movement range, since I’m solo at the moment and rushing to get something demoable, I’ll likely keep that until I can experiment with the grid. I think it looks cleaner to display the area, but choices, right? I’ll circle back to this when I have something to show for it.

 

The easy way to do this is to approach similar to DoS1 and just display the pathing info without displaying the movement radius.

I did this for earlier project and it worked well (although again, navmesh can generate degenerate paths at times and I could never find a fix for this without custom path generation).

You basically just sample the navmesh under cursor and then draw a spline over the returned path. Magnitude of path / meter per move point is your cost. You round up the costs for display while tracking remaining movement points as a float (to the player it looks like whole move points, but you track fractionally)

 

I also do think that grids have their inherant advantages in many aspects... even if it means manually having to post-processs a navmesh with a fine grid or overlay a fine grid on demand.

It has been done before somewhat. Here's some of my thoughts on the matter on how to do it "proper" if you really feel it's worth it.
https://gingkoapp.com/how-to-navmesh-movement-range

Honestly, if i'm going to try this out, it's more of an academic exercise. But this is something i thought off just offhand and there might be a loophole in certain assumptions i made.

(eg. shortest "straight" line path" may not necessarily be the shortest path to polygon if it passes through varying gradients... etc.), since such a path is no longer considered straight anymore in a 3D sense. Perhaps, those paths would still need a navmesh pathfinding query (which isn't 100% accruate to begin with) in finding the absolute shortest path.

Or like, a ridgeline portal edge issue. If the portal edge leads to a polygon that is non-coplanar to the surface from a previous junction you were standing on. it would mean the "last junction origin" has to be measured on the polygon edge intersection itself (the ridgeline), and not on that earlier mentioned junction spot leading to up to closest edge on target polygon. But then, you'd have an issue with the projected arc only being projected off a radius off the remaining distance from that actual "last junction origin", and wouldn't cover all possible movement along the full arc for the target polygon across the entire every possible junctiion point on the edge of the target polygon. So, how to get the full coverage off multiple junction arcs? The only way is to brute force raycast on every resolution/pixel unit of the ridgeline (ie. every resolution/pixel unit on the ridgeline is a potential junction) to originate an accruate arc distance measurement across the entire ridgeline? But that is way too heavy and detracts from the approach with pure navmesh (gridless) meant to avoid resolution dependance.

If i'm not wrong, this may not be necessary though. Maybe it should be just projection of the arc from 1 plane of the neighboring polygon (of the previous junction) to the other plane of the target polygon.

I mean, the system is easy to implemented if everything is flat on a coplanar plane (as done before by others). But once you could include non-coplanar navmesh regions in 3D, things get a bit more tricky.

 

Grid based with A* is definitively easier, but you can do this on a navmesh using Theta*.