Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Radial movement range mesh for a gridless TBS game.

Discussion in 'Scripting' started by MythrilMan51, Apr 11, 2020.

  1. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    It's been done before, like what you would see in Mind Over Mushroom, but you don't usually see them show their codes. I would want to generate a mesh that would show how far you could go for a gridless turn based strategy game.

    Anyone got any ideas how to pull it off?



     

    Attached Files:

  2. Yoreki

    Yoreki

    Joined:
    Apr 10, 2019
    Posts:
    2,605
    It's basically a circle. There are two parts to it. Allowing movement, and visualizing the circle.

    To allow movement, simply check if the raycast of the mouse on the terrain is inside of some radius, and not on obstacles. To draw the circle, use a shader. You can draw a circle around the player rather simply. You'll then only need to somehow exclude the obstacles from the drawn area, and visualize the path to the current clicked position (if you are going for that).
     
  3. PraetorBlue

    PraetorBlue

    Joined:
    Dec 13, 2012
    Posts:
    7,890
    I don't have a simple answer for you, but assuming you want something with obstacle detection rather than a simple circle with radius of moveSpeed, I would start with learning about Unity's Navigation and Pathfinding system (Navmeshes, Navmesh agents etc) https://docs.unity3d.com/Manual/Navigation.html. This will probably get you about halfway there :)

    NavMesh/NavMeshAgent will let you answer questions like "What is the cost (distance) to get from point A to point B?" taking into account obstacles etc. It will also let you animate the character moving from point A to point B properly when the character does move.

    You probably want to combine that somehow with a custom vertex shader that can essentially query a NavMesh and draw based on whether a certain point is within movement range of your character (cost < movement range).
     
  4. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    The movement and visualization parts're not what I having problems with. I'm more talking about the obstacle detection part of things, as if this mesh curves as it goes around obstacles. As you see in these examples, it would be a circle, but it's malformed because of the obstacles in the way, as if a grid less flood fill.

    Also, I was thinking a vertex shader, for sure, opacity telling how much energy it would take to get to that point.
     
  5. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    Yes, that's a tricky problem. I wonder if it's using a 2D Visibility algorithm. But where you detect an obstacle within the movement range, you need to do another 2D visibility test from there, with a smaller limit to account for how far it took to get to that point. Repeat until you don't hit any obstacles (that you haven't already hit before) within the remaining movement range. And finally, union all the resulting polygons.
     
  6. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    That could be something. I right now hacked Sebby’s sight tutorial to see how I could detect obbies in a given scene. Perpendicular points and limiting the angle of this new radius is still a mystery to look up.
     
  7. Yoreki

    Yoreki

    Joined:
    Apr 10, 2019
    Posts:
    2,605
    Maybe i didnt get my point along very well, but there is only 'movement and visualization' involved here.
    When you click somewhere, you move there if the clicked position is inside some radius around the player and not inside the collider of some object tagged with 'Obstacle'.
    To visualize the same thing, you draw a circle around the player (optionally using some texture as the images above), but do not draw this texture for any pixels that are inside one of the obstacle colliders. For this you should keep and update a list of obstacles around the player inside its move radius. You can either do this in a shader each frame (if performance doesnt suffer) or generate a texture as described above once and then overlay it on your ground as a decal.

    If you are already using a NavMesh, it may also be worth looking into visualizing it, since that would effectively be exactly what you are looking for (obviously, fading the visualization out after the radius).
     
  8. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    No. That's not what the illustrations at the top of the thread show, and I don't think it's what the OP is asking for.

    If your total movement distance is 10, but there's a big obstacle in the way, you can't move to a spot 10 units away from you on the other side of that obstacle, as your approach above would allow. You lose some distance detouring around the obstacle. So the area you can reach is not a circle in such cases; it's an odd shape, and how to compute that shape is the subject of this thread.
     
  9. Xiromtz

    Xiromtz

    Joined:
    Feb 1, 2015
    Posts:
    65
    This is definetely a topic you would need to do some research into.
    A great article to start on:
    https://www.gamasutra.com/view/feature/3317/smart_move_intelligent?print=1

    You should have a look at the terms Influence maps, Potential Fields and Avoidance Mapping
    I believe you might get the results you're looking for with influence maps

    I don't have much experience implementing these kinds of specifics, but what you're looking for probably includes the calculation of convex polygons and complicated stuff like that. Maybe you should look at an easier implementation first?
    From a difficulty perspective, easiest to hardest:
    Square Tile grid -> Hexagonal Map -> Convex polygons

    On the other hand, if you're not too keen on researching a lot (though it will definetely be helpful either way), you might be able to leverage Unity Navmeshes for your purposes.

    Additionally, you can have a look at the more popular Astar Pathfinding plugin you can get on the asset store:
    https://arongranberg.com/astar/

    This has a looot of features and maybe something that might help you.
     
  10. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    What Joe Strout said.
    I know he was trying to help another guy with the same type of project.
     
  11. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    And I can tell you now, @JoeStrout, I can at least breath a sigh of relief the maps'll be in 2D. Elevation would more tell if you're out of the fight or not.
     
  12. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    Wall tracking can be a key to pulling this off, too. Detecting hits is one thing, but seeing any other corners nearby would elude me, especially if I want to make this mesh generation efficient.
     
  13. Yoreki

    Yoreki

    Joined:
    Apr 10, 2019
    Posts:
    2,605
    You are right. The difference in shape is quite miniscule in the second image, so i didnt notice that it's not really a circle. It's a bit easier to see at the first image, but anyways yeah you are right on that. My bad.
     
  14. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    At least we're on the same page, @Yoreki. Actual movement would be easy, but generating the actual malformed mesh is more what I'm trying to find out how to do that. A lot of visibility checks could be the key... If I find how to identify all the vertices for a given wall that is vacant.... and the angle of this new check.
     
  15. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    I think I have a heading on that one. NavMesh.CalculateTriangulation() to get the points. NEXT would be to malform the circle from it.
     
  16. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    Guys! I think I'm onto something. I'm right now calculating the paths for every point. If it's greater than a character's range of movement, it will calculate the nearest viable point. Now all I need to do is to cut this mesh from the triangulated navmesh. How do I cut it, though?
     
    Last edited: Apr 17, 2020
  17. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    upload_2020-4-18_20-43-39.png So far on that! Next up is MORE RAY TRACING! to completely avoid an obstacle. And maybe an outline.
     
  18. fetish

    fetish

    Joined:
    Aug 25, 2015
    Posts:
    73
    You have to cheat and define some destination polling minimum distance. If your maximum movement is 50m in a turn, you might only want to poll an invisible grid in units of 1 meter at a time, or some bigger or smaller unit, and then mark areas within a blob of the same size as the frequency. I'm sure there are well-known ways to optimize this type of search, but it comes down to how much precision you want. Ultimately you can still have your character move directly to the target location, regardless of the fidelity of your visualization.
     
  19. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    If
    If that's so, got a script for (At least) a flood fill algorithm like that?
     
  20. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    And yeah, running straight forward? a spherecast.
     
  21. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    upload_2020-4-21_18-45-28.png
    Because I'm trying to do a flood-fill, but, uh.....
     
  22. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
  23. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    Wait, you have a tutorial for that, @PraetorBlue ? Send it right here!
     
  24. PraetorBlue

    PraetorBlue

    Joined:
    Dec 13, 2012
    Posts:
    7,890
    Here's a good tutorial for starting with NavMesh:


    NavMesh will get you the actual movement. The drawing part i'm still not sure about. I know you can draw the whole mesh by getting triangulation data with https://docs.unity3d.com/ScriptReference/AI.NavMesh.CalculateTriangulation.html, but that doesn't quite get you all the way to where you want to go.
     
  25. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    Well yeah. I know Navmesh.Triangulation is probably one of the elements I would need to get the whole story... Alongside navmesh.calculatepath. Now the next part would be to ACTUALLY make the mesh, which would be difficult to do... Or at least how to arrange it to generate it like in the examples.
     
  26. MythrilMan51

    MythrilMan51

    Joined:
    Apr 24, 2017
    Posts:
    146
    upload_2020-4-24_10-30-15.png
    And for a short break before going into that breach again.