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

A* Pathfinding on Unity Terrain and "minecraft-style" cube building construction

Discussion in 'Scripting' started by FisherM, Oct 21, 2014.

  1. FisherM

    FisherM

    Joined:
    Dec 28, 2013
    Posts:
    366
    So I am working on a project and the terrain is typical unity terrain, I have both Apex Path, Navmesh and A* working just fine. I've spent a couple days reading up on this but the support is often very vague and specific to circumstance.
    I read through the following posts:
    http://forum.unity3d.com/threads/tutorial-procedural-meshes-and-voxel-terrain-c.198651/
    http://forum.unity3d.com/threads/need-dynamic-pathfinding-ai-for-minecraft-like-game.182348/
    http://www.elysiun.com/forum/showth...h-finding-and-AI-with-Minecraft-like-graphics

    None of which where particularly helpful but this seemed to be a useful asset but very little explanation on getting started with it.
    http://unitycoder.com/blog/2013/04/09/a-pathfinder-2d-3d/

    I also did all of A* tutorials and Apex Path Tutorials.
    Both of which have a similar issue, they are all down top down raycasts so it works great when I build a wall but if I have a doorway or any overhang the grid is blocked. I can do multiple grids and this is my main idea. However, the issue is that I am using unity terrain, I am using a regular A* style grid to calculate my normal terrain and then I am simply stuck because I can either have the blocks not count as obstacles to the terrain which obviously compromises ai traveling the terrain but this would mean the grids of the cubes would only block themselves so the cubes would work.
    Or if I have the cubes block the grid on the terrain any overhang breaks the ai.

    Assistance would really be appreciated, will post a few screenshots in a minute
     
  2. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    This is a topic I'd love to get into with you. But I don't really have the time to.

    I will say this up front.

    Why use a Raycast to build the ai path grid?

    If this is a Voxel system, you probably already have all the various blocks organized up in data. This data should easily be letting you know which voxels are on top of each column of blocks in the world, and you should be able to easily find neighbor columns, and thusly neighbors. And this also works in finding overhangs too. And you can put in pathfinding weights between each node based on the change in height between the two.
     
  3. FisherM

    FisherM

    Joined:
    Dec 28, 2013
    Posts:
    366
    The terrain is unity terrain, it also isn't voxelized generated or anything else. It is a single prefabed map. However the player constructs castles out of blocks in a "minecraftish" fashion and then waves of ai attack, in squads with some fairly advanced behavior. Constructing my own A* is a lot of work, particularly as I am risking spending a lot of time on something that I could have accomplished in another way.

    Please even if you're time is under pressure help is really appreciated. Have I missed your point?
     
  4. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    Hrmmm... that's a tough one.

    I know that Aron Granberg A* has a way to create obstacles on an existing path grid. Maybe you can create a gird out of the height map, and treat said castles and the sort as their own grids that can be obstacles.

    Another option is it has Recast built into it that can be recalculated. But it's slow to do so... so you'd have to figure out the best times to do so, so it doesn't impact gameplay.

    Go check out the system, it's got a lot of features.

    http://arongranberg.com/astar/

    Here is grid updating with obstacles:
     
  5. FisherM

    FisherM

    Joined:
    Dec 28, 2013
    Posts:
    366
    Like I said in my first post, I actually went through the whole a*, the issue is that the dynamic obstacles are handled on a 2d dimension overhangs basically have the same effect as a full wall. This obviously crushes any ideas of multi-level buildings.

    However it does sport a multi-level grid generation but it doesn't support dynamic generation an instantiation of them, which kind of is flawed by the same issue the Recast system is. The castles are built 1mx1m brick at a time so regenerating is kind of critical
     
  6. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    I'm saying you generate a separate grid out of your castles and what not. And you treat them as obstacles on the main grid.

    This means you'd have to change grids when going into them. You can do this by linking the grids.



    And another option is using Recast, which directly supports calculating with layers (overhangs, doors, etc). Downside is each time you call to recalculate, it's slow.