New Blog Articles

More 0.8 Progress

As I mentioned in the last blog post, the MapGoal overhaul has been going very well. Most the functionality is there, and now we're just porting old map goals to the new interface and addressing issues as they come up and simplifying along the way. The goal is still to maintain compatibility with 0.7x waypoint formats, even if 0.8 ships with a different navigation system. Currently, the waypoint files are loaded, and from that data goals are created in the new format.

What exactly is the new format?

Map goals are configured entirely on the script side in 0.8. The main advantage of this is that ourselves or users can implement new map goals for anything they like, and simply drop the scripts into a folder, and those goals can be placed in a map, similar to how waypoints are placed. One important difference though, is that goals are not actually connected to the navigation system. They are independent of the navigation system, meaning we can change the underlying navigation and all the goals will still work. In practice, that means that 0.8 could stick with a waypoint navigation system and use the new goals, or if things work out well, we may ship 0.8 with a new navigation mesh or flood fill based navigation system and things would continue to work. The waypoint files with flags on them that were used to set up actions were an element to the earliest development of Omni-bot, going back to 2004. It was simple and easy to implement at the time, but clearly as the bot expanded to more games, it doesn't scale well at all. In addition it is a weak link in the amount of flexibility the rest of the bot provides via the scripting interfaces.

Since all the map goals are script defined now, it is completely open to implement as the scripter sees fit. You can define what properties you want to use, how the goal is saved and loaded, and how it renders itself. Some custom rendering can be seen below. This demonstrates that by being script defined, each goal can render itself very specifically to the type of goal it is, to provide the best visual indicators of the information the goal is set up with. The idea is that you shouldn't need to print out a bunch of text to visualize your goal, you can use debug lines to draw trajectories for example for mortar of airstrike goals, you can draw short lines that display the different facings a camp goal can randomly cycle through, or any number of visual aids.

What's it look like?

Ok let's get to the examples.

This may look like a mess, and I agree it kinda does from a static screenshot, but what this shows is that each goal can render information into a proper 3d text block. This block provides information about the goal such as the name, group, type, etc.

At their simplest, goals render themselves with their name, group(if defined), and bounding box. These goals don't yet have any custom rendering implemented. We may for example add support for a plant position, that could render as a little box or something so that one or more positions can be defined in the goal as places to plant the dynamite for plant goal types.

This is currently what a camp goal looks like. Camp goals are new, and the goal is that they are flexible enough to replace Attack, Defend, Sniper, and all variations of weapon specific Defend/Attack/etc points, since they can be configured with weapons that restrict their usage.

In 0.7X, Switch goals were crudely defined in a global table in the map script. In 0.8, they are promoted to script defined map goals, so they are placeable and configurable as if they were any other goal. Here we see the relevant information being rendered for the goal, the position, and the facing.

Similar to switches, in 0.7X, the escort goals relied on a bunch of information that was required to be set up in the map script. This too is simplified in 0.8, and with the new stuff comes the very useful ability to support and render additional useful information about the goal. In this case we see that there are 2 offsets that are part of this goal that represent where a bot should escort the vehicle from. These points are effectively attached to the vehicle, so that escorting bots will use them as formation locations when escorting.

Similar thing here. This goal also has offset points that represent the boarding locations for jumping up into the tram to ride it down the tracks. These properties can be tweaked while in-game and you can get immediate feedback, then that data will be saved with the goals.

On the fancy rendering end of the examples, the mortar goal in ET actually renders the trajectory of all the configured facings, so it's easy to tell where each potential shot will end up hitting. As you can see, the blue lines off of the goal itself are actually facing vectors, which is where the bots face when they line up each shot. The facing information alone is rather useless though, since the mortar doesn't fire along the players facing. Knowing how it fires allows it to be simulated and rendered by the script.

What's new?

Things are a bit slow lately, with me being a dad and all now. The good news is that crapshoot recently pushed out 0.72 for RTCW which has an impressive list of features and fixes, and hopefully in the near future we will push out 0.72 for Enemy Territory as well, then hopefully finally get the Doom 3/Quake 4 versions out that have been stalled for a long time.

0.8 Progress

The other good news is that this weekend saw some huge progress on the 0.8 front. The waypoint/map goal separation is going great. I'm using ET as the guinea pig for the new system as it has a ton of goal types with varying complexity which allows us to give the new stuff some good testing. Many of the ET goals are already working under the new system. I'm also happy to say that the configurable nature of the system is already showing promise. To help me out, crapshoot threw together a mapgoal + scriptgoal for an 'airstrike' goal, which could be placed in-game similar to how one would place a waypoint, but more intuitively. By dropping in 2 scripts(mapgoal and script goal) script, we had immediate access to new behavior, complete with all the functionality that is available for mapgoals, such as routing, scripting availability, etc.

Also, because the goal creation process is getting overhauled, I've improved the debug rendering output for goals, and that too is exposed to script, so the map goal can render itself however it pleases. For example, the sentry goal for Team Fortress 2 is an actual stick figure of a gun turret, with the appropriate orientation based on the sentry facing data.

Here are some early screenshots of the goal rendering. It will probably change significantly as we extend the map goals in script and customize the rendering of each to reflect the properties and capabilities of each map goal.

MapGoals

Quick terminology lesson. MapGoals are goals such as snipe points, constructions, dynamite points, attack, defend, etc. The bots themselves have behaviors that run off of these map goals. For example, a BuildConstruction behavior would look for construction MapGoals to run on. For whatever reason, I've been calling behaviors goals also, as is the case with Script Goals, which are in reality, behaviors. This is why there is a distinction between goals and MapGoals.

Currently MapGoals can come from one of 2 places. Either they are automatically detected as part of that map, as is typically the case with CTF flags, capture points, dynamite, construction, mg42, etc, or they are created as part of the markup on waypoints. When you set an attack flag on a waypoint, you are basically flagging that waypoint to create an attack MapGoal, using the position of that waypoint, the facing, and any custom properties that the MapGoal might support.

The way this works is the result of one of the very first systems to be implemented in the bot when Omni-bot first started back in 2004. Back then, it was my desire to get the bot running quickly and easily, so I opted to use the tried and true waypoint navigation system that so many bots have used. Also like many bots, I decided to attach goal information to waypoints in the form of flags.

As time goes on this has become less and less desirable. Most recently I have been experimenting with new and improved navigation system. Navigation Mesh, Flood Fill, whatever the new navigation system ends up being, it is obviously a problem when there is so much goal information that is encoded into the waypoint files.

When you add an attack flag, defend flag, snipe flag, etc to a waypoint, a goal is ultimately created. Some goals desire to have additional information. For example, the PipeTrap goal in Team Fortress has a bunch of extra informations, like a list of facing directions, a list of placement directions, all meant to be used to control the spread of the pipe bombs by the bot. Since specific MapGoals are place with generic flags on waypoints, it becomes cumbersome to place goals that have custom properties on waypoints. Even simpler goals such as Attack and Defend would like to have some extra parameters, like how long to wait at a particular point, perhaps what weapon should be equipped at the Defend goal, etc. Setting these properties means you need to know a bunch of named properties for a particular goal type and set them in a most inconvenient way.

To summarize, splitting MapGoals from navigation has several advantages.

• Can swap out navigation system without losing goal information
• Can better address the issue of placing goals and giving them their custom properties, custom render visualization, etc
• Can have different sets of goal information that configures a map differently, all run off the same navigation.

Splitting MapGoals

I've been working on this task for a few days now, and it's going very well. The new method of MapGoal creation basically involves the game giving the bot a list of named properties. The properties can be any number of generic properties that may be relevant to a particular goal. One of the properties will be a Type field, which is an actual name of the goal that should be created using that set of properties. The Type may be attack or flag or sentry or something. The important part of this is the added support for an arbitrary number of properties, as this is an important part of supporting arbitrary goal creation. This generic interface also means that the addition of new goals don't have to break the interface between the game and bot. For example, a new MapGoal type called DisarmMine could be added, and the mod can send the bot the information before the bot has been updated to support it. The new map goal could then be registered in script and a behavior implemented in a script goal, all without updating the code of the bot. The important part is that it will be more flexible and more data driven.

Scripted MapGoals

So with the change to a generically defined list of goal properties, I got to thinking how nice it would be to define MapGoals in script, similar to the script defined states that run on bots. This is currently what I'm working on, and is probably one of the more complex parts. Once Omni-bot gets the request to create a MapGoal of some named type, whether from the game or from the file that has all the goals in it, something has to handle pulling out the properties that the goal cares about. For example, a defend goal might have several custom properties, such as MinWaitTime, MaxWaitTime, EquipWeapon, Facing. The bot will create a MapGoal, and allow the script for the defend goal check for the presence of these properties. Also since these goals might be extended or changed, it is necessary for versioning support to be added, so that If you are running a version of the bot with defend version 2, and load up a map that has definitions for defend version 1, the script will be given the chance to update itself. If new properties are required that weren't defined before, and can't be given a default, that particular goal will be put in an un-used limbo state. The first use of the versioning will need to be used to translate the properties from waypoints into a usable goal. I'm calling version 0 for a MapGoal the version that comes from the waypoint, so that the new MapGoal system will be backwards compatible with old waypoints. Of course, saving the map will still save to a new waypoint file, and a seperate goal file. The waypoint files will likely be smaller, as they won't include properties and most of the flags will be gone.

Placing New MapGoals

Since MapGoals will be seperated from navigation, they should have a more sensible and easy to use system for placement. Since a MapGoals script will know what properties it wants, it can render the appropriate debug aids and/or print messages about what it needs, both during initial placement, and in cases where the version has changed in such a way that the goal needs to be updated to function again. Goals on waypoints work ok in the case where the goal can be represented by a single position, a single facing, and possibly some named properties. What happens if you need extra position or facing information? It's difficult and messy to do. The new script defined goals will not be tied to a specific position. They may have any number of positions per MapGoal, any number of facings, and whatever else they need. One could do a Patrol Mapgoal type, where it contains an ordered list of points to visit.

How is it going to be saved?

As I mentioned above, goals will be saved in a seperate file than the navigation file. Possibly something like mapname_goals.gm, and the format will likely be a script file, as the filename suggests. Couple reasons for this. Script file are human readable, easy to parse, easy to generate automatically, and extremely flexible.

What about the existing map script file?

This is a bit tricky. At its simplest, the mapname_goals.gm is just going to be a bunch of nested tables with property information for each goal. The existing goal scripts can get pretty complex, and contain a bunch of functions, globals, etc. The idea of merging them is tricky, primarily because it can be tricky to save out a snapshot of a file including the function code, and also because it is risky to automatically save information to a file that the user will be editing. It's a pretty big opportunity for a user to accidentally mess up the goal tables when trying to script for the map. For these reasons I lean towards leaving them as seperate scripts, but that has the downside that they are scripts that depend on each other. Ideally there would be a nav file, whether than a waypoint file or from another navigation system, and a goal file which contains all stuff about goals. This part will require some thought.

Intro

The forum on the main site kinda blows for making nice looking blog-like posts like the development logs, so I'm going to start using the wiki here.

I haven't done one of these since Aug 2006, so let's play catch up.

What is new?

We have version 0.71 out for Enemy Territory and Return to Castle Wolfenstein. Our good buddy Crapshoot did most of the RTCW port himself by looking at the Enemy Territory stuff. 0.71 brought a ton of enhancements to the bot, especially in the scripting department. There are now a large collection of script implemented goals that can be looked at to get an idea about how you can do whatever you want.

For anyone who hasn't seen on the main website, Omni-bot got a full page article in PC Gamer. A few months ago one of their editor contacted me because they were interested in doing an article, mainly to do with the recently announced Team Fortress 2 support. I answered some question in the email about it, and he turned that into the article you see. Looks pretty good. I only wish my real name was used in there somewhere and not just DrEvil.

What's going on recently ?

Quake 4/Doom 3

Crapshoot has recently begun trying to get Quake 4 and Doom 3 ready to release. Since they are relatively simple games with few maps it would be good to get an official version of Omni-bot for them out that is based on the 0.71 code. The communities are pretty small, so hopefully someone will use it. If nothing else it means more games we can officially say Omni-bot supports. I'll probably need to fix a few code bugs to get this releasable.

Day of Defeat: Source

Geekfeststarter aka Jaskot is still working on bringing Omni-bot to Day of Defeat: Source. Like Team Fortress 2, this will be based on the new SDK code that I have been working with Valve to get added. Hopefully this code will get rolled out to everyone in an update coming soon. The bots are running around and using nearly all the weapons already. The game modes in DOD:S are pretty simple, so those should be easy to get running. The difficult part about this game is that it's a more realistic shooter, and the bots probably wouldn't do well to just run for objectives and fight along the way as they can get away with in other games. DOD:S bots would benefit greatly if we had a cover system in Omni-bot, so that the bots could use cover during combat. The cover system is still in the design stage, but I'm hoping we can take advantage of the flood fill navigation system that I'm working on to evaluate cover points automatically, as placing them manually would be very undesirable. We'll see where that goes, but ultimately cover usage would be a nice thing for the bot to support, and the more automated it is the better.

Team Fortress 2

Ah, so what's going on with Team Fortress 2? This is probably the most anticipated games for Omni-bot in our history. It's the first 'modern' game we will be supporting, and it has a large community where we could potentially see a big growth in the bot community. As I mentioned above, this bot is built on the new SDK code that Valve has made at my request. I am trying to poke at Valve to get it released ASAP. I'm hoping it was mainly the holidays that have held it up so much. I've been using TF2 Omni-bot as the test bed for the navigation system work I'm currently doing, which you can read about below.

New Navigation

I have been working more on the new navigation system. I've jumped back into the flood fill method, since it's a mostly automated process. I've been improving the way it sectorizes the flood fill. I'll post an updated video up soon when I've worked out a couple more issues. I've improved the sectorization of the flood fill significantly, but there are still some issues I have to work out. Currently I can save the results of the flood fill to the format that the navmesh pathfinder can use, so the bots can pathfind on it. Just to be clear, there a 2 seperate navigation systems that I've been tinkering around with. Keep in mind that these solutions are based around the idea that I don't consider decompiling or reading map formats for individual games a viable option, considering Omni-bot spans several games and mods. If that were easy to do, I would likely do it. Exploring the world with collision tests is not near as good as having access to the raw geometry of the map.

NavMesh

This is basically an implementation of a navigation mesh. This is basically where the environment is represented by convex regions which the bots can pathfind on. This system is appealing for many ways.

Advantages

• Coverage - The convex regions, when done right, provide perfect map coverage. They represent all walkable space, and very efficiently.
• Performance - Most of the time it takes less sectors to cover a map than it would take waypoints, which means it is more optimal and quicker to path on.
• Bot behavior - You have probably seen erratic movement from bots on a waypoint graph, since it is such a poor representation for navigation. Since the NavMesh has near perfect and optimal map coverage, the bots can be very accurate in their movement, and they will approach points from the best directions.

Disadvantages

• Manual - Currently building these sectors is manual, though actually pretty easy and faster than building waypoints, for mirrored maps especially.

Flood Fill

The flood fill is an automatic way to explore the map by collision testing small axis aligned bounding boxes with the environment. It does this repeatedly until it has a huge list of small cells that it has explored. Because there are tens or even hundreds of thousands of cells, it has to optimize them into a more usable number, so it takes the cells and attempts to merge them into larger axis aligned sectors. The merging step is the most difficult part, as it has to figure out what cells it can properly consume with each sector. The main issue with this is that of uneven terrain. For example, even the ground in the ramp room of ctf_2fort in TF2 is uneven, but it's minor enough where I don't want a bunch of small sectors bloating up the results.

Advantages

• Automatic - The flood fill explores the world itself from seed points, so it does a majority of the work itself.

Disadvantages

• Axis Aligned - Due to complexities of merging into convex polygons, I have thus far been sticking with axis aligned sectors, which is the same strategy the Counter Strike: Source bot seemed to take. This means more small sectors for non axis aligned rooms but it keeps the difficulty managable.
• Difficult - I don't get a lot of collision options from the SDK. I can do raycasts and axis aligned box casts. In addition, it is a very difficult problem to take gridded data and generate good sectors from them, especially on uneven terrain. It would be trivial in a 2d gridded game, but 3d games have uneven grounds, ramps, etc that make it more difficult to merge the sectors in an optimal way.
• Unlikely to be completely automatic - Due to the complexity of exploring the levels and building good sectors out of that data, many maps will probably need manual tweaks to areas that it builds badly. Still tweaking a bit probably still beats building nav from scratch in most cases.
• Memory usage - Although not a huge deal, as it doesn't happen at runtime. The generate process consumes a lot of memory. The more wide open the map the more memory it will consume due to the sheer number of cells that are generated to explore the world. For example mml_minastirith, for Enemy Territory is the most wasteful wide open map I've ever seen, and in the 2 times I've attempted to generate data, I ran out of cells in both. I'm only allocating about 260,000 nodes, which is about 24 Megabytes. I don't know how much coverage of the map that handled, so it could take a good chunk more of memory to be able to finish it.
• Not very optimal - Because the sectors are axis aligned, and because generating them is difficult, typically the number of resulting sectors is a bit on the high side. The more non axis aligned the world is and the more uneven the ground, the worse the results will likely be. Lots of sectors means increased memory usage and increased cost of generating paths.

Although I am currently playing with the Flood Fill, I still tend to lean a bit toward the NavMesh as the future of Omni-bot. Yes it's a bit of a bummer that it wouldn't be completely automated, but the results, both in efficiency and coverage, outweigh that. Regardless of whether we use the Navmesh or not, the Flood Fill will likely get used in some form. At the very least there is a possibility that I will use the Flood Fill to do some automatic cover finding. Time will tell, but know that I am currently trying to improve the Flood Fill results. I know how great it would be if most of the work could be done automatically for the navigation, so I'm going to see how close I can get it to that. A hybrid approach may even be likely, where the Flood Fill can generate sectors which you can then clean up with convex sectors where needed.