AAS Files vs. Navmesh/Waypoints/etc.

Discuss Artificial Intelligence and Bot programming.
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

AAS Files vs. Navmesh/Waypoints/etc.

Post by jitspoe »

Is anybody really familiar with the the Q3/Gladiator AAS (Arena Awareness System)? I'm trying to decide if I should take this approach over something like a navmesh or waypoints, or if it's really that different.
Lightning Hunter
Posts: 169
Joined: Wed Nov 28, 2007 6:15 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by Lightning Hunter »

jitspoe wrote:Is anybody really familiar with the the Q3/Gladiator AAS (Arena Awareness System)? I'm trying to decide if I should take this approach over something like a navmesh or waypoints, or if it's really that different.
I haven't had much experience with AAS, but I can say that I am a huge fan of Waypoints. I have waypointed around 1,000+ maps between Unreal Tournament and Quake (the Frikbots). A good waypoint-based bot can navigate just about any map effectively. I would say that only about 0.1% of the powerups in all 600 maps I've waypointed for Quake could not be reached by the Frikbots. The powerups that could not be reached were difficult to obtain even for humans.

That being said, Not just anyone can create good waypoints. I'm not trying to boast or anything, but of the 20 or so people I've seen release waypoints for the Frikbots, only a few of them were any good. Even then, I found myself making improvements upon the best waypointed maps for my Frikbot Waypoint pack. I'm a bit of a perfectionist, and obviously have the experience (and patience) that not many people have with bots. It takes an average of 30 minutes for me to waypoint a medium sized map to perfection at full speed. The large, more complex maps can take 2-3 hours. Only about 25% of waypointing is placing the waypoints, while the other 75% is testing and perfecting.

Probably more than you wanted to know, but anyway... My vote is for waypoints. ;)
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by jitspoe »

Whatever I do, I'd like for it to be automated.

Current ideas:
1) Load the .bsp file directly to calculate walkable "volumes" (possibly similar to how AAS works?)
2) Do lots of traces to build up waypoints or a navmesh.
3) Build waypoints/navmesh on the fly, based on where players walk.
4) Generate paths players take as they play, and have bots follow these paths.

Right now I'm leaning toward a combination of 3 & 4.
Lightning Hunter
Posts: 169
Joined: Wed Nov 28, 2007 6:15 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by Lightning Hunter »

If you choose that path, don't expect the bots to be great. The truth is, automated bots will never be as good as bots with waypoints. I guarantee they won't be able to obtain powerups that require the following: Difficult jumps, ladders, rocket jumps, tricky teleporters, precision drops, walking along tight ledges, complex button sequences, and more. Bots that are waypointed can do all these things. So as long as you are ok with the bots missing half of the best powerups and weapons, that is your decision. The truth is, many mappers place rocket launchers, lightning guns, armor, and powerups in difficult areas. Many of them even require rocket jumps.

Reaper bots are automated, and they don't even compare to Frikbots. They can pretty much only walk around the map, perform basic jumps, and swim in water. Anything more advanced than that requires waypoints. You will never see Reaper bots going up ladders, performing difficult jumps, going through tricky teleporters, shooting complex buttons, jumping over pits of lava, or anything else that is remotely complex.
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by jitspoe »

That's where the player paths would come in.

For example:

Image

Image

There's a trick jump to get to the backdoor path in this map where you have to strafe jump up a hill just right to hit a little ramp higher up. This is using Quake2 physics, by the way.

Here's a video some players made of some trick jumps as well: http://www.youtube.com/watch?v=J_E2Ql7CTkI

Many of the maps are designed around these styles of jumps, and I need to find a way to make bots navigate like that for them to be remotely decent. Waypoints can define a path, but they're not going to define the precise movement needed to strafe jump along that path. I suppose I could make a system like that, but I fear the paths will become too predictable.
Lightning Hunter
Posts: 169
Joined: Wed Nov 28, 2007 6:15 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by Lightning Hunter »

jitspoe wrote: Many of the maps are designed around these styles of jumps, and I need to find a way to make bots navigate like that for them to be remotely decent. Waypoints can define a path, but they're not going to define the precise movement needed to strafe jump along that path. I suppose I could make a system like that, but I fear the paths will become too predictable.
That's what waypoints with flags are. They define what kind of move the bot should perform in order to reach a certain spot. Frikbots have pages of flags (from precise movement to rocket jumps). Unreal Tournament has all kinds of special path nodes that tell the bot to perform an impact jump, a trick jump, ride an elevator, etc.

The behavior of any bot will always have an element of predictability, but I personally feel that the Quake3 bots are far more predictable than the Unreal Tournament bots. UT uses waypoints, while Quake3 uses AAS.

Don't get me wrong; if you are able to successfully create an automated bot that uses ladders, performs trick jumps, rocket jumps, presses buttons to open doors, etc., it would be one of the best around. That being said, I just don't see how it's possible. Waypoints with special flags are what tells bots to perform special moves to reach certain spots. Many people complain that Quake3 bots are limited in that regard, because they can't just place a waypoint that tells a bot to jump from a certain spot to another spot to obtain a powerup. As a result, the bot falls constantly.
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by jitspoe »

The tricky thing is, most of these jumps require making a series of jumps beforehand in order to build up velocity. In the example I posted, there are like 5 jumps in sequence necessary to make that big jump. Hand placing all that seems like it would be very difficult. I haven't found any bots that can strafe jump effectively, so I might be on uncharted territory here.

Now this particular path is fairly narrow and limited, so a waypoint type system would work, but for some maps -- especially the more open ones -- there are a ton of different ways you can strafe jump around to gain speed and access to different areas of the map. That's why I was wondering if something like AAS would allow the map to be represented in a way that would be easier to just define general areas that you could move freely in.

Of course, if you have enough points, a waypoint system can effectively cover all the important playable area, but I'm not sure how many points that would take.
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by frag.machine »

Just to add some fuel to the discussion...

http://www.ai-blog.net/archives/000152.html
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
Lightning Hunter
Posts: 169
Joined: Wed Nov 28, 2007 6:15 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by Lightning Hunter »

I agree somewhat with that article, but the simple truth is that nobody has created a non-waypoint bot with any of the features discussed that beats a waypoint bot as far as a big multiplayer platform like Quake is concerned (last I checked, anyway). A lot of what that author is suggesting takes more code than anyone has been willing to do thus far. One big problem with automatic pathing systems is that no two map is alike. Bots need different instructions in different maps, and waypoints with AI flags can give them these different directions. Yes, there is a disadvantage to bots always taking the same path, but that is barely noticeable with good waypoints. I've said this for many years, but a good bot is only as dumb as a the waypoints created for them. Unreal Tournament bots and Frikbots are two of the best waypointed bots I know of, but there are still a lot of bad waypointers out there. Many people don't even attempt to create good waypoints for their maps. When a map is properly waypointed, the bot will make very few mistakes (although UT bots are much better at making less mistakes than Frikbots, admittedly).

Once again, I am not against the idea of an automated waypoint generator. I just haven't seen one work well enough yet. Quake 3 was the best so far, but even it had issues with certain maps. Some mappers have stated that waypoints in Quake3 would have made things easier for bots to visit certain areas and collect certain powerups.
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by frag.machine »

TBH I don't have an oppinion about which approach is better, and I wonder if some form of hybrid system (navmeshes + waypoints) could be the definitive answer.
Specifically speaking about Quake, navmeshes would require a lot of engine coding (unless we could derivate something from the BSP tree, but as the author pointed, it would be really inneficient to query the resulting navmesh).
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by jitspoe »

I certainly think a combination of systems would be the most effective. It would also probably be the most complicated to implement. Navmesh could define the basic movement area, and different parts of the navmesh could be connected with waypoint "shortcuts". Perhaps it wouldn't be so bad. The tough part is going to be defining what areas of the map can effectively be strafe jumped through, when you consider things you could potentially clip your head on and whatnot. I guess I could use the navmesh purely for walking, and have waypoints for jumping. Thing is, nobody walks in Paintabll2, so it almost seems pointless to have a navmesh in that case...
gnounc
Posts: 428
Joined: Mon Apr 06, 2009 6:26 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by gnounc »

sooooooooo.. waypoints it is?
jitspoe
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by jitspoe »

gnounc wrote:sooooooooo.. waypoints it is?
For now, I think. A navmesh is probably better for generic NPCAI covering large areas, but Quake2 maps are pretty small and require very specific movement. I feel the special case movements are going to be just as common, if not more common, than basic walking, so there seems little point in having an additional navmesh system.

I'll just record lots of waypoints and have a bit of randomization in the pathfinding algorithm so there's variation. I just have to be careful not to introduce too much cpu/memory overhead adding all these points...
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by frag.machine »

Hmm... In Quake one could simulate a navmesh using a bunch of QC customized triggers.
This would be useful to map areas with complex geometry that otherwise would require a ton of waypoints.

This looks like something worth a experiment... :twisted:
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
goldenboy
Posts: 924
Joined: Fri Sep 05, 2008 11:04 pm
Location: Kiel
Contact:

Re: AAS Files vs. Navmesh/Waypoints/etc.

Post by goldenboy »

IIRC Crysis used a navmesh combined with waypoints of various types. You would define an area inside which the AI should rely on waypoints (such as a building) and place specific entrances and exits to such an area. On top of that, there were AI anchors to mark stuff such as cover etc. You could also mark mountains etc. as "forbidden areas", so those were probably excluded from the navmesh generation or something.

I thought the Crysis AI was pretty good. It would climb ladders and get into/use vehicles, too (had to be scripted.)

Since I don't see quake engines supporting navmeshes anytime soon, my game will be using waypoints (not sure yet if I will use Frikbot code or write my own waypoint navigation) and AI nodes that can be flagged in various ways. My AI won't need to be able to trickjump, though, just basic navigation, cover and group tactics. Single player type stuff.

Oh, also, I have seen the AI in Doom 3 (AAS) do hilariously stupid stuff. It is often hard to make them do things or keep them from falling into pits.
Post Reply