Graph Creation
NavGrid or the NavMesh models are enough and good, without any customization, in several circumstances. If you want to build a single video game a time, for a video game similar to others, they can be perfect for you. If you have few NPCs living together, and you don't mind that they sometimes (or often) do what humans never do when walking, there is no reason why you should find for something better. Conversely, the future of video games will not use NPCs with a less-than-good human behaviour. Newer models should provide new features without the need to customize, to have better performance. The current Navgrid and Navmesh models have good pros, but even stronger cons. Both could make, in several circumstances, long time for the off-line calculations. You should not use them when there are several NPCs living together in a wider level. If you want your game go fast, or if the correctness of the human behaviour is a must, you shall find something new and different. Besides, it's not recommended the use of Navgrid for wider 3D levels, whom also develop in height. The use of the Navgrid in that context raises connections a lot, letting the path calculation be even more complex, with obvious performance issues. Waypoints in the reality: the focal points Can waypoints have a counterpart in the reality? You know that waypoints, or any kind of polygons that form a navigation map, are fundamental for NPCs to move across levels. Probably you never thought that also humans and animals need to have similar references when they move in the reality. A real human, with his needs, have to have a limited number of "strategic" positions along a path. Please put your attention to a real path. For instance, a path inside a building. You know that no living being can go straight to its target, unless it is in an open space. It has the need to change direction. Do you think we can find a rule with which reproduce the positions in which a real living being should necessarily change its direction? The goal is considering only points where a human need usually to change his direction. These points can be next to a corridor, between two neighboring columns, a doorpost and so on. Micro-environments If you take a look at an environment, especially a human-made one, you can see there are some parts where the passage is narrower respect to the contiguous parts of the environment (see the figure 1). Two walls forming a corridor make a micro-environment; a doorpost is a thin micro-environment; a column close to a wall or to another column forms a micro-environment. There can be different ways to build the Mental Map and, then, identify micro-enviroments. One of the easier (and the faster, in case you have one or more wider zones in the level) is possible thanks to the launch of linecasts from a series of points defined in the environment. The first thing to do is checking whether the reference point is inside an object or not. Only the reference point outside objects will be considered. There will be a point each X units of measure. The X is a value compatible with the width of the species of NPCs. I named this approach Radar Node Generation, because it emulates the way with which a moving radar builds up its representation of the environment. This solution simulates the behaviour of our mind when, the first time we walk a new path, records positions, clutters and so on. In the reality, our mind don't record all the positions in which we have been (as stated by Lynch). On the other hand, the approach I have proposed emulates, also, the ancient behaviour of our mind (shared with all living beings whom owns eyes) whom calculates the spaces between clutters. The algorithm will launch two linecasts from each single point: one to its left and one to its right, both toward the farthest point. The implementation of this approach can vary. Anyway, see the figure 2 for an example. We then need to check whether there is a collision with a closer object respect to the previous or the following point along the series. If, for example, the previous point hasn't found any closer object on the right of it, and the current point has found one, we could clearly state there is (from this point on) an object closer to the point. We should/could made this action in length, width and height. Nevertheless it depends on the level complexity, and is up to the developer. There are several tips that makes the action performance-compliant, but it's not the place in which to talk about it. Figure 1 Figure 2 Focal Points What are Focal Points? These kinds of points are the strategic position in which living beings need to change direction. In reality, that point is the last useful position for them to change their direction. Living beings, in fact, change direction smoothly, starting a bit before the focal point. Focal point have another great importance for living beings. As our mind can't record in memory a path with something similar to a video, something continuous, it records only the important places. I prefer to mention what Kevin Lynch said in his prominent contribution and study of mental maps (referred to the mental map of a city): "Most often our perception (of the city) is not sustained, but rather partial, fragmentary, mixed with other concerns. Nearly every sense is in operation, and the image is the composite of them all." (Lynch, 1960, p 2.). Always referring to his studies of the city mental representation, he said that mental maps should contain the following types of data:- paths: the streets, sidewalks, trails, and other channels in which people travel;
- edges, perceived boundaries such as walls, buildings, and shorelines;
- districts, relatively large sections of the city distinguished by some identity or character;
- nodes, focal points, intersections;
- landmarks, readily identifiable objects which serve as external reference points.
We can have one or two entrances for a micro-environment.
2- VisibilityA micro-environment is such if the focal points created at its limit or inside it see one each other. For example, a corridor formed by two big objects, placed in the middle of a wider place, leads the design-time elaboration create two focal points, each at the beginning (or ending) of the corridor. Where the focal points of the micro-environment can't see one each other (in case of a rounded corridor, for instance), we should add one or more new focal points along the micro-environment. In this way, each focal point can see at least one other focal point.
3- Two become OneIf the micro-environment is small, speaking about one dimension (horizontal or vertical) referred to the size of a medium NPC (for instance, between two columns), instead of creating two focal points, the algorithm will create only one. This resultant focal point will take place in the middle of the space between the deleted focal points. For instance, look at the two doorposts in the Figure 1, where you can see the result of this postulation.
4- Radius Distance toward static objectsConsider a user-defined radius distance between the static object of the level and the limit of the surface. This could help in avoiding to have lines between focal points that collides with static objects.
5- Follow the last visible Focal PointFocal points are the only parts of any zone that humans and animals consider, in a path, when they need to change direction. However, during the movement along the path, the BPF (Biological Path Finding) states the agent will go not toward the next focal point, but toward the "last focal point", along the path, the agent can "see". This is an innovation that improve further the agent's credibility, and this is what really humans do when are in place of agents.
Figure 3 Look at the previous image. The Green Circle, located in the left part of the building, is the position where the NPC takes place, while the Orange Circle is its target. The wider green line is the path the NPC will use thanks to the BPF, while the thin violet line is the selected path. The Violet Circles, instead, sign the change of viability, and only the NPCs able to jump (at a defined height) will see them. As you can see, the second focal point the NPC will take into consideration is not the second in the selected path, but the third. The third the NPC will use is the fifth of the selected path. This is because of the previously mentioned rule. With it, the run-time approach states the NPC will not lose time by following each focal point of the chosen path. Contrarily, the NPC will use, of the chosen path, only the "farthest, still visible" focal points the NPC can see from the current focal point. The result for the example is that the number of focal points the NPC will use is only two, instead of five, as provided by the path of the mental map. A solution like that will not only produce, most likely, the lesser number of path nodes ever, but even will improve the human behaviour simulation. Consider a real person in the same context of the NPC of the linked image (the building is a church). Throw away all the paths and focal points, and imagine how he behaves in that context. If he decides to follow the path that our NPC will use, he certainly goes straightforward, until the encumbrances of the buildings will allow him. Then, he will start to turn (a bit in advance respect to the focal point) to go another time straight until the building will allow him, or until he reaches his target. Please note that here there has been an almost completed discussion about the Mental Map of the BPF. Nonetheless, in the last article I prefer to talk again about that part, because its better implementation should consider some other factors. How a Path Finding model for innovative games should be? Coming back to the general discussion of this topic, we can say the generation games and, especially, the innovative games, in the early future will have the need to have more features and better performance. Also, we will have the need to reach those performance without putting complexity over complexity on an AI model that does not already provide those features. In detail, an innovative path finding model should provide:- A faster off-line calculation of the single graph, respect to the current ones*.
- Ability to use multi-genre paths for NPCs, by letting NPCs use not only walk and run along the path, but even jump, climb, swim etc.
- Ability to have different good paths for different species of NPC, according with the physical characteristics of each NPC species
- A faster run-time calculation of the "believable best path"**
- Resolve the problem of the dynamic objects along the paths with no added complexity
- Find multiple targets even of the same species (for example, shelters and bulky objects)***
- Change the graph dynamically when walls and big objects change their positions
- Take always into consideration that the mental map of each NPC can be different from the actual map****
Believable Path Selection
District Best Path Selection BPF is so different respect to the classic, "only-logic" approach, that work better without any use of the current algorithms used to find the shorter path. It's worth not going into details, for this issue. However, there are several factors for which the filters can bring to select a single path with no help of other algorithms. For example, the weight of emotions, mental map errors, the traits of NPC species or the limited number of levels, will usually bring to have only one path that overcomes all the filters. For example, a wide level could use 10 districts (see my previous article for more details). Normally, each district could have four other districts connected to them (unless the level develops even in height). Unless the level is a sequence of districts, or the level is huge, it's rare that the target is distant more than two districts from the NPC. Usually, then, it's useless to adopt any calculation of the best path, about the District level (see the previous article). There is a simple and effective solutions to limit the number of paths that reproduces the human behaviour. Its goal is avoiding all the paths whose first district is not far from the straight line between the NPC and its target (presuming the NPC knows the map, at least broadly). After that, you should also remove the paths containing at least one district checked as "to avoid" for the species type of NPC. For instance, the decision-making system or even the developer in design-time should flag the district as "to avoid" (or even the developer in design-time):- If a district is full of dangerous monsters that can kill the NPC.
- If a district is full of micro-environments non-viable, or is viable with difficulty for that NPC species.
- If the path contains a darker zone, and the personal traits of the NPC (if available) depicts it as a non-courageous individual.
- Only the district paths whose first district is not far from the direct line between the NPC and its target
- Only paths without "to avoid" districts
- Sensation of the Length of the Path
- Only paths with known districts
- Take the path with the lower number of districts or/and consider the higher number of district traversed by the direct line between the NPC and its target
A1 - select one side of the district where there is at least one passage to the adjoining district
A11 - For each passage, check if there is a path that conduct to another adjoining district. If so, flag the passage as compatible with the passage to that district (in the way you wish).
There is no need to calculate the length of each path, and this helps a bit. The run-time part of the BPF will use the data relative to the possible passages to the next districts, to check which passage to select for going to the next district. If there are more than one passages that traverse the district toward the next one, the NPC mind should decide which to use. How? You should use the same filters adopted to the district level of the path finding. Anyway, I suggest to use one or two, between the sensed length and the distance of the passage respect to the direct line toward the target. To start the run-time selection of the inner path, you need to know the early part of the inner path and the passage to the next district. The former is where the NPC is entering the district, or where the NPC is placed. When you have both, you shall select the path to use for arriving to your next path finding goal. Even in this case, you should use the filters already discussed. It's up to you to decide which of them, or use all. Note, though, that this way of thinking of the NPC is not the right way if your project is a tactical war game. The tactical war game is one of the rare cases in which the paths could be already well known by each NPC "at the table". In this case, then, a good solution remains one of the correct, only-logic approaches. The only filter you should add is the level of arousal of the emotions currently lived by the NPC (arousal is, for emotions, something similar to the volume for the music). This is, though, an issue not direct managed by the PF system. Nonetheless, you could easily note the Biological approach should be faster than the current ones. The reasons I affirm that is because the actions executed by BPF are lightweight. In fact, in any case there is a reduced number of nodes in the graph, even thanks to the paths leveling (see the first article for more info).