Archived

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

Timkin

Environment analysis... outputs and algorithms

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
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
quote:
Original post by Timkin
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).
[...]
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.


Most game AI is designed the other way around: data isn''t collected/created until there is an AI decision with (1) a need for it, and (2) a perceivable consequence in the game. Superfluous data just adds cost and time to content creation, and to running and testing the game.

For military simulations automated environment analysis is more relevant. Did you already read the following paper:
Applying Perceptually Driven Cognitive Mapping To Virtual Urban Environments, Hill, Han, van Lent, 2002
url: http://www.ict.usc.edu/publications/IAAI2002rHill.pdf

William



Share this post


Link to post
Share on other sites
quote:
Original post by Timkin
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...

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.

Again, 2 years ago I was in a tutorial at GDC where John Laird was showing us how his SOAR bots were processing the map this way. There was the example I gave in the other thread about how they picked the "out of sight" corner of the room to camp in. Also, there was an example of how the bot was following someone... it knew that the player had gone into a dead end, knew that there was powerup in the room at the end, figured that the player was getting the powerup, and calculated how quickly the player would reappear out of that hallway. It camped in a good spot and prepared to fire, knowing when the player "should" return. Smart stuff.

quote:
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.

If you truly mean "identify", that makes for some massive processing of data against some sort of mapping algo like a neural network to be able to say "I see that thing over there and it looks a lot like a ..... ". That would be a bitch. If you mean identify in terms of just categorize the sort of thing we are looking at, then we have a little more wiggle room - but any parameters we use would, again, have to be included in (or derivable from) the world definition.

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

Share this post


Link to post
Share on other sites
It seems like this would fall into the pattern recognition domain of AI. Of which, algorithims associated with data mining might also be useful, to quantify, coallate, and massage the data into a format the pattern matcher can use.

Tactics are a well defined body of knowledge which can be codified into an expert system. However such expert systems normally operate upon high level command queries, which might be asking too much of the AI to operate at. Perhaps creating a bridge between the expert system and the AI. A sort of translator program. Translations transform information from one form into antoher. I wonder if there is a branch of mathmatics which deal with information transformation similar to how energy transforms in therodynamics, perhaps compression theroy.

The way I would approach this would be segment the problem into 3 parts. First, an information filter which tranfroms observable and stated information into a digestable form for the next stage, using any data minning, and pattern matching techniques you wish. The 2nd component creates a model of the obserations, which then is used to guide a directed search of potential model space. The search can be by either forward or backtracking method. The 3rd element is the expert system which quantifies each search state. There is still the problem of extracting sufficent infomation from the model to feed the expert system to get an acceptable ranking for the search state. Also the issue of transforming the raw information into a digestable form to build the symantic model of the observations might be problemantic too.

Well Good Luck!

-ddn

Share this post


Link to post
Share on other sites
quote:
Original post by WilliamvanderSterren
Most game AI is designed the other way around: data isn''t collected/created until there is an AI decision with (1) a need for it, and (2) a perceivable consequence in the game.


I understand that William. However, many games have similar decision requirements, particularly within a genre such as FPS. Indeed, genres could in part be described by the sorts of decisions that needs to be made and the sorts of actions available to players and NPCs.

I think the problem in this discussion is that you guys are still thinking in terms of current games, current decisions and current methods for AI. I want to step beyond that and talk about the future of Game AI and what we might be able to achieve and how, with specific reference to environment analysis. I''m not looking for you to tell me how to implement something for current games or how someone else does it currently (like classification, or SOAR) since I know these techniques and systems very well. What I wanted was a discussion of how we might perform terrain analysis if we weren''t going to tag the environment at design stage. (Actually SOAR is capable of limited scene analysis in that it can represent 2D surfaces with lines representing boundaries. Like many SLAM (Simultaneous Localisation And Mapping systems in robotics, it can produce a 2D map floor map of an environment and use this for making spatial decisions. I want to go beyond this.)


quote:
Original post by WilliamvanderSterren
Did you already read the following paper:
Applying Perceptually Driven Cognitive Mapping To Virtual Urban Environments, Hill, Han, van Lent, 2002
url: http://www.ict.usc.edu/publications/IAAI2002rHill.pdf



I hadn''t, but I have now. This is just a slight variation on other work I have seen in this area. There was an excellent Master''s thesis last year (forgotten the author unfortunately) that looked at cognitive mapping in 3D based on light, colour and texture variations. It was designed for smaller environments than the ones being considered by Hill et al so it''s extensibility to useful environments has not been proven.

Guys, I appreciate the discussion to date. I think though, for now, Iim going to drop out of the discussion and do more research on my ideas myself. Feel free to take this thread in any direction you like, or drop it. If anyone does have any particularly good thoughts on the subject, feel free to send me an email.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Isn''t this exactly what David Morgan''s paper "ALGORITHMIC APPROACHES TO FINDING COVER IN THREE-DIMENSIONAL, VIRTUAL ENVIRONMENTS" is trying to resolve?
I''d be very interested in responses on the 3 suggested methods
and their limitations.

Share this post


Link to post
Share on other sites
''Tis a shame that the same work gets done by different people in different fields. I see this often with students studying in a military environment... there isn''t a general recognition of work done outside that environment.

That thesis covers methods that are already known and have been discussed in other publications. In particular though, it only covers the problem of finding cover. I was looking at the broader picture of analysing terrain from a tactical perspective, from finding cover to deploying armies, since the issues in each task are similar.

Thanks for the pointer though... I found another thesis from that group that was particularly interesting for another project I''m working on!

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Perhaps gamedev (or some other site) could start indexing papers people find useful, along with a short summary of why/how they are useful? Something similar to the book reviews, etc.

I try to spend 3 or 4 hours a week looking over thesis papers; I spend most of my time on siteseer. The main problem for me is that unless a paper is heavily referenced (read: 5 years old) or with very obvious merit/application, it is difficult justifying the chunk of time it will take to understand as most are redundant or too specialized.

I doubt there is a very practical way of handling this, but I can dream.

Share this post


Link to post
Share on other sites
Absolutely true. There was a project running some time ago about various code questions - I was thinking it could be easily extended.
But although the AI is a pretty strict area, in which you cannot go by the desired way without bumping into something specific, most of materials can be easily found on Google or similar.
I recently came to idea of using associative database for image object recognition, but who says it can be only used for it?
The game can be presented as features linked by some relations, and the agent task will be to figure ot the outcome.
Well, this is just the basic idea I''m now working on in free time (which I have a lot ).

Farewell.

" Do we need us? "


Ionware Productions - Games and Game Tools Development

Share this post


Link to post
Share on other sites
quote:
Original post by HellRiZZer
Absolutely true. There was a project running some time ago about various code questions - I was thinking it could be easily extended.
But although the AI is a pretty strict area, in which you cannot go by the desired way without bumping into something specific, most of materials can be easily found on Google or similar.
I recently came to idea of using associative database for image object recognition, but who says it can be only used for it?
The game can be presented as features linked by some relations, and the agent task will be to figure ot the outcome.
Well, this is just the basic idea I'm now working on in free time (which I have a lot ).

Farewell.

" Do we need us? "


Ionware Productions - Games and Game Tools Development




GOOGLE for copycat and metacat, i'm not sure but it's it deal with the same problem

however, timkim, your post look like things i'm working on isn't it??? if so then you must take care of 'topology of problem' domain, if you don't have a proper topology you may fail to have an efficient system, i'm not sure if i'm clear since i have trouble because i use my own terminology, did this make sens to you??
i'm not directly dealing with covering in my (simple) design but agent build beleif about what other agent beleif...

>>>>>>>>>>>>>>>
be good
be evil
but do it WELL
>>>>>>>>>>>>>>>

[edited by - neoshaman on April 29, 2004 10:03:23 PM]

Share this post


Link to post
Share on other sites
An old paper which might fit the dynamic analysis of terrain...
http://www.isn.ethz.ch/onlinepubli/publihouse/infosecurity/volume_3/F5/F5_index.htm
In this case we specify a region to defend against an opponent attacking from a known direction. An algorithm is used to determine what is a defensively good position in terms of cover, concealment and LOS to potentially important terrain features.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I have been reading your threads regarding finding cover since I myself am trying to make a simple hide & seek game. I have searched in vain for a good dynamic system that is simple enough for me.

I know Fast Method Marching and the Level Set Method is rather taboo in the AI field lately for it''s lack of speed, but have you considered that as an option? For quick (in relative terms) analysis of the terrain between a predator and his prey, I always thought using the FMM system based on predefined values of objects and terrain height would show ideal places to hide.

AI is rather new to me, so forgive my ineptness if I have covered something already discussed.

Share this post


Link to post
Share on other sites
I know this probably isn''t the best option, but why don''t you use an ANN to figure out how to use terrain. You could use the height of each terrain tile, location, and target location as inputs, and the network could give you a vague idea of directions to go in. I am not sure how this will work, and is something i am planning to test. Hope i helped.

Sagar Indurkhya

Share this post


Link to post
Share on other sites
There may be some interesting concepts in the Machining field, related to feature identification and extraction. The problem this field deals with is takinga design and looking for a series of actions which can feasibly manufacture an item.

To do this, it attempts to decompose the design into primitives based on the properties of machining tools. I would imagine that the structures used to do this may be similar to the data structures an AI engineer could use to define ''useful'' locations in the world.

I haven''t had enough time to look at this in depth, but this seems like it may be applicable to at least part of the problem.

Share this post


Link to post
Share on other sites
It is an interesting point how to analysis an environment into something useful to an Agent.

The approach used would depend on the constraints provided, if we assume that an agent has full world knowledge, the terrain is unchangeable and objects have relevant sensory data that an agent can access.

Then we could go with a layered approach to solve the problem.

1) Volume map - The position and size of all objects in the world is determined as well as the terrain information is processed to create the volume map which is stored a 3d dimensional binary grid with a value 0 for space and 1 for an obstacle. Since the world never changes the volume map never changes and so only has to be calculated once.

2) Function map - The objects in the world contain functional information that determines how they can be used, for example a ladder would have the climbable functionality. The function map is generated based on the functionality of the objects and stored as 3d dimensional integer grid, with a value of 0 representing no functionality and a non-zero value indicating the corresponding functionality code. This also only needs to be calculated once.

3) Environment map – those two layers are then combined into environment map which the agent will use to make its decisions

The environment map should be all the environmental information an agent needs in order to make decisions. If the terrain is changeable then we can simply update the changed parts of the maps as they change. Also if agents don’t have full world knowledge then we could generate an environment map for them by comparing their current world knowledge to the actual world environment map.

So, if we have the case of an Agent in a room preparing an ambush in a FPS then we could use a semantic net and the environment map to determine the best position for that ambush.

Step by step it would work like this:
1) Determine entry points - Based on the environment map the agent derives a list of the points at which an enemy can enter the room.
2) Evaluate entry points – The entry points are then assigned a utility value based on the likely hood of the enemy entering through that point.
3) Determine enemy vision map – Based on the chosen entry point an enemy vision map is applied to environment map, the vision map is determined based on position of the entry point and the volume map. It is stored as a binary value with 0 meaning the enemy can not see that point and a 1 meaning the agent can see that point.
4) Determine advantage points – Here the agent determines where to position itself based on points that are in range and can see the entry point.
5) Evaluate advantage points – The agent determines which advantage point to move to based on the difference in the vision map from that point and the enemy’s vision map, as well as the time to travel to that spot versus the expected time of the enemies arrival.


This would seem to be one way to begin moving towards what you are asking for.

Share this post


Link to post
Share on other sites