Thread: [Algorithms] Robust ray/triangle intersection?
Brought to you by:
vexxed72
From: Juhana S. <ko...@ni...> - 2007-08-21 13:14:09
|
Hello. I copied the ray/triangle intersection routine from Real-Time Rendering book. When I choosed the epsilon to be 0.0001, a lot of triangles became skipped. Many of the skipped triangles are facing the camera. Strange. http://www.funet.fi/~kouhia/ship_ok.png (eps = 0.0000001) http://www.funet.fi/~kouhia/ship_bad.png (eps = 0.0001) (The ship is on 2.0 x 2.0 square and is In_prison_ship.nif of Morrowind.) Juhana -- http://music.columbia.edu/mailman/listinfo/linux-graphics-dev for developers of open source graphics software |
From: Enrico Z. <enr...@gm...> - 2007-08-21 13:18:53
|
Hello, > I copied the ray/triangle intersection routine from > Real-Time Rendering book. When I choosed the epsilon to be > 0.0001, a lot of triangles became skipped. I dont know this specific algorithm, however with the epsilon it sounds strange. Have you tried ray-triangle intersection based on barycentric coordinates (http://rafb.net/p/gOE2vN82.html) ? Best regards, Enrico -- Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen! Ideal für Modem und ISDN: http://www.gmx.net/de/go/smartsurfer |
From: Stephan R. <ke...@so...> - 2007-08-21 13:22:38
|
On Tue, 2007-08-21 at 15:18 +0200, Enrico Zschemisch wrote: > Hello, > > > I copied the ray/triangle intersection routine from > > Real-Time Rendering book. When I choosed the epsilon to be > > 0.0001, a lot of triangles became skipped. > I dont know this specific algorithm, however with the epsilon it sounds strange. Have you tried ray-triangle intersection based on barycentric coordinates (http://rafb.net/p/gOE2vN82.html) ? > I can second that, I've used barycentric coordinate based ray/triangle intersection myself in the past and it worked flawlessly. Stephan |
From: Gino v. d. B. <gi...@dt...> - 2007-08-21 14:52:13
|
Juhana Sadeharju schreef: > Hello. I copied the ray/triangle intersection routine from > Real-Time Rendering book. When I choosed the epsilon to be > 0.0001, a lot of triangles became skipped. Many of the > skipped triangles are facing the camera. Strange. > > http://www.funet.fi/~kouhia/ship_ok.png (eps = 0.0000001) > http://www.funet.fi/~kouhia/ship_bad.png (eps = 0.0001) > (The ship is on 2.0 x 2.0 square and is In_prison_ship.nif > of Morrowind.) > > Juhana > First of all, if the ray origin is at some distance from the world origin, you might want to consider remapping all vertex position relative to the ray origin. Secondly, the only purpose the EPSILON serves is to compensate for the rounding error in the determinant. So, see if you can get away with EPSILON = 0.0. If not, then at least make it relative to the estimated rounding error (Absolute EPSILONS are plain evil and should never be used. ) The estimated rounding error would be something like EPSILON = 10.0 * numeric_limits<Scalar>::epsilon() * max(dot(vert0, vert0), dot(vert1, vert1), dot(vert2, vert2)), i.e. something relating to the maximum squared distance of the triangle's vertices to the origin. Gino van den Bergen www.dtecta.com |
From: Pierre T. <pte...@ag...> - 2007-08-28 12:58:27
|
Hi guys, I'm going back to some AI stuff and I'm wondering about cover algorithms for NPCs in a typical FPS / shooting game. Basically I would like my NPCs to run for cover in a realistic way when they get shot at. They should know where to potentially hide, and what place is the best hiding spot depending on the player's position. I have a game level exported from MAX, pretty much a polygon soup as far as rendering & collision is concerned. There's a 2D navigation mesh for path-finding, in case it matters. I'm wondering how to automatically detect "good" places to hide, and how to do it cheaply (of course). Any experience with this, guys? I have a bunch of ideas about how to implement "something", but it doesn't hurt asking if there's a well-known standard solution to the problem. - Pierre |
From: Megan F. <sha...@gm...> - 2007-08-28 13:15:08
|
Assuming your pathing node structure supports it, one way is to search outwards from the enemy position until you find a node that has no visual connection to another node. That is, a node blocked from the player by a wall, etc. However, that would result in fairly boring AI visually. If you want to make it fancier, go through your levels and flag "exciting" cover (corners, things to crouch behind), and design the flags to indicate what position the enemy should be in to take cover there - "Blind firing around corner", "crouched", etc. Then just search that structure when looking for cover, instead of the normal movement structure. On 8/28/07, Pierre Terdiman <pte...@ag...> wrote: > Hi guys, > > I'm going back to some AI stuff and I'm wondering about cover algorithms for > NPCs in a typical FPS / shooting game. > > Basically I would like my NPCs to run for cover in a realistic way when they > get shot at. They should know where to potentially hide, and what place is > the best hiding spot depending on the player's position. > > I have a game level exported from MAX, pretty much a polygon soup as far as > rendering & collision is concerned. There's a 2D navigation mesh for > path-finding, in case it matters. > > I'm wondering how to automatically detect "good" places to hide, and how to > do it cheaply (of course). Any experience with this, guys? I have a bunch of > ideas about how to implement "something", but it doesn't hurt asking if > there's a well-known standard solution to the problem. > > - Pierre > > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > -- Megan Fox Idyllon, LLC http://www.shalinor.com/ http://www.idyllon.com/ |
From: Emile K. <fla...@gm...> - 2007-08-28 13:20:41
|
Heh, funny, I saw a presentation this afternoon about that at GDC China, by the guy who did Company of Heroes :) Not a FPS, though it might still be useful. Basically, each piece of cover would "generate" good "cover spots" around it. When a guy got shot at, he'd scan five meters around him, and take the best cover (he didn't go into details, but I assume it takes account of from which angle he got shot at, how good a protection is offered, whether they can shoot back, etc.). If there's no cover within 5 meters, he falls to the ground. Then later he might move to a better cover. Things would probably be different for a FPS, but I guess a bunch of "good cover spots" all over the map would probably be the best (placed by LDs or automatically generated). Emile On 8/28/07, Pierre Terdiman <pte...@ag...> wrote: > Hi guys, > > I'm going back to some AI stuff and I'm wondering about cover algorithms for > NPCs in a typical FPS / shooting game. > > Basically I would like my NPCs to run for cover in a realistic way when they > get shot at. They should know where to potentially hide, and what place is > the best hiding spot depending on the player's position. > > I have a game level exported from MAX, pretty much a polygon soup as far as > rendering & collision is concerned. There's a 2D navigation mesh for > path-finding, in case it matters. > > I'm wondering how to automatically detect "good" places to hide, and how to > do it cheaply (of course). Any experience with this, guys? I have a bunch of > ideas about how to implement "something", but it doesn't hurt asking if > there's a well-known standard solution to the problem. > > - Pierre > > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: John W. R. <jo...@si...> - 2007-08-28 14:10:55
|
Pierre, Why not just add 'cover' as a heuristic in your Astar search? There's an enormous amount of raycasting bandwidth available in your collision code so it doesn't seem like it would be that big of a problem to add to the search. Instead of searching Astar to find the closest path, simply search to find one that provides the 'most cover' based on visibility blocking. With your raycasting code I can do something like 10,000 raycasts a second against a highly complex 3d environment without any really significant CPU overhead. That's a crap load of visibility checks. John -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Pierre Terdiman Sent: Tuesday, August 28, 2007 8:00 AM To: Game Development Algorithms Subject: [Algorithms] Enemy cover algorithms Hi guys, I'm going back to some AI stuff and I'm wondering about cover algorithms for NPCs in a typical FPS / shooting game. Basically I would like my NPCs to run for cover in a realistic way when they get shot at. They should know where to potentially hide, and what place is the best hiding spot depending on the player's position. I have a game level exported from MAX, pretty much a polygon soup as far as rendering & collision is concerned. There's a 2D navigation mesh for path-finding, in case it matters. I'm wondering how to automatically detect "good" places to hide, and how to do it cheaply (of course). Any experience with this, guys? I have a bunch of ideas about how to implement "something", but it doesn't hurt asking if there's a well-known standard solution to the problem. - Pierre ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Pierre T. <pte...@ag...> - 2007-08-28 14:26:49
|
Hi John, > Why not just add 'cover' as a heuristic in your Astar search? There's an > enormous amount of raycasting bandwidth available in your collision code so > it doesn't seem like it would be that big of a problem to add to the search. That's a good idea, actually. Hmmm, I'm currently using PathEngine so the actual pathfinder / A* code is in a black box, but I might drop it soon anyway (replacing it with your AI Wisdom article, actually). I might very well try the cover stuff at the same time. Hmmm. Not the answer I expected but that's an interesting twist.... - Pierre |
From: John W. R. <jo...@si...> - 2007-08-28 14:35:57
|
Well, here is a really fast Astar implementation. I didn't write it, it was originally published by Justin Heyes-Jones. I simply refactored it to use a simple pure-virtual interface to bind with your own application. http://www.amillionpixels.us/FastAstar.h http://www.amillionpixels.us/FastAstar.cpp This thing is really quite fast. As far as generating a nav-mesh, my algorithm is holding up well. I can send you a new source code drop if you want. I'm waiting to publish it online until the AI Wisdom 4 book comes out though. John -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Pierre Terdiman Sent: Tuesday, August 28, 2007 9:28 AM To: Game Development Algorithms Subject: Re: [Algorithms] Enemy cover algorithms Hi John, > Why not just add 'cover' as a heuristic in your Astar search? There's an > enormous amount of raycasting bandwidth available in your collision code so > it doesn't seem like it would be that big of a problem to add to the search. That's a good idea, actually. Hmmm, I'm currently using PathEngine so the actual pathfinder / A* code is in a black box, but I might drop it soon anyway (replacing it with your AI Wisdom article, actually). I might very well try the cover stuff at the same time. Hmmm. Not the answer I expected but that's an interesting twist.... - Pierre ------------------------------------------------------------------------- This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Emmanuel D. <lo...@fr...> - 2007-08-28 15:00:42
|
Maybe kynogon's technology description might give you some ideas (http://www.kynogon.com/products/technology/index.html). At the GCDC I interviewed the Sales Manager of Kynogon and he was kind enough to demo me their Kynapse AI middleware, and of their demo ("Team Hide" - here: http://www.kynogon.com/products/demos/index.html) does just what you want. They appear to generate some additional information when they process the environment to create the path data. This information can then be used to manage perceptions (they have a whitepaper about that subject (http://www.kynogon.com/images-blog/Documents/WPG1Perception.pdf); their "large scale AI" whitepaper also contains some additional information (http://www.kynogon.com/images-blog/Documents/WPG3large_scale_ai.pdf)). Unfortunately, it seems that their preprocessing step requires some additional effort from the designer (it seems that he still need to mark some regions to make the whole thing work). Well, I'm not of great help, but maybe you can spot some ideas here. -- .Emmanuel Deloget .Website: http://www.emmanueldeloget.com .Software Architect @ Amesys .News Team Manager @ GameDev.Net Selon Pierre Terdiman <pte...@ag...>: > Hi John, > > > Why not just add 'cover' as a heuristic in your Astar search? There's an > > enormous amount of raycasting bandwidth available in your collision code > so > > it doesn't seem like it would be that big of a problem to add to the > search. > > That's a good idea, actually. Hmmm, I'm currently using PathEngine so the > actual pathfinder / A* code is in a black box, but I might drop it soon > anyway (replacing it with your AI Wisdom article, actually). I might very > well try the cover stuff at the same time. Hmmm. Not the answer I expected > but that's an interesting twist.... > > - Pierre |
From: Jason H. <jas...@di...> - 2007-08-28 22:04:21
|
Pierre Terdiman wrote: > That's a good idea, actually. Hmmm, I'm currently using PathEngine so the > actual pathfinder / A* code is in a black box, but I might drop it soon > anyway (replacing it with your AI Wisdom article, actually). I might very > well try the cover stuff at the same time. Hmmm. Not the answer I expected > but that's an interesting twist.... > > > Sorry to plug my own tech, but I've been working on a middleware pathfinding solution based on a navigation mesh. It's pretty fast, good on memory, yadda yadda. The way I set it up is so that the A* search is driven by callbacks so the user can apply any heuristic they choose for a given transition from one triangle in the mesh to another, and each transition has a set of flags that indicate the kind of motion required to use it. This makes possible transitions to spaces that are accessible only by jumps, or crawling on the walls and ceiling, or flying or whatever. The implementation I put in for a licensee stores a set of preferences for the actor, so an entity that has multiple motion types available can score them differently based on their current status or emotional state. So, to provide for cover points, it would be possible to indicate transitions to using a 'cover' motion where the cost for going into cover would be fairly negative, which means the transition is extremely good for the player... while an actor is not under fire, the preference for cover would be set to 0.0f, so those transitions would not be considered. But under fire, it might be ramped way up to 1.0f or higher, increasing the likelihood of taking that as the destination. Of course, the user callback handles the details of this, so custom data could be inspected instead. Hope that gives some ideas, JH www.dirtybitsoftware.com |
From: Sebastian S. <seb...@gm...> - 2007-08-28 16:32:15
|
On 28/08/07, Pierre Terdiman <pte...@ag...> wrote: > Hi guys, > > I'm going back to some AI stuff and I'm wondering about cover algorithms for > NPCs in a typical FPS / shooting game. > > Basically I would like my NPCs to run for cover in a realistic way when they > get shot at. They should know where to potentially hide, and what place is > the best hiding spot depending on the player's position. > > I have a game level exported from MAX, pretty much a polygon soup as far as > rendering & collision is concerned. There's a 2D navigation mesh for > path-finding, in case it matters. > > I'm wondering how to automatically detect "good" places to hide, and how to > do it cheaply (of course). Any experience with this, guys? I have a bunch of > ideas about how to implement "something", but it doesn't hurt asking if > there's a well-known standard solution to the problem. > A random idea: I'm asuming you have some sort of grid or node based graph of your world so you can actually refer to locations somehow. Start off by generating decent cover points e.g. using some simple heuristic such as how large portion of the sphere around the node hits an object within 2m or so. Then produce a score for how well each cover point can attack other cover points (note that it's possible for A to have a high score w.r.t. B, while B has a low score w.r.t. A - consider sitting behind cover on high ground so that only your head pops up): * How well can I fire at the other cover points while crouching * How well can I fire at the other cover points while crouching if they are standing. * How well can I fire at the other cover points while standing if they are crouching. * How well can I fire at the other cover points while standing if they are standing. Then you'd iterate over and over to compute the overall "cover score", by weighting the above scores by the current overall cover score of the other nodes (being able to attack "good cover" is better than being able to attack bad cover), and also taking into account what scores they have against you (negative weights, naturally). Hopefully "good" cover points (other points can't hit you very well, but you can hit other points very well) will soon bubble towards the top of the list. You could also prune off bad cover points after a few iterations to speed things up if needed. And obviously you would only consider cover points that are within shooting range and aren't completely occluded (that pruning can be done up front). Use ray tracing against some sort of average "actor volume" for crouching/standing and shoot off a bunch of random rays to find the score for each (where the origin is at "eye height" for the shooter), and store the results in an interaction matrix (you can fill this once and reuse it). Sebastian -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 |
From: Dan G. <dan...@gm...> - 2007-08-28 23:28:26
|
On 8/28/07, Pierre Terdiman <pte...@ag...> wrote: > I'm wondering how to automatically detect "good" places to hide, and how to > do it cheaply (of course). Any experience with this, guys? I have a bunch of > ideas about how to implement "something", but it doesn't hurt asking if > there's a well-known standard solution to the problem. Pierre, Have you seen the GDC presentation by the guys that implemented the tactical AI for Killzone? www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf cheers DanG -- Dan Glastonbury, Dan dot Glastonbury at gmail dot com `Pour encourjay lays ortras' |
From: Christopher K. <ck...@ir...> - 2007-08-29 16:09:15
|
In SWAT 4 we had a dynamically-generated cover system based on objects that were explicitly flagged as "potential cover". Basically, when an AI wanted to run for cover, the game would grab the player's position and then, treating the AI as a cylinder, extrude a "cover frustum" from the player's point of view. It's pretty much the same concept as shadow frustum extrusion. To make it look good we added a little bit of special support to the AI so that when running inside the cover frustum they would try to choose a point that would put them in full cover while also allowing them to shoot at the player if they leaned to one side. Additionally, AIs knew whether or not they had to crouch to take advantage of a particular cover frustum. Since AIs knew when they wanted to be in cover, and when they lost their cover, a nice side effect was that the system supported moving cover (like having an AI walk behind a rolling barrel) "for free", though our designers never used this functionality. Though in general the system was simple enough to run fast in even a naive implementation, to minimize hitches we limited the game to 3 or 4 pieces of cover per room, cached cover frustums, and only updated them when the player moved a reasonable amount. We also greatly simplified the extrusion process -- instead of using raw geometry I think we just used the bounding box of the mesh by default and optionally allowed artists to attach a hand-modeled "cover box" to the mesh if they wanted to be more precise. To be honest though, in hindsight it's not clear whether it was a good decision to spend time adding a dynamic cover system in a game where combat was decisive and usually concluded in a matter of seconds. I don't think players were really aware of its presence -- but it sure was nifty when it worked! -chris Pierre Terdiman wrote: > Hi guys, > > I'm going back to some AI stuff and I'm wondering about cover algorithms for > NPCs in a typical FPS / shooting game. > > Basically I would like my NPCs to run for cover in a realistic way when they > get shot at. They should know where to potentially hide, and what place is > the best hiding spot depending on the player's position. > > I have a game level exported from MAX, pretty much a polygon soup as far as > rendering & collision is concerned. There's a 2D navigation mesh for > path-finding, in case it matters. > > I'm wondering how to automatically detect "good" places to hide, and how to > do it cheaply (of course). Any experience with this, guys? I have a bunch of > ideas about how to implement "something", but it doesn't hurt asking if > there's a well-known standard solution to the problem. > > - Pierre > > |
From: Eric H. <eri...@gm...> - 2007-08-24 14:24:03
|
Juhana Sadeharju wrote: > Hello. I copied the ray/triangle intersection routine from > Real-Time Rendering book. When I choosed the epsilon to be > 0.0001, a lot of triangles became skipped. Many of the > skipped triangles are facing the camera. Strange. > Not sure what this problem is, I passed your note on to Tomas. I'm just about to go on vacation, but thought I'd point at this page: http://jgt.akpeters.com/papers/LofstedtAkenineMoller05/, which has code for a whole test framework and a (huge) variety of ray/triangle intersectors that a student of Tomas' tested out. Eric |
From: Pierre T. <pte...@ag...> - 2007-08-28 14:02:51
|
> Things would probably be different for a FPS, but I guess a bunch of > "good cover spots" all over the map would probably be the best (placed > by LDs or automatically generated). But that's pretty much my question: how do you automatically generate this? I don't really feel like manually locating good "cover points" in an editor, because: a) well, it's tedious :) b) maybe I'm thinking too much about this, but it looks to me that there's no obvious "cover points" - any point can be used. For example consider a pillar in the middle of an otherwise empty room. I could mark the area around the pillar as "good cover point" (and even for that, it's unclear where the "points" are located), but in reality any point in the shadow of the pillar (as seen from the player, as if the player was a lightsource) is actually "covered". So it's useless to manually locate cover points in an editor, since all available points in the room are potentially good, depending on where the player is. So I was more asking for algorithms like that (say computing a shadowed area and finding a good spot within that area, I don't know). Maybe it's too complicated, nobody does that, and everbody actually places some cover points around the edges of pillars or something :) Hmmm... - Pierre |
From: Anders N. <ja...@an...> - 2007-08-28 14:44:54
|
Maybe marking the region around a pillar as "interesting" and then adding that into your "cover"-heuristic as well might produce even more... interesting behaviour. The rationale here would be that interesting spots are chosen over uninteresting when there are multiple "cover"-spots to chose from. Lowering the interesting-factor on crates might improve the fun-factor of your AI =) Anders Nilsson. 2007/8/28, Pierre Terdiman <pte...@ag...>: > > > Things would probably be different for a FPS, but I guess a bunch of > > "good cover spots" all over the map would probably be the best (placed > > by LDs or automatically generated). > > But that's pretty much my question: how do you automatically generate > this? > > I don't really feel like manually locating good "cover points" in an > editor, > because: > > a) well, it's tedious :) > > b) maybe I'm thinking too much about this, but it looks to me that there's > no obvious "cover points" - any point can be used. For example consider a > pillar in the middle of an otherwise empty room. I could mark the area > around the pillar as "good cover point" (and even for that, it's unclear > where the "points" are located), but in reality any point in the shadow of > the pillar (as seen from the player, as if the player was a lightsource) > is > actually "covered". So it's useless to manually locate cover points in an > editor, since all available points in the room are potentially good, > depending on where the player is. > > So I was more asking for algorithms like that (say computing a shadowed > area > and finding a good spot within that area, I don't know). Maybe it's too > complicated, nobody does that, and everbody actually places some cover > points around the edges of pillars or something :) > > Hmmm... > > - Pierre > > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Marc H. <ma...@gm...> - 2007-08-28 18:56:17
|
John's method works really well. You can combine this with some animation to hide the expensive A* with the raycasts. When the NPC starts taking fire, do one of a few moves: 1. Go to one knee and return fire. 2. Dive prone and return fire. 3. Go into a sighted stance and return fire walking backwards slowely. This should give you a second or two to spread the load of doing an A* search with an expensive heuristic. As NPC's find cover, queue up some AI yells of something like: "There's cover over here" or "Fall back", or somesuch. Then reuse the NPC's searches that yelled to narrow your searches for cover nearby their find. Then when you find a good open spot, you just need to do a cheap A* to find the path to that location. On 8/28/07, Pierre Terdiman <pte...@ag...> wrote: > Hi guys, > > I'm going back to some AI stuff and I'm wondering about cover algorithms for > NPCs in a typical FPS / shooting game. > > Basically I would like my NPCs to run for cover in a realistic way when they > get shot at. They should know where to potentially hide, and what place is > the best hiding spot depending on the player's position. > > I have a game level exported from MAX, pretty much a polygon soup as far as > rendering & collision is concerned. There's a 2D navigation mesh for > path-finding, in case it matters. > > I'm wondering how to automatically detect "good" places to hide, and how to > do it cheaply (of course). Any experience with this, guys? I have a bunch of > ideas about how to implement "something", but it doesn't hurt asking if > there's a well-known standard solution to the problem. > > - Pierre |
From: Brian G. <bri...@gm...> - 2007-08-28 19:03:26
|
On 8/28/07, Marc Hernandez <ma...@gm...> wrote: > > John's method works really well. > > You can combine this with some animation to hide the expensive A* > with the raycasts. When the NPC starts taking fire, do one of a few > moves: > 1. Go to one knee and return fire. > 2. Dive prone and return fire. > 3. Go into a sighted stance and return fire walking backwards slowely. > > This should give you a second or two to spread the load of doing an > A* search with an expensive heuristic. > > As NPC's find cover, queue up some AI yells of something like: > "There's cover over here" or "Fall back", or somesuch. Then reuse the > NPC's searches that yelled to narrow your searches for cover nearby > their find. Then when you find a good open spot, you just need to do > a cheap A* to find the path to that location. This not only frees up the time, but it's also realistic. While some people may be Steven Seagal enough to calmly move to cover, most people, even soldiers, react to fire by hitting the deck or diving away from the shooting, then assuring proper cover. Of course, if we're talking about Joe PublicNPC, he is probably just going to stand there and scream and tense up, but that wouldn't make for much of a game. -- Brian P. Gefrich Microsoft MVP - PC Games http://www.notasenator.com/blog AVSIM Forum Administrator http://www.avsim.com |
From: Adrian B. <ad...@gm...> - 2007-09-08 22:26:21
|
It's not always true that the entire shadow counts. If you're just looking for immediate safety, then maybe. However, what if the enemy moves to the side a bit, the farther away from the cover you are, the farther you have to move to get back in. Also, being far away, might allow the enemy to run up and take the other side of the cover, essentially eliminating its usefulness to the NPC. The same works visa versa for if you're up against cover, it forces the enemy to move a lot to try and get to you/take it. Why not just go with authoring + auto-generation. There are bound to be many cases where auto-generating cover is easy (e.g. pillar you mention). But there are also bound to be places it will miss or aren't static (cars, movable boxes, broken mini wall where only some sections work). Adrian On 8/28/07, Pierre Terdiman <pte...@ag...> wrote: > > Things would probably be different for a FPS, but I guess a bunch of > > "good cover spots" all over the map would probably be the best (placed > > by LDs or automatically generated). > > But that's pretty much my question: how do you automatically generate this? > > I don't really feel like manually locating good "cover points" in an editor, > because: > > a) well, it's tedious :) > > b) maybe I'm thinking too much about this, but it looks to me that there's > no obvious "cover points" - any point can be used. For example consider a > pillar in the middle of an otherwise empty room. I could mark the area > around the pillar as "good cover point" (and even for that, it's unclear > where the "points" are located), but in reality any point in the shadow of > the pillar (as seen from the player, as if the player was a lightsource) is > actually "covered". So it's useless to manually locate cover points in an > editor, since all available points in the room are potentially good, > depending on where the player is. > > So I was more asking for algorithms like that (say computing a shadowed area > and finding a good spot within that area, I don't know). Maybe it's too > complicated, nobody does that, and everbody actually places some cover > points around the edges of pillars or something :) > > Hmmm... > > - Pierre > > > ------------------------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. > Still grepping through log files to find problems? Stop. > Now Search log events and configuration files using AJAX and a browser. > Download your FREE copy of Splunk now >> http://get.splunk.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Sebastian L. <del...@gm...> - 2007-09-27 02:44:47
|
SGksCgpJIHNhdyBzb21lIG9mIHRoaXMgQUkgc3R1ZmYgaW4gdGhlIHNvdXJjZSBvZiBQT0Rib3Rz ICh0aGUgYmVzdHMgYm90cyBmb3IgdGhlCmNsYXNzaWMgSGFsZi1MaWZlKS4KSSBrbm93IHlvdSBt aWdodCBiZSBsYXVnaGluZyBidXQgdGhleSd2ZSBpbmNyZWRpYmxlIGJlaGF2aW9ycyBkZXBlbmRp bmcgb24KdGhlaXIgb3duIHN0YXRzIChsaWtlIGhlYWx0aCwgYW1tbywgZXRjKS4KCldoYXQgRW1p bGUgS3JvZWdlciBzYWlkIGlzIHdoYXQgUE9EYm90cyB1c2U6CgoiLi4uQmFzaWNhbGx5LCBlYWNo IHBpZWNlIG9mIGNvdmVyIHdvdWxkICJnZW5lcmF0ZSIgZ29vZCAiY292ZXIgc3BvdHMiCmFyb3Vu ZCBpdC4uLi4iCgpBbmQgSSBwZXJzb25hbGx5IHVzZSB0aGlzIHRvIG15IG93biBnYW1lcy4KCkhv cGUgdGhpcyB3aWxsIGJlIHVzZWZ1bCBmb3IgeW91ciBnYW1lLgoKUmVnYXJkcywKCk9uIDkvOC8w NywgQWRyaWFuIEJlbnRsZXkgPGFkcnVhYkBnbWFpbC5jb20+IHdyb3RlOgo+Cj4gSXQncyBub3Qg YWx3YXlzIHRydWUgdGhhdCB0aGUgZW50aXJlIHNoYWRvdyBjb3VudHMuICBJZiB5b3UncmUganVz dAo+IGxvb2tpbmcgZm9yIGltbWVkaWF0ZSBzYWZldHksIHRoZW4gbWF5YmUuICBIb3dldmVyLCB3 aGF0IGlmIHRoZSBlbmVteQo+IG1vdmVzIHRvIHRoZSBzaWRlIGEgYml0LCB0aGUgZmFydGhlciBh d2F5IGZyb20gdGhlIGNvdmVyIHlvdSBhcmUsIHRoZQo+IGZhcnRoZXIgeW91IGhhdmUgdG8gbW92 ZSB0byBnZXQgYmFjayBpbi4gIEFsc28sIGJlaW5nIGZhciBhd2F5LCBtaWdodAo+IGFsbG93IHRo ZSBlbmVteSB0byBydW4gdXAgYW5kIHRha2UgdGhlIG90aGVyIHNpZGUgb2YgdGhlIGNvdmVyLAo+ IGVzc2VudGlhbGx5IGVsaW1pbmF0aW5nIGl0cyB1c2VmdWxuZXNzIHRvIHRoZSBOUEMuICBUaGUg c2FtZSB3b3Jrcwo+IHZpc2EgdmVyc2EgZm9yIGlmIHlvdSdyZSB1cCBhZ2FpbnN0IGNvdmVyLCBp dCBmb3JjZXMgdGhlIGVuZW15IHRvIG1vdmUKPiBhIGxvdCB0byB0cnkgYW5kIGdldCB0byB5b3Uv dGFrZSBpdC4KPgo+IFdoeSBub3QganVzdCBnbyB3aXRoIGF1dGhvcmluZyArIGF1dG8tZ2VuZXJh dGlvbi4gIFRoZXJlIGFyZSBib3VuZCB0bwo+IGJlIG1hbnkgY2FzZXMgd2hlcmUgYXV0by1nZW5l cmF0aW5nIGNvdmVyIGlzIGVhc3kgKGUuZy4gcGlsbGFyIHlvdQo+IG1lbnRpb24pLiAgQnV0IHRo ZXJlIGFyZSBhbHNvIGJvdW5kIHRvIGJlIHBsYWNlcyBpdCB3aWxsIG1pc3Mgb3IKPiBhcmVuJ3Qg c3RhdGljIChjYXJzLCBtb3ZhYmxlIGJveGVzLCBicm9rZW4gbWluaSB3YWxsIHdoZXJlIG9ubHkg c29tZQo+IHNlY3Rpb25zIHdvcmspLgo+Cj4gQWRyaWFuCj4KPiBPbiA4LzI4LzA3LCBQaWVycmUg VGVyZGltYW4gPHB0ZXJkaW1hbkBhZ2VpYS5jb20+IHdyb3RlOgo+ID4gPiBUaGluZ3Mgd291bGQg cHJvYmFibHkgYmUgZGlmZmVyZW50IGZvciBhIEZQUywgYnV0IEkgZ3Vlc3MgYSBidW5jaCBvZgo+ ID4gPiAiZ29vZCBjb3ZlciBzcG90cyIgYWxsIG92ZXIgdGhlIG1hcCB3b3VsZCBwcm9iYWJseSBi ZSB0aGUgYmVzdCAocGxhY2VkCj4gPiA+IGJ5IExEcyBvciBhdXRvbWF0aWNhbGx5IGdlbmVyYXRl ZCkuCj4gPgo+ID4gQnV0IHRoYXQncyBwcmV0dHkgbXVjaCBteSBxdWVzdGlvbjogaG93IGRvIHlv dSBhdXRvbWF0aWNhbGx5IGdlbmVyYXRlCj4gdGhpcz8KPiA+Cj4gPiBJIGRvbid0IHJlYWxseSBm ZWVsIGxpa2UgbWFudWFsbHkgbG9jYXRpbmcgZ29vZCAiY292ZXIgcG9pbnRzIiBpbiBhbgo+IGVk aXRvciwKPiA+IGJlY2F1c2U6Cj4gPgo+ID4gYSkgd2VsbCwgaXQncyB0ZWRpb3VzIDopCj4gPgo+ ID4gYikgbWF5YmUgSSdtIHRoaW5raW5nIHRvbyBtdWNoIGFib3V0IHRoaXMsIGJ1dCBpdCBsb29r cyB0byBtZSB0aGF0Cj4gdGhlcmUncwo+ID4gbm8gb2J2aW91cyAiY292ZXIgcG9pbnRzIiAtIGFu eSBwb2ludCBjYW4gYmUgdXNlZC4gRm9yIGV4YW1wbGUgY29uc2lkZXIKPiBhCj4gPiBwaWxsYXIg aW4gdGhlIG1pZGRsZSBvZiBhbiBvdGhlcndpc2UgZW1wdHkgcm9vbS4gSSBjb3VsZCBtYXJrIHRo ZSBhcmVhCj4gPiBhcm91bmQgdGhlIHBpbGxhciBhcyAiZ29vZCBjb3ZlciBwb2ludCIgKGFuZCBl dmVuIGZvciB0aGF0LCBpdCdzIHVuY2xlYXIKPiA+IHdoZXJlIHRoZSAicG9pbnRzIiBhcmUgbG9j YXRlZCksIGJ1dCBpbiByZWFsaXR5IGFueSBwb2ludCBpbiB0aGUgc2hhZG93Cj4gb2YKPiA+IHRo ZSBwaWxsYXIgKGFzIHNlZW4gZnJvbSB0aGUgcGxheWVyLCBhcyBpZiB0aGUgcGxheWVyIHdhcyBh IGxpZ2h0c291cmNlKQo+IGlzCj4gPiBhY3R1YWxseSAiY292ZXJlZCIuIFNvIGl0J3MgdXNlbGVz cyB0byBtYW51YWxseSBsb2NhdGUgY292ZXIgcG9pbnRzIGluCj4gYW4KPiA+IGVkaXRvciwgc2lu Y2UgYWxsIGF2YWlsYWJsZSBwb2ludHMgaW4gdGhlIHJvb20gYXJlIHBvdGVudGlhbGx5IGdvb2Qs Cj4gPiBkZXBlbmRpbmcgb24gd2hlcmUgdGhlIHBsYXllciBpcy4KPiA+Cj4gPiBTbyBJIHdhcyBt b3JlIGFza2luZyBmb3IgYWxnb3JpdGhtcyBsaWtlIHRoYXQgKHNheSBjb21wdXRpbmcgYSBzaGFk b3dlZAo+IGFyZWEKPiA+IGFuZCBmaW5kaW5nIGEgZ29vZCBzcG90IHdpdGhpbiB0aGF0IGFyZWEs IEkgZG9uJ3Qga25vdykuIE1heWJlIGl0J3MgdG9vCj4gPiBjb21wbGljYXRlZCwgbm9ib2R5IGRv ZXMgdGhhdCwgYW5kIGV2ZXJib2R5IGFjdHVhbGx5IHBsYWNlcyBzb21lIGNvdmVyCj4gPiBwb2lu dHMgYXJvdW5kIHRoZSBlZGdlcyBvZiBwaWxsYXJzIG9yIHNvbWV0aGluZyA6KQo+ID4KPiA+IEht bW0uLi4KPiA+Cj4gPiAtIFBpZXJyZQo+ID4KPiA+Cj4gPgo+IC0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KPiA+ IFRoaXMgU0YubmV0IGVtYWlsIGlzIHNwb25zb3JlZCBieTogU3BsdW5rIEluYy4KPiA+IFN0aWxs IGdyZXBwaW5nIHRocm91Z2ggbG9nIGZpbGVzIHRvIGZpbmQgcHJvYmxlbXM/ICBTdG9wLgo+ID4g Tm93IFNlYXJjaCBsb2cgZXZlbnRzIGFuZCBjb25maWd1cmF0aW9uIGZpbGVzIHVzaW5nIEFKQVgg YW5kIGEgYnJvd3Nlci4KPiA+IERvd25sb2FkIHlvdXIgRlJFRSBjb3B5IG9mIFNwbHVuayBub3cg Pj4gIGh0dHA6Ly9nZXQuc3BsdW5rLmNvbS8KPiA+IF9fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fCj4gPiBHREFsZ29yaXRobXMtbGlzdCBtYWlsaW5nIGxpc3QK PiA+IEdEQWxnb3JpdGhtcy1saXN0QGxpc3RzLnNvdXJjZWZvcmdlLm5ldAo+ID4gaHR0cHM6Ly9s aXN0cy5zb3VyY2Vmb3JnZS5uZXQvbGlzdHMvbGlzdGluZm8vZ2RhbGdvcml0aG1zLWxpc3QKPiA+ IEFyY2hpdmVzOgo+ID4KPiBodHRwOi8vc291cmNlZm9yZ2UubmV0L21haWxhcmNoaXZlL2ZvcnVt LnBocD9mb3J1bV9uYW1lPWdkYWxnb3JpdGhtcy1saXN0Cj4gPgo+Cj4gLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LQo+IFRoaXMgU0YubmV0IGVtYWlsIGlzIHNwb25zb3JlZCBieTogTWljcm9zb2Z0Cj4gRGVmeSBh bGwgY2hhbGxlbmdlcy4gTWljcm9zb2Z0KFIpIFZpc3VhbCBTdHVkaW8gMjAwNS4KPiBodHRwOi8v Y2xrLmF0ZG10LmNvbS9NUlQvZ28vdnNlMDEyMDAwMDA3MG1ydC9kaXJlY3QvMDEvCj4gX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KPiBHREFsZ29yaXRobXMt bGlzdCBtYWlsaW5nIGxpc3QKPiBHREFsZ29yaXRobXMtbGlzdEBsaXN0cy5zb3VyY2Vmb3JnZS5u ZXQKPiBodHRwczovL2xpc3RzLnNvdXJjZWZvcmdlLm5ldC9saXN0cy9saXN0aW5mby9nZGFsZ29y aXRobXMtbGlzdAo+IEFyY2hpdmVzOgo+IGh0dHA6Ly9zb3VyY2Vmb3JnZS5uZXQvbWFpbGFyY2hp dmUvZm9ydW0ucGhwP2ZvcnVtX25hbWU9Z2RhbGdvcml0aG1zLWxpc3QKPgoKCgotLSAKjaGOgY2B oY6hgYGNoY6BoQpTZWJhc3RpYW4gSmF2aWVyIEx1Y2FzClByb2dyYW1tZXIgJiBHdWl0YXIgSGVy bwo= |
From: <olo...@gm...> - 2007-09-27 19:23:27
|
Hi, I think the killzone ai did this in a nice way by pre-calculating the cover in different directions for each node in the navigation graph. This provides not only means for taking cover, but also to find paths in cover from the enemy or to predict where an enemy can leave it's cover. The technique is discussed in detail here: http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf (please forgive me if this has already been discussed in this thread, I just joined recently and haven't followed it from the beginning.) Regards, Olof |