Return to Answer

Lastly, there are two ways you can approach this: coarse-grained quantisation of your level space, and fine-grained.

Arbitrary node placement is super, if your constraints allow it. This would be where you have level designers constructing your (static) levels. Here, the simplest and most sensible solution is to have them specify via editor or data file, nodes that represent portals inside your pathing graph. Obviously in this case it is also up to level designers to ensure that the geometry of the level is suited to that pathing which is put in place (usually you would do the level geom first, then lay pathing nodes over that to ensure the nodes are in all the right places and no others).

A coarse-grained grid is one where each cell in the grid you divided your level into, is at least as big as each entity you have moving around. In this case, it's very easy: wherever a cell has just two non-adjacent neighbours, it's single width, and you can assume that, if the previously walked cell had more than that, you've reached a narrowing point that you can call a portal. The downside? Particularly if your level is dynamic and you don't tend to match walls exactly to grid cell edges, you'll find there are times when geometrically it is clear that an entity could pass from one cell to another, but in terms of the pathfinding graph, due to its resolution and origin position, the pathing-evaluator simply can't detect the connectedness of two adjacent cells. This may not be a problem for you, however.

A fine grained grid is one where every cell is smaller than the entities in question, is a lot more complicated...

In the procedural case, or in a case where your initial level may be manually-constructed, but can be changed later (as is the case with destructible terrain), you need intelligence built in to detect what might be considered a "portal". This sounds a lot easier than it actually is, geometrically speaking. Consider a cave complex constructed, throughout, of the same homogenous material. Say you use some form of noise to generate spaces inside a level-sized block of solid rock, and then used some sort of coherence/metaball approach to join the closest points of these spaces. Now some of these join channels are going to be narrower than others, and in different places. You can see how the shape of entities can also affect where they might be able to traverse and where they might not. This is quite a problem in 3D; in 2D, it's a lot easier to handle but still not trivial. One way to make things easier in both cases is to assume either a square (cubic) or circular (spherical) bounding volume for each entity.

And this leads to 3 rough approaches that I've come across in my work.

Arbitrary node placement within a static level is super, if your constraints allow it. This is where you can place your nodes at any point in floating point space. This would be where you have level designers constructing your (static) levels. Here, the simplest and most sensible solution is to have them specify via editor or data file, nodes that represent portals inside your pathing graph. Obviously in this case it is also up to level designers to ensure that the geometry of the level is suited to that pathing which is put in place (usually you would do the level geom first, then lay pathing nodes over that to ensure the nodes are in all the right places and no others).

Coarse-grained grids are used when a more dynamic approach to pathfinding is required, such as where the level is either procedurally generated, and/or where it can change at runtime. Here, you need intelligence built in to detect what might be considered a "portal" in your grid of potential pathfinding nodes. Each cell in the grid you divided your level into, is at least as big as each entity you have moving around. In this case, it's very easy: wherever a cell has just two non-adjacent neighbours, it's single width, and you can assume that, if the previously walked cell had more than that, you've reached a narrowing point that you can call a portal. The downside? Particularly if your level is dynamic and you don't tend to match walls exactly to grid cell edges, you'll find there are times when geometrically it is clear that an entity could pass from one cell to another, but in terms of the pathfinding graph, due to its resolution and origin position, the pathing-evaluator simply can't detect the connectedness of two adjacent cells. This may not be a problem for you, however.

Fine grained grids are used in the same circumstances as coarse-grained grids, but with the added constraint that you don't want your pathfinding nodes to be so clearly delimited into low-res tiles. So each cell is smaller than the entities in question.

This sounds a lot easier than it actually is, geometrically speaking. Consider a cave complex constructed, throughout, of the same homogenous material. Say you use some form of noise to generate spaces inside a level-sized block of solid rock, and then used some sort of coherence/metaball approach to join the closest points of these spaces. Now bearing in mind that your pathfinding grid resolution is finer than the size of a single entity, some of these join channels are going to be too narrow for an entity to pass (even though air could pass through), while others might not. This will vary at different points along the channel, and you can see how the shape of entities can also affect where they might be able to traverse and where they might not. This is quite a problem in 3D; in 2D, it's a lot easier to handle but still not trivial. One way to make things easier in both cases is to assume either a square (cubic) or circular (spherical) bounding volume for each entity.

A coarse-grained grid is one where each cell in the grid you divided your level into, is at least as big as each entity you have moving around. In this case, it's very easy: wherever a cell has just two non-adjacent neighbours, it's single width, and you can assume that, if the previously walked cell had more than that, you've reached a narrowing point that you can call a portal.

A fine grained grid is one where every cell is smaller than the entities in question, is a lot more complicated...

In the manual case where you have level designers constructing your (static) levels, the simplest and most sensible solution is to have them specify via editor or data file, nodes that represent portals inside your pathing graph. Obviously in this case it is also up to level designers to ensure that the geometry of the level is suited to that pathing which is put in place (usually you would do the level geom first, then lay pathing nodes over that to ensure the nodes are in all the right places and no others).

Arbitrary node placement is super, if your constraints allow it. This would be where you have level designers constructing your (static) levels. Here, the simplest and most sensible solution is to have them specify via editor or data file, nodes that represent portals inside your pathing graph. Obviously in this case it is also up to level designers to ensure that the geometry of the level is suited to that pathing which is put in place (usually you would do the level geom first, then lay pathing nodes over that to ensure the nodes are in all the right places and no others).

A coarse-grained grid is one where each cell in the grid you divided your level into, is at least as big as each entity you have moving around. In this case, it's very easy: wherever a cell has just two non-adjacent neighbours, it's single width, and you can assume that, if the previously walked cell had more than that, you've reached a narrowing point that you can call a portal. The downside? Particularly if your level is dynamic and you don't tend to match walls exactly to grid cell edges, you'll find there are times when geometrically it is clear that an entity could pass from one cell to another, but in terms of the pathfinding graph, due to its resolution and origin position, the pathing-evaluator simply can't detect the connectedness of two adjacent cells. This may not be a problem for you, however.

A fine grained grid is one where every cell is smaller than the entities in question, is a lot more complicated...

There are two concepts at work here: graph topology and level geometry (aka topography). They're two sides of the same coin.

Furthermore, there are two ways your levels could be produced: manually or procedurally.

In the manual case where you have level designers constructing your (static) levels, the simplest and most sensible solution is to simply have them specify via editor or data file, nodes that represent portals inside your pathing graph. Obviously in this case it is also up to level designers to ensure that the geometry of the level is suited to that pathing which is put in place (usually you would do the level geom first, then lay pathing nodes over that to ensure the nodes are in all the right places and no others).

In the procedural case, or in a case where your initial level may be manually-constructed, but can be changed later (as is the case with destructible terrain), you need intelligence built in to detect what might be considered a "portal". This sounds a lot easier than it actually is, geometrically speaking. Consider a cave complex constructed, throughout, of the same homogenous material. Say you use some form of noise to generate spaces inside a level-sized block of solid rock, and then used some sort of coherence/metaball approach to join the closest points of these spaces. Now some of these join channels are going to be narrower than others, and in different places. You can see how the shape of entities can also affect where they might be able to traverse and where they might not. This is quite a problem in 3D; in 2D, it's a lot easier to handle but still not trivial. One way to make things easier in both cases is to assume either a square (cubic) or circular (spherical) bounding volume for each entity.

One way to identify portals is to exhaustively cast rays around a circular or spherical shell whose diameter is equal to the minimum width needed for an entity to pass through (i.e. their body width). In order to limit the number of locations to do such a test from (to something less than infinity), it's a good idea to quantise your level space into a grid. Even so, this is very time-consuming in both cases, especially in 3D, and if possible should be done once only, and cached. Of course, that is easier said than done if your level geometry is indeed dynamic. Another way to visualise this casting of ray to a shell, is to see it as the placement of an "atom" into a tiny open space, and growing that atom until is hits the surround rock, like a balloon expanding.

The point I'm getting at is that while a portal is pretty much instantly recognised by any higher animal (our facility probably being due to natural selection, since quickly identifying hiding places had to have been crucial), there is actually a lot of raw logic that goes into determining where a body of a given set of dimensions can pass, and where it can't.

There are two concepts at work here: graph topology and level geometry (aka topography). They're two sides of the same coin.

Furthermore, there are two ways your levels could be produced: manually or procedurally.

Lastly, there are two ways you can approach this: coarse-grained quantisation of your level space, and fine-grained.

A coarse-grained grid is one where each cell in the grid you divided your level into, is at least as big as each entity you have moving around. In this case, it's very easy: wherever a cell has just two non-adjacent neighbours, it's single width, and you can assume that, if the previously walked cell had more than that, you've reached a narrowing point that you can call a portal.

A fine grained grid is one where every cell is smaller than the entities in question, is a lot more complicated...

In the manual case where you have level designers constructing your (static) levels, the simplest and most sensible solution is to have them specify via editor or data file, nodes that represent portals inside your pathing graph. Obviously in this case it is also up to level designers to ensure that the geometry of the level is suited to that pathing which is put in place (usually you would do the level geom first, then lay pathing nodes over that to ensure the nodes are in all the right places and no others).

In the procedural case, or in a case where your initial level may be manually-constructed, but can be changed later (as is the case with destructible terrain), you need intelligence built in to detect what might be considered a "portal". This sounds a lot easier than it actually is, geometrically speaking. Consider a cave complex constructed, throughout, of the same homogenous material. Say you use some form of noise to generate spaces inside a level-sized block of solid rock, and then used some sort of coherence/metaball approach to join the closest points of these spaces. Now some of these join channels are going to be narrower than others, and in different places. You can see how the shape of entities can also affect where they might be able to traverse and where they might not. This is quite a problem in 3D; in 2D, it's a lot easier to handle but still not trivial. One way to make things easier in both cases is to assume either a square (cubic) or circular (spherical) bounding volume for each entity.

One way to identify portals is to exhaustively cast rays around a circular or spherical shell whose diameter is equal to the minimum width needed for an entity to pass through (i.e. their body width). In order to limit the number of locations to do such a test from (to something less than infinity), it's a good idea to quantise your level space into a grid. Even so, this is very time-consuming in both cases, especially in 3D, and if possible should be done once only, and cached. Of course, that is easier said than done if your level geometry is indeed dynamic. Another way to visualise this casting of ray to a shell, is to see it as the placement of an "atom" into a tiny open space, and growing that atom until is hits the surround rock, like a balloon expanding.

The point I'm getting at is that while a portal is pretty much instantly recognised by any higher animal (our facility probably being due to natural selection, since quickly identifying hiding places had to have been crucial), there is actually a lot of raw logic that goes into determining where a body of a given set of dimensions can pass, and where it can't.