AI Question
Blitz3D Forums/Blitz3D Programming/AI Question
| ||
| I'm at a point in my little 3D project now where I'm focusing on AI. I have a basic "chase" system going but I can easily walk into a room if I'm being chased, let the spider walk in, I walk out, and run around the outside of the room a bit and of course the spider has no idea where the door is. I was thinking a simple linepick for the walls and turning the spider until the pick is zero...but it would have to walk all the way around the inside of the room until it is able to slip out the door. Back in the old days (Everquest) they just translated the monsters forward a bit if they got stuck. Looking for ideas on this...I am guess I need to start learning A+? |
| ||
| The simplest technique to do this would be to drop AI "hint" objects (invisible non-colliding objects i.e. pivot) at design time i.e. for doors, corners, cover points, etc. Record a short trail history of the player's movements at regular intervals especially any time the players movement angles changes substantially and any time they pass through a hint object (use a sphere or bounding box for the ai hint object that covers the area that when the player was inside would trigger that hint). If the monster is currently in a chase status and lost visual sight of the target have it hunt around a little then if it doesn't find the player head for the oldest door hint in the player's history that is more recent than the time it lost sight of its chase target then repeat if it doesn't find the target after heading to that door - hunt around a little more than head to the next most recent door hint in the history - if you don't have way finding built in then the cheap and dirty solution is to use the player's trail history. |
| ||
| If it's at all possible for your game's design, have your AI actors consume an abstract version of the world that doesn't include meshes, colliders, or physics objects. e.g. if your levels are laid out according to a base grid, even though they may be made of 3D geometry and not show any sign of this in the rendered view, you can have far more efficient AI by preserving the notion of that grid at runtime and simply letting it know which squares are obstructed or clear, rather than having it reconstruct that information out of data not intended for the purpose. This will let you use an efficient algorithm like A* instead of messing about with picks (protip: there is no efficient solution that uses picks). The AI doesn't have to move on a grid, just consume the grid points as waypoints to its target. If you can't do this, the next best thing is to use a graph of nodes laid out over the level geometry manually. Actors can again move over geometry using regular movement and collision, but aren't aware of it as such (much like what you have now) - but instead of moving towards a target object, they plan a route to that object via the graph (pick the nearest node to the target, the nearest node to themselves, and then move along the chain). Navigating a graph again would use A* or something similar (A* navigates any graph: grids are just a special case with an even layout). There's an excellent introduction to this second strategy in the developer commentary for Half-Life 2 Episode 1, in the abandoned hospital (the commentary actually turns on node visibility for you to see what the zombie AI is doing). If you go and play that you should get a lot of ideas! (that particular strategy is no longer used in new Source games, but it's much simpler than what they replaced it with) |
| ||
| Breadcrumbs..... Let your creatures drop a trail of breadcrumbs timestamped and follow them.....bloodhounds sniff the trail sort of thing. V easy to implement and effective in many cases. More complex: precalculate a little by running through the level and leaving a base trail of breadcrumbs which can be parsed. The breadcrumbs approach is good for maze like structures. Not so good for open environments. |
| ||
| Hint I learned from a book years ago: Direction = random (4) is never a solution to pathfinding! ;-) |
| ||
| and of course the spider has no idea where the door is Why not use nodes positionned near passages, near incorners, near outcorners, around obstacles with premade links between some nodes ? This works well and is fast because there are less nodes to consider to create a path. See : http://www.blitzbasic.com/Community/posts.php?topic=104836 However if you use this approach you can't turn move obstacles. But Morrowind, Oblivion, Fallout 3 and many others games use this approach. (only the small objects can be turned moved, not the big obstacles) If you want to be able to turn move obstacles you need to use nodes positionned on a grid, with premade links (at front, at back, at left, at right, at frontleft, at frontright, at backleft, at backright), and then calculate which nodes and which links can be used (those which do not collide with obstacles) for the path calculation. This also works well but is slower because there are more nodes to consider to create a path. All of this is easy enough to code, but try to add obstacle crossing into the system and this can become very difficult to code... |
| ||
| Thanks guys these are all good ideas and helps me out a good deal with this thinking process. But now I'm curious as to how to implement a decent line of sight routine for entities that don't rely on a camera. Looking into this now. |
| ||
| The easiest way to do line of sight in a fixed but arbitrary environment is to precalculate. Fill the level with different sized spheres much like a childs play area ball room. Any entity within the radius of one of these definitely can see the other entity. If you can draw a straight line through overlapping spheres then assume the two are visible from each other. Not exact but good enough. A lot of gaming is about faking things well enough that no one notices. |
| ||
| Thanks Matty. Can I have my yogurt now? |
| ||
| You can use low tris meshes for obstacles and for characters/vehicles parts but you would have to do several linepicks to see if each part of each character/vehicle is visible. THis can be fast enough if the meshes representing the obstacles and the characters/vehicles are low tris and if you consider only the obstacles characters/vehicles which are near enough (of course you can use different meshes for the collidables/pickables and for the "renderers") Another approach is to hide all lights, set the ambient light to 000,000,000, color the obstacles in black, color the characters/vehicles in different color (other than black...) then capture a small render (for example 100x75), then analyze the colors of the rendered image and determine if some of the colors which are "seen" by the bot correspond to the color of one of the other character/vehicle. If yes one or several character/vehicle can be seen, if no none can be seen. This works well and is fast enough if you do this for one or a few bots per frame. |
   |