• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Gianni Guarino

Members
  • Content count

    2
  • Joined

  • Last visited

Community Reputation

683 Good

About Gianni Guarino

  • Rank
    Newbie
  1. Well, the second part of your discourse is clear, and right. The first part, though, I don't know if I well understood. In fact, BPF doesn't make any cost evaluatio, because humans can't do this as they have normally no cost data to use about the real possible paths. BPF only use filtering with the common sense, so I don't see similarities with the A* algorithm.
  2. I think that's probably it's useful that you take a look along the whole article, because in the other parts you can see a lot of differences with the other types of path finding. Anyway, you're right when you say that it's not totally new. As I already wrote in the second part of the article, some parts of the model have already been used in other contexts, but here are for the first time part of a whole, organic model, and for the first time are confirmed by some psychologic theories.
  3. This is the first of three articles that treat a new approach for the Path Finding. It's a part of the studies and experience I made in the last years, in the fields of the Artificial Intelligence for Games, Philosophy and Evolutionary Psychology. The current panorama of the Path Finding All the Artificial Intelligence modules for Videogames are made by using models thought several years ago. Some of those models are rather old, taking into consideration the fast growing of the other software modules of videogames. For example, even I didn't found any source that specifies when the Navigation Mesh (or Navmesh) has been implemented for the first time, I can state that this model is used at least from the 2004 (and then 10 years ago). It is, together with the Navigation Grid, the most used and, practically, the most advanced approach to obtain the graph for making paths for videogames. Nonetheless, the Waypoint Navigation is still used in a multitude of simple games, and is even older than the Navmesh. If we compare the improvements in the AI modules with the ones of Graphic modules (I mean the ones that render the game), we could see that, referring to when the waypoint navigation has been used for the first times, the graphics were at level of the CGA technology. The evolution made by the Graphic module, in these years, is enormous. Ok, you could say that computer graphics has been largely helped by the evolution of the hardware. The problem, though, remains: in the last 10 years, if we avoid to mention the OCC model (relative to the psychological approach to the intelligent agents) and some other agent-based approach that, by the way, are still practically unused in videogames, we can't say to have witnessed something that could be defined as really new, or a strong, sharable improvement. The reason? Mainly because, despite the advent of the cognitive science, the approach to the artificial intelligence topic by the insiders is never changed in decades. How the path finding of the videogames of the future will be? Is it possible that it will have modules made on models that we have from decades? Personally, I reckon that the videogames of the future will be far different from the currents. The problem for developers is not how they will be, but how to build AI models able to support new features. I had a different approach, respect to the classic one, about the "intelligence" topic. I started from the consciousness that we humans are not a species fallen from the sky, completely different from all the other species of Nature on Earth. This brought me to know the Evolutionary Psychology, from which I profitably tapped several theories that, I'm sure, will help AI to develop the first, real, virtual living being. A topic question: what is intelligence? What is Intelligence, speaking about what is important for videogames? Intelligence is not more than a tool to improve the human ability to manage the environment. It's the more powerful tool ever made by natural selection on Earth, but still a tool like the elephant tusks, or the opposable thumbs we share with the other primates. The Evolutionary Psychology calls them Evolutionary Adaptations. There are a lot of studies and findings, in Neurosciences and Psychology that state the fact that emotions take part of the human (and animal) intelligence, and without them the sole logic is useless. This way to think at intelligence changes dramatically the approach to any problem you find in videogames, and with any other human or animal simulation. For instance, my approach to the path finding issue takes into consideration the fact that humans (and animals) have their own way to memorize maps in mind. The result of this memorization often doesn't correspond to the actual map, more often than we would admit. Even the approach to the navigation for building the graph is completely different. In my opinion, it should take into consideration how we move toward a physical target. This approach carries several new features and performance improvements, in respect to the ones currently adopted. I try in few words to explain some of the main thoughts that are at the base of this new approach. First of all, I need to title the parts in which I divide the news. Navigation Graph Population Best Path Identification Dynamic Objects Avoiding Smoothing Movements Mental Map First Topic - Navigation for innovative games Please think about a game like "I am alive", "Spiderman", "Tomb Rider", "Prince of Persia", "Assassin's creed" or one of a lot of others where the player's character is able to climb, jump and make other unusual actions. In almost all the titles of this genre, there are some unnatural behaviours done by NPCs. One of the most evident is when NPCs want to catch/kill the player and, in order to do that, "decide" not to climb and follow the PC. They only expect the player to finish his climbing actions in order to attack him, or try to shoot him from the walkable area when it's climbing. This is not a logical and biological behaviour, because unless all the NPCs know the buildings around them like their shoes, they can't be sure that the PC could flee from their hands. In order to reproduce a correct human behaviour, NPCs, for example, should use the simple tactic of the pincer: some of them follows the thief/enemy/PC by climbing behind him, while the others try to run and block his way out. How to do that, though, if the Path Finding Navigation system can't use walls as "usable areas"? Videogame programmers rarely make their NPCs able to climb and follow the climbing player. This is because, in order to do that, they should customize the path finding module, making it more complex and often not usable for other videogames in which the player only has to walk and run. A new approach, that I baptized "Biological Path Finding" (BPF), resolve the problem at its root. There should be focal points (automatically generated) only in the places where two micro-environments meet. This brings to have a focal point even where the way to proceed changes because the different micro-environment is vertical, that is a wall or some other "climbable" surface. Each line that comes from a node will acquire a weight (talking with an A* approach) that will be calculated in base of the ability of each "kind of NPC" to traverse it, by climbing, swimming, walking etc. This solution involves a more general management of NPCs, whom should be categorized in Species. The good news is that, with this approach, you can have a different best path for each Species of NPC, while each NPC is able to move along the level based on its own ability. The better performance in elaborating the paths thanks to a lower amount of nodes, respect to the current approaches, mitigate the fact that the path elaboration, with this approach, will be done for each species. Unless the game uses dozens of different species (I never found a game like that!), the total amount of time for elaborating the paths off-line should be not higher than the ones of the current approaches, but giving us more features and wider solutions to adopt in videogames. Yes, it's something more complicated than a mere, simple path navigation system (do and use), like most of the current videogames have. Nonetheless, videogames are already evolved from the first ones like Invaders or Pacman, and we can surely say that all the main titles in genres like RPG, MMORPG, Shooters and Strategy are very complex per se, so that the cost for having new features for NPCs could be paid without too much regret. The need to ease the run-time elaboration In the last years, more and more videogames contain larger levels. It's obvious that the larger the level, the harder is remaining into acceptable performance when NPCs calculate their paths to catch the target and the number of NPCs is higher. I know that several videogame developers recognize that problem as one of the most time-consuming during the development. The fact is that we continue to think too logically to the issues that involve human simulations. If we think, instead, to have a person in place of each NPC, we should then linger on to the way with which humans think about the path finding, speaking from the point of view of the Psychology. I don't want to write down here a book again (I already made it, and in the next month will be published), so I need to condensate some thoughts in a shorter version. When a human tries to think about a larger zone and how to reach his destination, he usually has some mental images about the most important, for him, parts of the environment (blocks of a city, for example), and then think about each zone as a black box. This approach helps a lot, even with our path finding issue, because it avoids calculating the path at the highest detail. One of the studies in Psychology that better analyse the issues related to paths traveled by humans has been done by Lynch (1960). The double dimension for path finding has been already used in some games. The fact is that in the Biological Path Finding it fits the overall approach, being one of the tools that derive directly from a psychological study of the human behaviour. What this approach brings is the fact that you save time in making only the calculation that you really need. In fact, are you sure that the NPC will travel all the path? How high is the possibility that the NPC will be killed along the path, or will find a good reason to find a new path again or, in any case, do something different? In these cases, the calculation of the overall path in a large level has been made in vain. The approach of breaking large calculations into several, smaller ones made "along the road" by NPCs should be used widely, because it's a good way to enhance the performance. In any case, this lets the NPC be more "human" without making heavy the overall performance. Then, the BPF takes use of two dimensions of Path Finding: the District and the Zone Path Finding. The District Path Finding is the one I explained in the previous paragraphs, the other is the one that resolve the need to walk along a short path, in order to catch a closer target or exit from the district (if necessary) from the side required by the selection of the "correct" (not the best!) macro-path found by the District Path Finding. Even at that level, the approach is completely different from the usual. It tries to minimize the amount of micro-paths that has to be kept into consideration. Humans, in fact, take a decision about the path to use, in order to move toward a closer target, by looking at the target (or in direction of it) and check only the paths that have their first focal point not distant, in terms of angular degrees, respect to the direct direction toward the target. This way to select the path has been already addressed by other researchers, for example by Douglas Jon Demyen (2007) in his thesis. Conclusion In my next articles, I'll continue to talk about a Biological Path Finding approach, and more precisely talking about the other five topics already named in this article. Path Finding for Innovative Games: Graph Creation and Best Path Selection. Path Finding for Innovative Games: Object Avoidance and Smoothing Movement. Article Update Log 14 Mar 2014: Title changed 10 Mar 2014: changed the number of articles, whom becomes three 1 Mar 2014: Initial release
  4. In the previous article, I mentioned a new approach you should consider if you want to build next-gen, innovative games, called Biological Path Finding (BPF). I always thought that the most used models are not a bible, to use without thinking about, and that doubts are often the factor that brings our mind to create better AI models. Please note that you need to read the previous article of this topic (relative to the Navigation), before reading this one. 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. A strictly reliable simulation should consider all the data mentioned by Lynch. Anyway, this would build a huge algorithm that no one will implemented in any game. A good approach, then, is taking all the most important notice for a human and animal simulation. Where we need to put the Focal Points respect to the micro-environment? We should position them one for each entrance of the micro-environment. Those positions are the nodes of a real path, and will be the nodes of our Mental Map. Each micro-environment must have one or two entrances. The exact position will be the central point between the objects creating the micro-environment. We can have different levels of Focal Point identification. For instance, one that identifies focal points only for a single dimension for each inner object, like in the Figure 1 in the left part. Or, like in the Figure 1 in the right part, one that identifies FP for both the width and length dimension. A level that develops even in height should also find FP by checking with the height dimension. Postulates My (little) experience in implementing the BPF leads me to say there must be some postulations, some rules that you should use to make a great implementation of this model. I can't describe all the postulations I've collected, because of the reduced space of an article. The ones I don't describe, anyway, are not too much. Their importance, also, is less than the ones of the postulations I'm going to describe. 1- Entrances We can have one or two entrances for a micro-environment. 2- Visibility A 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 One If 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 objects Consider 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 Point Focal 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**** (*) This is not a mandatory need, respect to the one of the run-time calculations. (**) As the Psychology states (Lynch, 1960, )(Tversky, 1993) we can't: 1) Remember a map as if he owns the map physically on his hands, especially if the zone is not "lived" by the NPC for a while. 2) Avoid that emotions and the need to decide fast confuse reasoning, and then the decided path can often be not the one the logic would propose. (***) It's time, I reckon, that 'smart' games will adopt the natural subdivision among NPCs, in order to better use the new features of the next-gen path finding solutions and innovative decision-making systems. (****) Psychology states that humans can also forgot parts of an already-used path, or make mistakes in remembering the exact sequence of the focal points (Moar, Bower, 1983)(Sadalla, Montello, 1989)(Hirtle, Mascolo, 1992)(Byrne, 1979)(Lloyd, Heivly, 1987)(McNamara, 1986) 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. Another filter is the "sensation of length" of each path. Look at this filter, because it should be difficult to implement but really useful. It is one of the most used filters by our mind. Humans and the most intelligent animals should consider the sensation of length of a path (Sadalla, Staplin 1980)(Maki, 1981). There can be several factors that could take place in defining the length sensed by a biological entity. One of them is the emotions proven during the past traversals (the better the sensations proven, the smaller the perceived lenght). Another one is the fact that the path is mostly straight or tortuous. If you want to use this filter that matches with some psychological studies (Sadalla, Staplin, 1980), you can even create one or two flags for any focal point. There are even other filters you can create, but let me say this is on of the most important among the ones relative to the typology of the path. The duty of this flag is store the type of the micro-enviroments that starts after the focal point. As you can see in the figures of this article, a focal point can stay close to only one micro-environment (see the Figure 1), or in the middle of two micro-environments (see the Figure 4). The flag unchecked could mean that the mini-environment is straight, while the flag checked means that it is tortuous. The higher the number of checked flags along the path, the lower the likelihood that any NPC will use that path. Figure 4 An example of a focal point and its two flags suggesting the type of the two adjoining micro-environment. A further filter is about the NPC knowledge of the districts. This is another important feature that a well-done human simulation could consider. The BPF could create randomly the knowledge map of the district, made per NPC or per Species. In case of long-living NPCs, you should do it by recording the places travelled for each NPC. Normally, the result should be one or two paths, maximum three of them. What is then the one to use, if there are more than one of them? The path to use will be the one containing the highest number of districts traversed by the linecast that goes from the NPC toward the target. This solution, though, should be counterbalanced by the number of districts of each path. To recap the filters: 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 ... If the result is more than one district path: 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 Inner Believable Path Selection After having decided the district path to follow, the NPC has to start to resolve the path finding inside the current district. Then, when inside the next districts, redo the same for that district. Dividing the level into districts (cubes) normally leads to have several cases into which more than one walkable (or better usable) surface links two districts. This means that an NPC could have more than one solution to go to the next district of the chosen district path. Dividing the paths into two levels speeds up the run-time selection of the believable path, and forces you to split the path finding into more than one step. Nonetheless, to use the approach correctly, there are some new issues with which you should face with. In case of the passage between two districts, there are two things the design-time elaboration of the paths should check: the "dead paths" and the connections between passages through districts. In fact, if one of the possible paths whom connect two adjoining districts stops into the district without the possibility to pass to another one, the NPC should know previously about this issue. To fulfil the problem, in design-time we shall select, for each district, the paths that travel the district by going from one adjoining district to another district. This could be a time-consuming calculation, especially if the number of the passages between adjoining districts is high. This could be a good reason to change manually the districts, to avoid having too many links between two districts. Anyway, the algorithm should be the following: A - select the district 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). Conclusion The biological approach to a path finding, inherent the Biological Path Finding, is an innovative solution not only for humans, zombies, monsters and aliens simulation, but even for intelligent animals. Nevertheless, never underestimate the role of emotions under the path finding issue. Even the ability to decide, like the one explained in this article, is a feature made not only by logic. As a confirmation of this statement, Plutchik said that emotions are basic adaptations needed by all organisms in the struggle for individual survival (1980, p. 145). He suggested that the selection occurred in the Cambrian era, 600 million years ago, was responsible for most of our emotions. The eight adaptations are incorporation, rejection, destruction, protection, reproduction, reintegration, orientation and exploration. This means, also, that a wide variety of animals can share the most important filters of the Mental Navigation. So, what differs from humans way to solve a path finding to the ones of animals? The difference is rather small, and is specifically related to the use of logic. This is not entirely true, by the way. Nonetheless, the causes of this are so deep and so difficult to reproduce in code that I prefer not to mention. Most animals cannot use training to better govern their emotions, and they are also unable to consider more than one deduction about the filters adopted. If you want to distinguish the human behaviour to the animal one (or among animals with different intelligence) toward the decision for the path selection, use only one filter for the simplest animals. Then, apply other filters when you are facing with humans (or more intelligence animals). The only filter you should always use is the one about the selection of the paths whose first focal point is toward the direction of the target. A last consideration I wish to put into the article is the following: as you could state, the two (or more) level Path Finding requires you to have a Decision-Making system whom allows NPCs have more levels of goals. This is another important issue to bear in mind when you chose the BPF. The next article will focus on the Mental Map, Dynamic Object Avoidance and Smoothing movements. References Byrne, R. W. (1979) Memory for urban geography. Quarterly Journal of Experimental Psychology 31, 147-154 Hirtle, S. C. and Mascolo, M. F. (1992) The heuristics of spatial cognition. Proceedings of the 13th annual conference of the cognitive science society. Hillsdale, N: Erlbaum 1992, pp. 629-634 Lloyd, R. and Heivly, C. (1987) Systematic distortions in urban cognitive maps. Annals of the Association of American Geographers 77, 191-207 Lynch, K. (1960) The Image of the City. Cambridge MA: MIT Press. Maki, R. H. (1981) Categorization and distance effects with spatial linear orders. Journal of Experimental Psychology: Human Learning and Memory 7, 15-32 McNamara, T.P. (1986) Mental representations of spatial relations. Cognitive Psychology 18, 87-121 Moar, I. and Bower, G. H. (1983) Inconsistency in spatial knowledge. Memory and Cognition 11, 107-113 Plutchik, R. (1980). Emotion, a psychoevolutionary synthesis. New York: Harper and Row. Sadalla, E. K. and Montello, D. R. (1989) Remembering changes in direction. Environment and Behavior 21, 346-363 Sadalla, E. K. and Staplin (1980) The perception of traversed distance: Intersections. Environment and Behavior, L. J. 12, 167-182 Tversky, B. (1993) Cognitive Maps, Cognitive Collages, and Spatial Mental Models. In Frank, A.U. and Campari, I. (Eds.) Spatial Information Theory: A Theoretical Basis for GIS, Proceedings COSIT '93. Lecture Notes in Computer Science, 716, pp.14-24, Springer: Berlin. Article Update Log 19 Mar 2014: Added References 19 Mar 2014: General updating for ease the reading 18 Mar 2014: Change the figure 4, added other 2 images, adde a description of the term micro-environment 14 Mar 2014: Title modification, moved the image as an attachment, some other changes 10 Mar 2014: Initial release
  5. A* finds a least-cost path from a given initial node (that, in game, is the closest node to the NPC) to one goal node (that, in game, is normally the closest to the PC). A* traverses the graph by following a path of the lowest expected total cost or distance. I dont' see where I told something different respect to that definition, in my article.   The issue of the A* is that is not able to make filters before making calculations. You need to calculate all the paths before knowing which is the best to use. With the Biological Path Finding you just need to filter paths with the common sense and,only for some of them,in case you remains with more than one still available, you make a sort of a draft calculation with some "on/off" relative the kind of micro-environments of each remained path.   So, the A* is a brute force, somewhat bovine approach respect to the BPF one, in the sense that you are forced to do all the calculations, even the ones that the common sense would propose you to avoid. Hope this could help better.
  6. This article concludes the topic of Path Finding for innovative games. The model described is based on scientific evidences which assert that human intelligence is not made only by logic. The Biological Path Finding approach is still in the research phase, even if the writer already adopted it in a couple of games. Dynamic Object Avoiding Nowadays, some game developers force their AI implementation to recalculate the best path when an object is intersecting the current path of an NPC. Fortunately, not all developers use this approach. The outcomes of that action, speaking in terms of credibility of the NPC and about performance, are definitely negative. Dynamic Objects in Path Finding is a strange issue, and in my opinion is a non-problem. We should first divide the issue into two main cases: 1. an object is moving toward the current path of an NPC 2. an object has moved and been placed along the current path of an NPC The way to react to these two cases should be different. In fact, if an object is moving, we have to worry about the possibility of a collision with this object. A possible collision, though, never should lead us to change the path, unless there is a high amount of moving objects in the same place. If this case happens, you shall check your game or simulation setup. In fact, a place in which there can be multiple moving objects should have lines of the graph with a higher weight. When an object (or another NPC) is moving toward a line of a path used by an NPC, the only problem to face with is avoiding it. This though must not change anything in the decision, already taken, of the path to follow. A similar problem you'll have with an object that has moved and placed along a line of the path used by an NPC. In this case, unless the object is so wide to block completely the passage, you need to treat it with the Object Avoidance algorithm. How should be a proper Object Avoidance algorithm for the BPF? There is no preference or precaution to consider. You should use the algorithm 'only' to avoid object. When the NPC has avoided the object, the algorithm must go to its end. After that, the Path Finding system will be active again, and the NPC will go straight toward its next focal point. What if the object that is blocking the path is so wide that makes impossible any trial to turn it? Do we need to find another path? I absolutely prefer avoiding this solution. Humans, when inside a real and physical problem, are not dominated by logic. Even if it's difficult to understand, emotions manages our actions. Only after having filtered events with emotions, we may think and then use logic. A human, when started on a path, if there is a problem along it, tries to imagine (not calculate!) a sub-path that helps him to turn the problem and continue along the same path. It's too complicated considering to change path, and the time is never enough for a human walking along the road. Only a danger can change this way to do, but it's something that has not to do directly with the path finding system. So, even in the worst case, there is no need to start the path finding calculation from the current position to the target. The correct solution for a proper human simulation is finding the "simplest" sub-path from the current position to the first focal point beyond the object, or using the Object Avoidance algorithm. In the human approach to the PF problem, there is never a sort of calculation, but rather estimations. Estimations consider the number of turns and the number of focal points: in our mind there is no continuous registration (like a video, for example) of the path, but only flashes about the focal points. Thus, if the human saw a map, he will have a better chance to make a better estimation of the length of each path. Any focal point is close to a micro-environment. This helps us, because it's impossible that an object occupies more than one micro-environment (unless is a giant object!). Smoothing Movements Especially in case of complex or wide and open paths, I reckon that grid and mesh navigation don't give enough NPC credibility because of the number of nodes in the map. There are, substantially, four grades of quantities of nodes in a path: Too few nodes, or/and placed in senseless positions: it's not possible for the NPC to walk as a human, and then it will have unpredictable results; [possible with the Waypoint approach] Few nodes placed in the "focal points": the NPC reacts like humans do; [currently proposed only by Biological Path Finding]; Many nodes: the behaviour of the NPC is far from being similar to the one of humans. Without a good (and sometimes time-expensive) smoothing algorithm, the NPC will have a behaviour similar to one of a drunken man [can happen with the current navigation solutions]. Too many nodes (from dozens to hundreds of times more than the focal points): the behaviour of the NPC comes back to seem similar to the one of humans. The off-line and run-time calculations, though, become really expensive [can happen with NavGrid]. Take the example below. Figure 1 You can see here the number of convex polygons (squares) made with the Navigation Grid and, below, the same map treated with the Mental Navigation, the Navigation made with the Biological Path Finding approach. You can see the number of nodes and relative lines that Navigation Map will create is higher in the current navigation approach in respect to the new one. Figure 2 Another problem, for the current navigation approaches, is the need to make use of the smoothing algorithm almost for any line. For an approach that develops a high amount of nodes, this worsens performance. Mental Navigation needs the smoothing algorithm for any passage among focal points too. Nevertheless, the cost is minimal if referred to the overall time of execution of the current path finding approaches, because of the small number of focal points. There is now the need to cite another postulate of the BPF: if there is a static object or a ravine between two focal points referred to non-contiguous micro-environments, NPCs will use the Object Avoidance algorithm to move between those focal points (see the previous paragraph). This rule could even be substituted by another that, instead of using the Object Avoidance algorithm, moves one or both focal points in order to overcome the issue. The Mental Map Mental Map is the approach for building a Navigation map that takes into account how humans (and animals) actually build the mental maps in their mind. In the previous section I already treated the most important part of this part of the module. Nonetheless, there are some factors you should consider before thinking how to implement the BPF. As I've written several times in some different places, human intelligence is not only logic. It's rather the contrary. Into the cauldron of intelligence there are other ingredients with an importance higher than logic. As the evidences of several findings made in biology and neuroscience can witness, intelligence is not owned only by humans. All primates have a high intelligence. Despite what you may think, a chimpanzee for example may use a language with 250 words! Other animals have a moderate intelligence, like dolphins and dogs. The base of intelligence is nearly equal among all these species. The human species, though, developed a multitude of "psychological adaptations" that animals don't have, or have in a simpler version. What I want to say is that logic is only the diamond tip of the biological intelligence, but it's far from being the unique ingredient. Emotions and several other factors are the very basic ingredient of intelligence, and without them we could not understand the world that surrounds us. What are the outcomes of this reasoning? Two facts: A) Humans, when the arousal* of one or more emotions is high or too low, tend to have non-logic behaviours; B) Animals, in terms of path finding approach, have almost the same way of doing things when faced with a path selection or an object avoidance. (*) - Arousal is, for emotions, something similar to the volume for a radio receiver. There has not been, so far, any complete model able to represent the whole world of intelligence. I mean, for whole world of intelligence, a module containing emotions, moods, sentiments, beliefs and personality traits, not to mention the age differences, social rules and hormones. This leads us to think that, at least for a while, BPF could not be implemented at its best. Conclusion So, is it already possible to treat emotions in the Path Finding, in order to better simulate human behaviours? Maybe not immediately, I think, but soon. There are some guys trying to build a solid AI model (and I'm one of them, even if I follow a different, in some ways easier road than others). I reckon the time for a solution which simulates humans and animals behaviour with a higher reliability is coming. Anyway, you can even build an implementation of the BPF that makes no use of emotions. For the rest, you can find in the first and the second article the main ingredients of the Mental Map Navigation. The topic of the Biological Path Finding still belongs to the field of research, even if in these articles you can find the base for making successful implementations too. It's my intent to put on an Open Source project about BPF, to speed up the development of this new approach. Article Update Log 20 Mar 2014: An updating 19 Mar 2014: Initial release
  7. I reckon you're right, Buckeye. That's why I'm trying to completing the book about BPF with a practical approach, and I hope to start with a new Open Source project, for the first library that will help in using BPF, in April.
  8. Hi, Buckeye, and thank you for your considerations. I'll soon make better explanation in some parts of the article. Nonetheless, for the micro-environment explanation, I should start from far away, and it can't be a matter for a single article. In April will be published my book about BPF, and there you'll find an exaustive explanation of the topic.
  9. Bravo, Tutorial Doctor, you started from the right place. You said "We discern the difference between wrong and right", and this is the main difference between "learn" and "understand". All our current AI models, I refer to the learning machines and all the models that use neural networks, are able to learn things, not to understand them.   Let me introduce you to an example I've made in my blog (it's in Italian, but I'm just translating it in English): there are three reigns: the reign A, the reign B and the reign C. The first two are alwasys in war one each other, while the last one is unwarlike, and all its resources are driven toward scienses.   Suddenly, an earthquake shakes the ground in the realm A. There are collapsing buildings, thousands of deaths. Let us now give the "meaning" that the subjects of the three kingdoms do to the same event, namely the earthquake just happened. In the realm A, certainly they will define it as "the catastrophe" and will remember that event certainly for so long as an "extremely negative event" The kingdom B, for its part, will define that earthquake as "a blessing from heaven" and it certainly will remember it for a long time "as the Divine that punished their warlike enemies". It 's very likely that the event has then changed the fortunes of war. So, for the subjects of the kingdom B the earthquake just happened is an "extremely positive event" The subjects of the kingdom C, finally, define the event as an "extremely interesting event" because, with the subsequent large aftershocks that followed the big one, they have improved their understanding of the seismic event in general. Then they will remember it as an event "very positive" and appreciate the great contribution it made ??to their knowledge of the planet.   So, what is the real meaning of that hearthquake? Which of the three reigns gave it the effective meaning? I want to go deeper in the issue: do you really believe that a thing or an event could really be valued by logic? Is Logic able to say that an event is good or bad? Neither in thousands of years this could happen. Simply because only emotions can let use "decide" what is wrong and what is good. But good and wrong are things that we can define only with a point of view. Hearthquake, collisions of planets or the flutter of a butterly are only events for logic, nothing more.   If someone of you wants to go in deep and continue with me this topic, I'll be happy, because I'm developing (maybe) the thirst AI model that takes into account the main discovers of biology and psychology.
  10. I reckon almost all of you started from a point that brings to nowhere. Do you know that Artificial Intelligence scientists, researchers, companies and universities are trying to arrive to replicate the human intelligence from decades? The fact that no one reached his goal is so simple that you could probably not imagine.   First of all, the meaning of "intelligence", the way with which we use to mean that term, is completely wrong. We use the old concept of intelligence inherited from classic philosophy, that thought intelligence was only relative to the faculty to use logic. Unfortunately (for all the people who followed this road), intelligence is something more complex than logic.   I exort you, if you really want to know how the real things are, to make some interesting reading on some of the discoveries of the modern psychology. Take a look, for example, to Antonio Damasio. He is one of the most important living scientists who have studied the behavior of the human brain. In 1995 he wrote "Descartes 'Error", with which "flips the cultural tradition that has always devalued emotions because could disrupt the serenity of reason and shown that, on the contrary, they are essential for good functioning of the mind: if a man loses emotional capacity is not able to be reasonable." Damasio says his theories through scientific evidence. In fact, he makes reference to a patient's clinical study (patient's name: Gage), as a result of an accident at work. Gage had an iron bar of 110cm that, from a cheek, smashed the skull ( from the inside ). By chance or miracle, Gage remained alive. But what happened in his brain was extremely interesting ( for science, much less to him ) . Before the accident, he was balanced, polite, clever and shrewd in business. After that, Gage became bizarre, defiant, unable to make profitable decisions for himself or to plan for his future as a social being. This is due to a lesion in the prefrontal cortex. From this discovery it was realized that there are, in our brain, some areas that "manages" emotions and others for logic (although some have been used for both functions) . Gage was no longer able to have its own sake, nor to perceive pain. The part, so to speak, of his emotional brain does not work anymore, or at least work only partially and very bad. He was able, however, to perform all the logical operations of which he was capable before. So the logic in his brain, didn't receive any damage.   There are a sum of other scientific evidences of the importance of emotions and, more in deep, impulses into the development and maintenance of intelligence that only a part of the science, inside Artificial Intelligence field, continues to ignore.   Without emotions, any AI model can't "think to itself" and then be really intelligent. And if you want to say more, I could also say that emotions are the "reinforcement" that led humans build new parts of their mind to work with logic, and the consciousness is the counterpart of emotions, and is a "reinforcement" too, that natural selection brought to combat against emotions and then balance their exceeds (emotions, alone, can harness the logic of our mind and bring us to make choice that lead us to prove pleasure soon, despite what could be better for the future, but this is a more difficult part of the matter; if you want to go in deep, please wait for a couple of week to take my book "Biological Behavioural Model", or ask for information to some experts of Evolutionary Psychology).   What I want to say is that I could answer to the thirst question of the thread: if we continue to think that intelligence is only logic, not few months, but neither a billion of years could be enough to fulfil the goal of creating a virtual human mind.