Hi everyone,

I have implemented pathfinding on 2D grid, I can provide start and end index and get the valid path in array.

.

The function that I have created:

vector<int> Pathfinding(bool* Grid, int StartIndex, int EndIndex, int GridWidth); // bool* Grid (array: true = open node, false = closed node)

Now, I'm looking to use this function in the 3D environment, I'm not sure about the right way to accomplish that

I have a terrain and building with two floors and the character should be able to walk in and outside the building and even walk on stairs and climb ladders.

What are the possible ways?

That depends on how your path-nodes are stored. Do you have a 3d-grid of walkable places? Do you have a network of path-nodes that is not in a grid?
The graph/grid you would use to search the path in would have to have extra-info, such as a boolean value to mark cells/nodes that are walkable/climbable to get stuff like ladders working.

Tell us a bit more about how the world you want to do pathfinding on is structured and how players/entities move around that world.

I thought about this myself for my grid, and I would need to move away from whether a node itself is walkable/blocked, and instead have a list of nodes that can be traversed to from that node. This reflects the situation where a player on top of a bridge can walk along the bridge, but wouldn't consider the spot underneath a valid spot. (Another way to do it is to ensure that your grid resolution is fine enough that the bridge tiles are marked as blocked, and you have enough room for open grid spaces above and below that, but that's quite limiting -- though it might work for a minecraft-like game where the world is made out of the same size chunks.) The first method is also better in that it will allow you to reuse your pathfinding for multiple things, it would work on a navmesh or a series of waypoints, or if you have teleporters or elevators, you could pathfind on them pretty easily.

(And if you are wondering about how to maintain a single flat index, the formula is: Flat[x + WIDTH * (y + DEPTH * z)] = Original[x, y, z])

The grid looks like the following:

bool* Grid = new bool[GridWidth * GridHeight];

Grid[0] = false;  // <- Closed node
Grid[1] = false;  // <- Closed node
Grid[2] = true;   // <- Open node

The function Pathfinding() returns array of walkable indices on Grid from start index until end index

Yeah, like I said, that doesn't work well, unless you have a very grid like world (And by that I mean your Bridge is as exactly as thick as your pathfinding tiles). You can move towards one or two different models, one is like this:

struct Node
{
   vector<int> Links;
}

then you have Node[yourcubesize] nodes, and that node can only travel to the nodes whose indices are inside that nodes Links field. The other way I have seen it done, is by having a Link be a structure itself, something like:

struct Link
{
  int DestTileIdx;
  LinkType (If you have different movement types, you could have things like Infantry, Any, Amphibious, Flying, etc)
}

(Someone can pipe in with how to optimize that for better perf, probably by moving out to a array of links that's outside the node, with the index into the array being the node you're interested in.)

@ferrous:

The following is what I have done so far in pathfinding:

[attachment=29652:pathfinding.png]

What I thought about is that I could treat the terrain cells as nodes and check for collision on each node with other game objects to determine if the node is open or closed

Then I could use the same pathfinding function that I wrote for the 2D grid above.

This may be a good use for a hierarchical method for your pathfinding.

The second (outer/coarser) tier mapping need not be grid based (so a natural split point between the tiers)

which may alleviate issues (and likely inefficiencies) of trying to do 3D all with grid.

Still there is more complexity of 2 diffent pathfinding methods, with having your map be sets of lower level grid maps (individual building floors, etc) and those connected by a more general (irregular) network of nodes (the entry exit points between the lower level map grids).