Sensors based pathfinding and behaviors
Blitz3D Forums/Blitz3D Programming/Sensors based pathfinding and behaviors
| ||
| Hi, :) I was thinking about the pathfinding and the behaviors of the npcs in my game. I try to code a game with a gameplay similar to Daggerfall, but only the part about the dungeons exploration and the fights against creatures (in my game the bad guys are vampires.) I want the vampires to be agile, fast, strong. Therefore if i make the vampires characters follow a path of nodes around a furniture, that's not an impressive behavior... But if i manage to make the vampire character "sense" that there is a furniture, let's say a table, blocking his path, and if he can climb on it, or jump above it, then this will be an impressive behavior ! If you have played Morrowind or Oblivion, you understand what i mean by non impressive behaviors, the npcs only walk or run towards nodes. You climb on a rock or on a wall and you can shoot arrows to the npc and he is lost... If you have played Urban chaos or Gothic 2, you have seen what i mean by impressive behaviors, the npcs can follow you everywhere ! on the walls, on the crates, on the ladders, on the roofs, this is so funny to observe these smart bots ! Ahah :D I think i'm going to use nodes only to guide the npcs to the doors of each zone, and sensors to guide the npcs through the obstacles of a zone (mainly furnitures and columns) I have already used sensors with several linepicks each loop so that a character can sense the walls and the ledges in a parkour demo. This worked well, but linepick seems to be slow, i think i can try to use several collider spheres instead, or the Coldet lib as Yasha suggested. How would you achieve this ? Nodes with parameters around each furniture ? Or sensors on each npc ? Also do you know how to use navmeshes ? I have already read articles on the subject but i don't understand how you can use the tris of a mesh to guide a npc. Thanks, Last edited 2012 |
| ||
Have you tried creating a pivot connected to the NPC in front a few feet? Like so (O is the NPC and x is the pivot) top view and side view:
________
| |
O--x |Obstacle|
|________|
________
O--x |Obstacle|
______|________|___
Very simple way to detect obstacles, but it might work for you. If you give your obstacles and pivot different collision types and the pivot is hits the obstacle mesh, then have the NPC jump. Once the NPC jumps and the obstacle is low enough and is no longer colliding while in the air, have the NPC move forward. I like simplicity. Give it a try. Will probably fail miserably :). Last edited 2012 |
| ||
| Well navmeshes are the correct starting point for what you want to achieve - getting past the obvious artificiality of node-based pathfinding. Nodes can work well but they need to be pretty dense and be closely linked to the level design (e.g. they work brilliantly in the HL2 series, but that's because they're not trying to be a "generic" solution but rather the node placement and level design are linked to each other the whole way through the design process). The first part of using a navmesh is that to get from distant-point-A to distant-point-B, they map a path in essentially the same way as nodes: treat each pathfinding quad as a node and use a simple, fast algorithm to find out which quads the shortest path will cover. It's the second part where it gets interesting: as long as an NPC is anywhere on the nav quad, they're still "on" the path and don't need to immediately decide to "correct" their path the way they would if you were using nodes. So once the long-term route is chosen, they can also plan a short-term route that chooses how to cross this quad to get to the next one and the ones after that; the target they're now aiming for is a flexible position along the joining line that happens to provide the shortest following step to the quad one along from that. This point can move as the NPC may be required to move, making for much less obvious node-seeking behaviour. Now the first two parts assume that within a single quad, an NPC will not be obstructed. If there are no dynamic objects, this should be true, since the navmesh is set up to show routes that the static environment never obstructs. So the third, and most, interesting part is handling obstructions. Any object your system marks as a "collider" should have a top-down profile, either a box or a circle (possibly ditching the circle if having two kinds of profile slows things down too much; circles are much harder). It does not need to be any more specific than this: just err on the side of caution and mark irregular objects with an oversize box that comfortably holds them, and your NPCs will avoid them by a safe margin of an extra few inches. Knowing the collider box's X/Z position and yaw, you can determine the transform of the rectangle that needs to be subtracted from the nav quad. What you then need to do is triangulate the nav quad to take account of the missing space and extra vertices, and the NPC can then safely pathfind across every individual sub-quad nav-triangle in a very simple operation, stringing them together in the same way that the NPC initially chose the long-route across the whole quads. e.g.:  If there is no route across the triangles, mark the whole quad as obstructed and find a new long-route. Tips: - do not attempt to use B3D meshes or B3D collisions for this (do it entirely in software using "hypothetical" quads in a bank or something) - do not attempt to use overcomplicated object profiles - do not run this every frame Advanced commercial games, like Left 4 Dead, will work out every step taking several steps ahead into account as well, in an iterative process; this will let them consider things like the smoothest path across several quads or tris and take proper account of cornering and so on; thus removing the first unnecessary swerve to the right or the unnaturally tight final corner in the diagram above. However, this may be computationally expensive and you don't need to think about it immediately (upgrading your pathfinding to look more natural is a smooth progression if you start with even a simple navmesh, as opposed to nodes). Or, read how the pros do it: http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf Last edited 2012 |
| ||
| Get Game Programming Gems 1, it has a nice article on navMeshes. GPG3 also has one, but I haven't read it. (It's item 3.6 of book 1 in this list.) |
| ||
| Thanks for the suggestions and links :) I think i have an idea of what to do. Here : https://developer.valvesoftware.com/wiki/Navigation_Meshes Search "jump areas" or "crouch areas", i don't know if these are navmeshes, it seems to be trigger meshes which explains to the bot what to do but i can also use nodes at the same time. With this method, i only need to put one sensor on the npc and several triggers around each furniture. I think i will try both methods. Navmeshes are too complicated for me for the moment. Thanks, Last edited 2012 |
| ||
| +1 for Game Programming Gems. A NavMesh sounds more complicated than it is. I've written quite a few now and I'm very suprised how simple they are. It is only a slight adaption from node based pathfinding after all... Last edited 2012 |
   |