Propper use of Recast and Detour

[otty]

Hi,

i've included recast and detour (technically) into the my engine, wich is basicly a fork of ID Tech3. I can create a navigation mesh of any world using the map compiler and detect paths between two reachable points in the map during runtime. There is no more AI yet. I've removed the entire AI System of Quake 3 ( which was based on ID's house made AAS - area awareness system) to replace it with my own. Before writing any lines of code i was investigating some AI concepts in gaming nowadays. There are quite nice resources out there ( Killzone e.g. ). Technicaly i came up with recast and detour to be the most advanced solutions in area awareness and pathfinding. Before i start to test some AI concepts i'd like to know more about the capabilities of detour and recast.

I'm focusing on a very limited "situational" ai, not a master-brain-rule-the-world-better-than-commercial-ai.

What i want to create is a challanging AI for cooperative situations. I mean situations, not games. I am only working at this project during my free time. Therefore, i'd like to create specific situations, like a small area ( imagine a warehouse) with up to four players dropped in. Players have to reach from A to B. There is a specific number of "Enemys" dropped too. Regarding to that number, there weapons and the area surrounding them the AI is supposed to handle that situation: keep the players away from B, while using "Group-Intelligence" like covering each other, helping each other, "Area-Intelligence" like taking cover, throwing bouncing grenades, using the area as weapon against the player, and "Learing-Intelligence" like remembering patterns/behaves of the players.

I've done AI coding before, got some experience. The only thing i want to know is how much of the aims i already can cover with detour. I had a brief look into the code, ran the demo, included it into my engine. I know there is "Detour Crowd Behaviour", some steering, corridor fixings. Nice.

My "perfect vision" is, to create a challange for any set of up to four players. The AI should be a very tough challenge ( nowadays games are mostly far to easy for me and my friends, most of them totaly dropping any cooperative experiene too).

A lot of research has been done into that field the last years. But most game studios don't care about AI and challenge as they care about graphical effects and engine features. ( Remember Crysis 2, Black Ops, all to easy when you know how the AI works, and taking any fun away when you learned how to use the bugs of the AI, or in the worst case: totaly unbalanced situations).

Is there anyone who already had done some serious stuff with recast and detour? Like tactical movement of groups ( e.g. a squad of marines against a player ), or crowd behaviour like zombies ( steering, flocking etc. ). The first step would be to create fail-safe movement capabilites before doing anything like behaviour and learning.

Would be very interesting to know.

regards,

Adrian

[Mikko Mononen]

Hi,

There are bunch of AAA games which has shipped with Recast & Detour.
For tactical movement, I recommend checking out Alex's stuff
AIGameDev.com. Navmeshes are good for navigation, but for tactical
stuff, I'd build a rough waypoint/coverpoint/tacticalpoint system on
top of it. The compact heighfield is awesome for automatically
building such waypoint graphs. Also Alex has some nice examples how to
use such graph to create influence maps, etc.

Btw, I wrote a good chunk of Crysis 1 AI, so I have to defend that a
bit ;). Writing AI for a story based game is a different thing than
writing AI bot which plays against the player, the rules are just so
different, and it is very hard to make the AI to learn new things
because the environment when you encounter the AI is constantly
changing (different levels). it is quite easy to make a randomly
behaving hard AI, but it is super hard to create believably looking
human AI that is also challenging. Also the games these days want to
make the player to have awesome abilities, which makes creating a good
and balanced AI even harder.

I'm glad that you are trying to solve that, a small contained
situation definitely makes the AI shine more. I think the most fun
levels we had during Crysis1 dev was the "gameplay sandboxes" that the
designers made to test some features, i.e. group AI. Small levels,
action packed, you could replay them the whole day and not get bored.

Maybe someone should make a ground hog day shooter? ;)

--mikko

[cyr]

Adrian, would you mind sharing your code for converting a map to a
recast obj file? I've done it through the bspc tool, and it works fine
for most idtech3 based maps (even idtech1 ones ) but I always had
problems figuring out which brush types to include or ignore while
converting. Here's what I did: http://dl.dropbox.com/u/7801031/bsp2recast.diff

By the way, the AAS system still has things to offer which
recast&detour lacks. Like automatic creation of links for jumping over
gaps, jumping off ledges, accell- and jumppads and swimming through
water. In recast, those are off-mesh links that you have to create by
hand. Recast shines when you need the navmesh to adapt to dynamic
obstacles at runtime.

[otty]

Hi,

thank you for your answers. I am still researching the subject, just coded some lines with recast and detour to find out what i can do with it. Most of my work up to now is theoreticaly.

Mikko, i knew that you where involved into serious AI programming, you already got a name in the community ;) . Didnt want to affect you or your work ;) I know it is hard to create challenging ai - or games in general. Most games today are just crap, but only because there are so much developers out there. its like movies - in in the 50s, 60s, up to the 80s there where only a few movies a year. most of them high quality. But nowadays nearly everyone can ship a movie to the cinema.

I do not want to design my AI to be like human or behave like human. Thats far to much for the subject. I think its the wrong way to go. I'd like to have a challanging game, what i can play with my friends. The "sandbox" term you mentioned mikko is close to what i want to have. I'd like to have different enemys with different behaviour. My focus will be on "situational adaption".

That means: every AI will have some attributes attached ( like attacking power ). Additionaly every ai should be aware of the others ( to work as a team). Also the surrounding area should be taken into consideration. Then the AI got a simple "mission objective" like: defend position A, or attack position B or just: Survive.

Players then have to reach their own objective, like kill all monsters, reach position A or defend postion B.

Some of the players actions will be collected into an external database to alter future AI's behaviour.

I'd like to give the player and the ai exactly the same options: choice of weapon, choice of way to walk, choice of equipment and abilities. I dont like the player to be the hero, id like the team to be the hero. That may not suit the current singleplayer situation for most games, but maybe its an option for some little "experimental" game, like it was Counterstrike these days( cs went then indeed to be a great success). I still think that team oriented games are the most recommend choice for players, because the human itself IS a team orientated lifeform. Fighting against a "higher enemy" is deeply anchord in our culture. So my focus will be some research in that direction: cooperative teamplay against an challenging AI ( which is not supposed to be like human, its supposed to be better than human)

Regarding my implementation into ID Tech 3:

its realy basic. i've not done any special stuff, just taking the surfaces which are walkable ( based on normal ). i havnt set any custom flags ( like lava, water etc ) and have not set any off mesh connections.

But feel free to have a look, my project is ( of course ) on github. Look into the nav.cpp file of the maptool:

https://github.com/otty/Legacy/blob/master/code/tools/legacymap/nav.cpp

again, its very basic. i dont want to put any effort in it until i got a concept. The engine is based on ID Tech 3, but its gone far beyond this point. For example, the map tool expects Doom3/Quake4 style map format( and BSP). But my nav mesh code should work for the old ones to.

I know that the AAS system of the original quake3 is still a nice option. At the time of inventing it was a genious piece of technology. it may still is. I will not "throw" it away, just cut off all the connections to the engine to test different approaches.

Alien Swarm is using still a waypoint approach. that is very interesting, because it works well, even for hordes of aliens. I already thought about using a waypoint system uppon a navigation mesh. Nice to hear that there is a possibility in recast/detour, can you give some more information about this? Also, i got a specific design question about different sizing of agents. Some may be huge/giant, others may be small like a rat. From the "real" worlds perspective, every agent holds its own navigation mesh, "can i walk there?" because of self-recognition. How does detour/recast handle that?

I think the more the AI System knows about the area sourrounding it ( and everything within) the more options i have to make it challenging.

regards,
Adrian

[Mikko Mononen]

Hi,

If you have different sized agents, you should create a navmesh for
each of the agent size. The restriction is there to make the navmesh
generation easier. There are actually quite a few parameters which
affect the shape navmesh: agent radios, agent height, agent climb and
max slope.

There are no examples how to generate tactical waypoints. I recommend
first placing them by hand so that you get good idea how they should
be placed and then automate it. once you get there, I can help you
out. The idea is to use the waypoints for spatial reasoning, to answer
questions like "where is the nearest hide location" or "how to flank
the enemy from right", but not for navigation, you use navmesh to
actually find the path. You can use the navmesh to find the nearest
waypoint too, so you don't get the usual problems that plain waypoints
have.

--mikko

[otty]

I'm going to put an additional layer on the top of the navmesh. I'm going to create "points of interests" for the ai. Every point will be an answer to questions like "where can i find ammo for my weapon" or "where can i hide". I'm still struggling with placement by hand, even when the map itselfes wont change. From a research point of view it would be nice to have some logic clustering the walkable areas into fields, representated by waypoints.

Later on, the solution should be as flexible enough to classify danger zones, or zones with dynamic weight to create more interest for the AI to actualy go there.

[otty]

Hi Mikko,

i've figured out how to use the recast edges for creating coverpoints. I assume that a coverpoint is a point near a wall, giving cover for a specific angle between two directions. At the attached screeshot you can see a small maze, with a bot running around ( marked with the yellow box ). The bot is able to run to any reachable point located at the navigation mesh (blue fields).

All possible coverpoints are showed as triangles. They are calculated from the edges ( center of each edge ) before the game starts.

During the gameplay each point is checked, if a) an enemy is within its cover range ( angle between the direction limits ) and b) the point is visible by an enemy.

For debugging purpose i am calculating that each frame. For a "real" game, it should be enough to calculate the state of a point ( "is it a valid cover?" ) when e.g the agent wants to find cover. What do you think about this solution?

regards,

Adrian

[Mikko Mononen]

Hi,

That's cool idea. We used similar thing to create cover for Killzone3. We even calculated a "cover plate" from the voxel representation which can be used to calculate if the AI can take cover at run time. Take a look at the slides from my presentation at this year's Paris Game AI Conf, in the first part I explain the KZ3 stuff:

http://digestingduck.blogspot.com/2011/07/paris-gameai-conference-2011-slides-and.html

--mikko

[otty]

Thanks for the link, your presentation is really impressive. You've gone far further then me yet, it is a good idea to go further than just the static cover detection. Lets see how i can improve my solution with some of the ideas from your slides.

Adrian

[otty]

Hi Mikko,

i'm done with the basic implementation of cover plates into quake3.

I'm using the navmesh and its outer edges to generate two types of plates, one for the croush height as "crouch cover" and one for full cover. This is done in debug mode right now, the AI does not take any advantage of it ( well, that is the very last step). Have a look:

Yellow is crouch height cover, green is full cover. Thank you again for the presentation, it worked very well to build the algorithm with the help of your slides. My calculations are static, done before map starts. so speed doesn't really matter. For this test level, the engine creates  32 crouch, 148 full plates. i think the level is "medium" sized, but not optimized for tactical situations. 

But there is one issue im still thinking about: With my previous solution, using "points", not "plates", i wrote a very fast "angle detection", to evaluate if the cover is safe or not. How do you do this in KillZone3? Takes the evaluation of each coverpoint place when an AI has the need to take cover? Thats pretty much expensive, or not? How do you handle "cover sharing" between two or more agents?

I'm still working on the "Area Awareness" for my AI, so i can ignore that problem for now. But it would be worth the time to think about optimisations, like precalculating as much as possible.

Btw. the system is suitable for real time calculation as well. The quake3 engine has no real physic engine, so it makes no sense to implement that now. Currently i'm not calculating vaulting for crouch cover or checking if the cover plates are making sense ( some of them are facing non walkable areas, this cover wouldn't probably ever taken...). Also calculating "shootareas" is not done yet, because they are depending on the agents itself. For now i have no plan how they will look like later on.

regards,

Adrian

[Mikko Mononen]

Hi,

Killzone2 and 3 used cube maps for cover calculations. There is presentation out there somewhere describing the method. In Killzone3, the players also used those cover plates for in cover behavior (you can latch into cover).

Cover points are usually the simplest to evaluate. In the past (that is, Crysis1), we used cover points (1 per plate) to select which cover to use, and the cover plates were used to position the AI behind the cover and to detect when the cover is not good anymore. Each cover plate creates a "shadow volume", which can be used to detect which locations behind the cover are hidden and visible. That allows you to create "shoot out" and "take cover" positions. I have used both a grid of locations behind the cover as well as a "strafe line" which was clipped to the frustum to find the covering and firing locations.

--mikko