# A* pathfinding algorithm to identify entrances into current “room”?

Was looking for some online articles that might have a good idea or two in how to approach this but not finding much. Most of it deals with the various ways to generate and follow a path to a known destination type.

Basically the idea is that you have an existing node graph and want to utilize that data in order to locate entrances into the current area an AI unit would want to defend. So think of an AI unit assigned a task of defending a point with a radius and wanting to choose the best direction to face while waiting for enemies to show up that would be pathing to the defend point.

The critical point that I was looking for input on would be how one might identify the entrance points. Or the nodes that are the doorways into the area being defended.

The best idea thought of would be to do a breadth first outward search from the defend point and identify nodes that can see the defend point, have links, but none of the linked nodes can also see the defend point.

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.

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.

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.

• Excellent info. Thanks for the tips. While our levels are quite static they also dont really have consistently sized "doorways." So the grid approach could have limited use. But there might be crossbreed approach we could think about. Either way its looking like having precomputed or manually placed portals is going to be the best bet. – Alturis Jan 11 '12 at 21:58