A* Pathfinding Project

3D Board Game With Multiple Layers


#1

I looked through the documentation, but I’m not entirely sure which Graph type I should be going with for my project. Here’s a description of what I’m wanting to do for it to help narrow down which type to use:

  • The “board” pieces will move like the cube in this video (so hopping from one tile to another, except in 8 directions instead of just 4) https://www.youtube.com/watch?v=ZmYXymCR22M

  • The pieces will only be able to stop on top of a tile at a certain point (the middle of the top)

  • The “board” will be dynamic. A user will generate a kind of battle map at runtime, save it, and then other players will be able to load that map to play on.

  • There can be multiple levels to a board, like a building with more than one floor or a bridge that you can go over or under.

  • All tiles will be the same size and have the same spacing along the XZ axis, but the Y axis placement could be anywhere from -1.0 to 1.0 higher than the neighboring tile

  • Tiles will need to hold data like:

    • If a tile is a ladder piece
    • If a tile teleports to another tile
    • If a tile is harder to traverse (so something like double cost for moving through it compared to a normal tile)
  • The tiles can be set manually (so if a user takes a model of a building and wants to define the walkable tiles inside that building, they would put tiles on the floor, tiles going up any stairs, tiles on the second floor, etc.) So it would need to be able to tell which tiles were neighbors from proximity.

  • The world could be fairly large if the user wanted it to be

From what I’ve read in the documentation, it seems like the Point, Recast, and Layered Grids are all options, but I don’t know which would be the best to go with for my case.


#2

Hi

Sorry for the late answer.

The only reasonable graph type for this game is the layered grid graph or point graph. Recast is not the right one.
In the current version the layered grid graph only supports 4 neighbours though, but in my dev version it supports 8, so that will be released at some point.

Question: Does the pathfinding need to take into account ladders and teleports? Or is this part of the puzzle?

You’ll want to have a look at https://arongranberg.com/astar/docs/turnbased.html#ITraversalProvider


#3

Hey aron! I’ve been so busy this month, sorry for the late reply! I’ve actually re-thought the design of this and wanted to see if it was plausible:

Is it possible to get all points in a navmesh area at runtime (so generating the walkable area at runtime as well) that intersect with points on a specified grid?

For example (with my terrible drawing), if I had a road with a bridge going over it, would it be possible to generate the gray areas as navmeshes and then get every point on those navmeshes that falls inside of a 1 by 1 grid (so starting at 0 and increasing/decreasing by 1)? They would be able to have the same XZ coordinates as long as the Y coordinate is different (like the green point where the bridge goes over the road). If I can get that information from your asset, then I can feed that data into my grid to make the rest of what I want to do work.


#4

Hi

I’m not quite sure what you are asking… I’ve tried to answer some questions that I think you are asking:
The graph can be recalculated during runtime. You can get all nodes within a region.
Layered grid graphs can have multiple nodes at the same XZ coordinate.


#5

Sorry for not being clear! Here’s what I’m asking:

For a Layered Grid Graph, can I generate it with a specified grid size ([1 x 1], [0.5 x 0.5], etc.) and then get a list of all of the node points created?

If so, when the not points are created, will they be generated along the axis lines or in the middle of them? So like A or B in this image:

image


#6

I just bought the asset since I know I’ll end up using it in other projects no matter what the answer is here, but I hope it’ll work for this too.


#7

Yes.
See https://arongranberg.com/astar/docs/runtimegraphs.html for info about how to create a graph during runtime. You can also just create it in the inspector and then just set the size from a script.

You can get the nodes using
https://arongranberg.com/astar/docs/layergridgraph.html#GetNode2
or
https://arongranberg.com/astar/docs/layergridgraph.html#GetNodes
or
https://arongranberg.com/astar/docs/layergridgraph.html#GetNodesInRegion2

See also https://arongranberg.com/astar/docs/accessingdata.html
The nodes’ positions are in at the center of the nodes (like B).