Calculating RPG radial movement bounds/range

Behavior & Navigation Navigation
1

Hello!

I am a wannabe game developer, 3d art student graduate, diving deep into learning C# programming for just over a year, and am trying to prototype a game idea. I’m having problems figuring out how to calculate a radial range of movement for characters in a turn based RPG. I originally had a projector with the range of movement, but decided I want obstacles to alter the range of movement. I have made several attempts at figuring this out, and while I have a few “solved” methods, no solution has turned out “exactly” how I want it.

In every attempt, I’ve started by calculating points in a circle around the origin point of my character, and I also cast rays from the character to each point and figure out if there is a collision (Those steps seems to be necessary for any or all methods). The next part (the non-stupid easy part) is what I have trouble with.

  1. I tried Unity’s Navigation Mesh, had some success, but the characters’ obstacles’ shapes on the navmesh are squares, when I’d prefer them to be a circles.
  2. I tried a a method in which I found the furthest visible edge of a collider, and casted another circle out of those points with a reduced range based on how far it is from the character, but this yielded so many points, and I’m not sure how to filter points that are already within my range.
  3. I also tried a* pathfinding; This seemed to be what I need, but I possibly just need to understand it better in order to make it work.

Does anyone have any ideas or suggestions to solve this seemingly complex problem?

I found a few references. One is a game called Makai Kingdom; It has radial movement, but there is no obstruction from obstacles/characters/walls/etc. I then found a game that does what I need: Arc the Lad: Twilight of the Spirits. I’d like to email the developer (Cattle Call Games), but I can’t seem to find an email or navigate the (Japanese?) site.

tl;dr
Anyone know how to achieve this?

(sorry for the tiny image, but it’s the best one I could find that shows what I need to achieve)

How to make a ring effect like the Total War Warhammer campaign movement range?
2

Since you’re still fairly new to programming, I think you should consider building your RPG on a grid (either square or hexagonal). There’s a venerable tradition of grid-based RPGs, dating all the way back to Rogue, and including highly successful francises like Diablo.

I realize that today, grids may seem passe… but what you’re wanting to do here, i.e. delineate the area a character can move to with completely arbitrary movement around obstacles, is going to be tricky. Not just for showing (and enforcing) the movement range, but for all the other complications that arbitrary movement brings.

However, if you really want to stick with this, then let’s keep talking. I find this challenge intriguing. I suspect that you’re on the right track with A*, but how best to apply it?

I might try starting with a circle of points in a circle around the actor, at the maximum distance he could move without obstructions. Then, for each of those points, do standard pathfinding to measure the distance of the shortest path to the player. If it’s more than the maximum movement, move that point along the path to the point where it is the proper path distance. Then, make a polygon out of those points, and that’s the region he can move within.

But I don’t think it will be quite that easy; where we have to split two neighboring points apart, they would still be connected by an edge, which would mean the polygon would actually end up overlapping obstacles. There may be ways to fix that, but no easy solution leaps immediately to mind.

Of course you could solve the problem by making a very fine grid, and then simply doing a fill on that grid up to the proper depth (path distance). Then, fit a polygon around the filled grid points, and smooth it out if necessary to hide the fact that a grid was used. But this hardly seems efficient, does it?

I look forward to hearing whether others here know of a standard solution to this problem.

3

JoeStrout, thanks for your reply! I’m planning on sticking with this, so your input is appreciated. I have a few versions of your first suggestion, and it works to an extent. I do want to have obstacles omitted from the “movement mesh,” but haven’t found an easy way. I’ve looked in to subtractive boolean operations, but have had limited time to study that. The fine grid sounds like it would work, but like you said, doesn’t seem efficient.

I’m currently trying a node based pathfinding system where each obstacle has a set of nodes(transforms/gameObjects) that I set up manually. I still calculate my points of a circle and use those points as my bounds if there is no collision. If there is, I use the nodes to find the shortest path to the circle point, and shorten the path based the max length. I am using SphereCast to each of these points to keep the calculation more accurate the shape of my character collider. This method still has the issue of needing to cut out the obstacles from the movement mesh, but I supposed I can tackle that afterwards.

I was suggested by an accomplished app developer to look into fragment shaders for this, i.e. not even deal with a physical mesh, but to use a shader and projector(?) to display the bounds of movement. I have tried to research fragment shader specific stuff, and have written a few simple pixel/vertex shaders, but have a hard time finding help on learning fragment shaders. Also, because career in programming just beginning, the cg language and shader writing in general is currently over my head.

4

Pic of current progress:

1st column is what I have. Blue lines are origin - circle points. Green lines are shortened points based on movement range.
2nd column shows pink points that I need to calculate. Thinking I should cast out points in a circle with a reduced range and somehow get those pink points.
3rd column is what I think the goal shape should be.

5

shameless self bump
I’ve been doing some hacky things to try to solve this problem, so I’m taking a break, and hopefully can solve this with with a less frustrated mind. I had the idea of generating a bunch of circles, and combining the meshes, but that seems like wrong thing to do.

6

I think you’re on the right track, except you don’t want to make and combine meshes; you want to stick with mathematical descriptions of circles or arcs, and combine those.

Then, once you have your combined figure (a series of arcs and straight lines), you can make that into a mesh.

Or, I think maybe you could do it all by ray-casting, something like this, but with a couple of added twists: the rays you cast have a maximum length, and when you get to a corner, you repeat the process from there but with a shorter series of rays. Then you would need to combine the polygons where they overlap.

This is advanced stuff! Have you searched the Asset Store pretty thoroughly to be sure there isn’t a solution in there already?

7

I have searched the web and asset store pretty thoroughly for a solution, and haven’t found what I need. Your suggestion and that link may have just inspired an idea that I think might work! I’ll keep it posted.

8

I think this is the closest I’ve been to solving this thanks to JoeStrout!

I still have to figure out how to get the outermost points/points I need/combine these shapes into one cohesive shape.

(edit) seems like this is what I want. I will see if I can find a way to implement a Boost.Geometry .dll.

9

How’s your progress going? I love Arc the Lad’s combat system and I am considering using a similar system for a game. If I come up with anything worthwhile, I’ll let you know.

10

I made some progress on this, (actually posted this on Unity Answers too). I figured out how to do shape combining, but what I had must not be as robust as I need it because when I combine the last shape (the 4th pac-man shape in the gif), it doesn’t know how to do it. Also, amidst trying to find a solution for that, I did a test to create the pac man shapes on a much more complex scene (end product scenerio), and the calculation of it all (even without the combination of the shapes) was horrifically slow. So, now I’m at a point where I either gotta optimize and rework, or come up with a new idea.

11

HOLY SHIT! I’ve been looking for this! Need this for a game I’m doing!

12

Now if I were to, say, do this, but with an energy system in mind… Your idea on how I would do this?