Wrapping my head around multi-level grid based pathfinding

I’m trying to come up with a way to pathfind on multiple levels. See image:

The orange walls would be considered a ladder, connecting you to the upper levels.

At first I thought of looking at it as though it were top down 2d, but I also need to be able to go under things at some point. Does anyone have any suggestions as to where to start? If there is an asset that can handle this out of the box?

Any advice would be welcome :slight_smile:

Well, NavMesh handles this out of the box, assuming your ladders are NavMeshLinks.

If by “pathfind” you mean you want to be able to apply common algorithms like BFS or A* to the gridspaces in your map, then fundamentally all you need to do is find some abstraction that allows you to view your level as a graph, where the places you can legally be are the nodes in the graph and the directions you can legally move are the edges. In this case, you probably treat each cell of your grid as a node, and then come up with some rules for enumerating all the directions you can move from a given node.

Your rules might be something like this:

  • You can’t move to any cell if it is inside a wall

  • You can’t move to any cell unless there is a wall (floor) directly below it, so you have something to stand on

  • You can move horizontally to any adjacent cell (within the above restrictions)

  • You can move “diagonally” upwards or downwards if a ladder is present at the appropriate coordinates

Assuming that moving horizontally diagonally is not allowed, that gives you 12 possible directions of movement to check for each node (4 moving horizontally, 4 moving up a possible ladder, and 4 moving down a possible ladder). No more than 4 of those directions will actually be legal for any given space, but you need to check them all to know which ones are legal.

Alternately, if you want to allow jumping and falling from higher levels onto lower ones, then the rules might be something like this:

  • You can’t move to any cell if it is inside a wall
  • If there is no wall (floor) directly below your current cell, then the only direction you can move is straight down
  • If there IS a wall (floor) directly below your current cell, then you can move horizontally to any adjacent cell (except walls)
  • You can move “diagonally” upwards if a ladder is present (you don’t need to use the ladder when going down, since you can just fall)

Note that any cells that you can NEVER enter (such as walls) can effectively be “removed” from your grid, which might speed things up (depending on how your data is represented). But you should probably just focus on making something that works before you try to optimize it.

Wow, thanks for such a detailed response. A lot to think about here. What do you think is the best way to store this data? An array, multiple arrays? A list? I was actually thinking about falling and flying etc, but I may have bit off more than I can chew as I’m fairly new to this :smile:

My levels are built out of sections much like you see in the picture, which are placed together randomly. Should I add cubes to each unit with the floor data and destroy them at load after getting their info? Just having a hard time figuring out where to start.

The most obvious approach would be a multi-dimensional array. This is similar to an array of arrays, except it has to be “rectangular” (all the sub-arrays are the same length) and it makes your intent a little bit clearer.

Sometimes in these sorts of games you end up with a really large grid area of which only a small percentage is actually usable (for instance, you have a really tall tower in one spot that forces you to have 100 vertical spaces in your grid, but everywhere else in the map you only use the bottom 3 planes). If that happens, you end up with a “sparse array”, where most of the values in your array don’t really matter. At that point, you can often get a significant efficiency boost by switching to a different representation that only stores the values you care about, without allocating memory to the 95% of your grid that no one will ever enter. For instance, you might use a dictionary where the key is the coordinates of a gridspace, but the only gridspaces you actually store in the dictionary are the reachable ones.

1 Like

With all your advice I almost have it completely working, just working on rules now, and making them less… "if"ish

Thanks so much!