Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Timkin

Environment analysis... outputs and algorithms

This topic is 5206 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi folks, This thread is sort of a fork from the ''AI using cover'' thread. It was briefly discussed in that thread that both FPS and RTS genres required environment (terrain) analysis to enable AI to make use of their environment for better game play. For example, in an FPS environment, a bot might used the hidden region behind an objects as cover, or the specific corner of a room to maximise arc of fire coverage of all doors into the room. In an RTS, an army general might select a given hillside on which to deploy his units, so as to maximise their effectiveness in combat. These thoughts led me to the conclusion that it would be very useful to have the ability to process the world model - in real time - to obtain information useful to the AI agents deployed in these domains. For example, in the FPS genre, obtaining a visual representation from the point of view of a specific player or bot could be used to deduce locales for cover and concealment. The interaction of sound and the walls of the environment could be turned into a sound map for the bot. In RTS, tactical terrain analysis can, to some extent, be handled with Potential Fields (Influence Maps). However, these are typically handled on a case by case basis and highly depend on the game design. What I am thinking of is a generic processing capability (that might be configurable to specific genres) that can process the world model in real time and extract important sensory information for the AI agents acting in this world. I specifically want to take the game designers out of the loop, so the use of embedded tags in the world model denoting good locations for cover, or the emmission of sensory signals (a la Sims) is not what I''m looking for. If you have thoughts, comments or suggestions as to the sorts of input and output formats of said data, or algorithms to compute it, I''d really like to hear them. While you''re considering this, ask yourself how generic your idea is and whether it would work on a piece of hardware optimised for processing world models in real time. Cheers and thanks, Timkin

Share this post


Link to post
Share on other sites
Advertisement
Hi Timkin,
I am VERY inexperienced with AI but do enjoy reading up on the subject.
I enjoyed...
http://terra.cs.nps.navy.mil/www.movesinstitute.org/Theses/MorganThesis.pdf
with summarising .ppt on this page... http://online.cs.nps.navy.mil/www.movesinstitute.org/openhouse2003-wslides.html
The paper mentions depth maps.
There is an article, Using a Spatial Database for Runtime Spatial Analysis, in AI Programming Wisdom 2 by Paul Tozour which discusses the combination of data maps.
The use of 'Influence' maps for terrain analysis seems to be getting more popular. Is this true?

P.S. There are a few of the Monterey Naval PostGraduate papers which are very interesting but never seem to be quoted. What is the relationship between Military AI and Games AI people?


P.P.S. Nice to see William Van Der Sterren in the other post.
It was after reading 'Terrain Reasoning in 3D Action Games' that I began to believe I CAN write AI for my bedroom coded games.
I still haven't but at least I now believe I can ;-)

P.P.P.S Just realised this should have gone in the other thread.

[edited by - TonyG on April 23, 2004 6:01:18 AM]

Share this post


Link to post
Share on other sites
Timkin, I think Paul Tozour covers a lot of what you have in mind using his Spatial Database for Runtime Spatial Analysis. It''s an article in AI Game Programming Wisdom 2.

There are lots of layers of information associated with the terrain, and each is computed with a different algorithm, statically or dynamically. The agent then combines the layers to get a customized desirability map in realtime...

I was thinking of using potential fields for coding up a game of hide and seek. The agents could use local steepest ascent to get to a place that''s dark and hidden.

Seems like an ideal combination!

Alex


AiGameDev.com: Artificial Intelligence from Theory to Fun!

Share this post


Link to post
Share on other sites
*I wonder if my Bob Scott summoning spell works still?*

Empire Earth did some really neat stuff with layered influence maps, but also did nifty tricks with pathfinding. By running the pathfinding algo a good number of times and tossing them into a terrain influence map, they could identify choke points quite readily. Some of the methods are in the Gems/Wisdom books... my shoulder really hurts now or I would reach up above my desk and find them.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
I''ve always thought that if the game world uses pre-defined objects (such as "crate" or "table"), it might be useful to store information about that object''s cover characteristics with the object itself. I doubt this would solve the problem, but it seems to me it could form part of the solution, and it would probably be pretty efficient (e.g. one instance of the metadata applies to all instances of the object).

On the other hand, I don''t know anything about the subject, and it does strike me as an obvious concept that someone would have already come up with.

Share this post


Link to post
Share on other sites
I'm not sure exactly how our terrain analysis would be able to help in a "find cover" situation... As Dave pointed out, we used it do define choke points (for tower/mine placement and guard spots) and forests (for hiding and wall building). We also had political influence maps for defining things like where citizens could safely walk.

Except for the latter, most layers were precomputed. Occasionally (when there was free CPU), we would reprocess small sections of the map (like a de-forested forest or when a wall was built), but this was not at all "real-time". We were satisfied that the data was "current enough" for our purposes.

I know Timkin doesn't want tags placed by the level designer, but I can't think of a better way than to label objects as "potential hiding spots". Once these tagged objects are noticed, some of the more expensive ideas (like raycasting from the player's point of view) could become cheap enough.

Bob Scott
AI Designer/Programmer
Stainless Steel Studios



[edited by - eeaiguy on April 23, 2004 11:20:09 AM]

Share this post


Link to post
Share on other sites
One problem with tagging is that it is not dynamic. As we move toward more and more physics in games, we will have more moveable objects and more dynamic environments. A stack of crates may be a good hiding place. A tumbled stack of crates (now just individual crates lying about) would likely not be. If the designer tags the stack as a good hiding place, it would need to change so that the individual crates are NOT good hiding places. What if only PART of the stack falls? What if some of them fall onto each other or close to each other to allow prone hiding?

The pre-set points are a good fix for now because the environment design allows it. When we grow out of the current static environment model, we will need to adapt to it.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
(This may be too far off topic, so I will keep this post short)

Dave,

That seems like it borders on the 'how do we do dynamic pathing' topic. While there are solutions based on using some sort of 'local pathing' (force based?), this seems to ignore the possibility that a large obstruction that totally when renders a space totally blocked.

Perhaps these could be addressed by the same sort of algorithm that determines which falling objects are considered cover.

[edited by - BrianL on April 23, 2004 2:49:32 PM]

Share this post


Link to post
Share on other sites
Getting back to analysis of the environment, one needs to look at a specific problem in the same way that people do. With regard to EE''s terrain analysis for choke points, they used algorithms that we understand... that is, "what is a highly traveled area compared to the areas around it?" That makes sense to us. With regard to cover, the question becomes "what is a large enough item for me to hide behind?" Therefore, it would seem the first calculation that would need to be done would be of object volume, followed by object density. After all, that''s how WE do it, right? That''s even how level designers would make their decisions about which items to flag as hiding spots.

The situation comes down to world descriptors. If we include either ways to represent or ways to calculate such things as size and density, then we can use those in our calculations. For the most part, many of these parameters are not needed in static world games. However, they will be needed in dynamic world games and can be leveraged by us. Alternately, we can insist that such parameters be included specifically so that we CAN use them.

You can''t ask our agents to process the world intelligently until you give them the tools to make those decisions with.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
First up, thanks for the replies and the interesting discussion. One point though; influence maps are not generic enough for the sort of analysis I''m looking at. They may be applicable to a wide range of scenarios, however they are the sort of algorithm you would expect to find in an AI middleware solution, rather than an environmental analysis setting. Sure, there''s overlap, but what I''m more interested is the fundamental issue of analysing the raw domain model and creating useful data (from just the world model) that a Game AI agent can use to make tactical decisions (This has strong implications beyond games).

Alex, I''ll definitely look at those references... it may not be until next weekend though... I have a paper to write and a funding proposal, all by next Friday 8(.

Bob, I understand that tagging the environment at design stage ''works'', but as Dave said, it relies on the environment not changing... and not all environments are designed (just most of those in the Games industry)!

Dave, I like the idea of your last post, however I don''t necessarily agree that we make decisions about cover based on size and density (at least, not just on those). We might use those attributes to perform a rough filtering of the domain to choose candidate areas. I think though, that once we have a list of candidates, that we probably hypothesise as to the ''goodness'' of the location based on what the enemy might do and what we''re trying to achieve.E.g. "Can an enemy who walks through door X see me behind crate Y?" Such decisions though are left to the AI itself...

I had an idea last year (or what is the year before) abou turning visual (or other sensory) representations of an environment into a semantic representation, so that scene analysis could result in scene descriptors which could then be used in an appropriate AI in whatever way was desired. So, for example, a description of the connectivity of rooms and corridors, along with doors (and their states) could be used in a pathfinding algorithm. Or, the same information could be used to plan escape routes from a room, or predict enemy entry points. I''m not really interested in how the information gets used, but this was one idea along the lines of environmental analysis that I had. Others we more basic: perform image understanding to identify objects in a field of view (2D projection of 3D space) and then pass those objects off to the AI for classification and action.

I hope this makes my intentions/desires a little more clear.

Cheers,

Timkin

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!