Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
icecoldduke

Quake 3 - Bots using Navmesh

Recommended Posts

Hey,

 

I've been working on replacing AAS in Quake 3 Arena with Recast NavMesh. This is quite a lot of work, because the AAS bits in Botlib basically touch all of the bot code, so on top of replacing AAS, I'm also heavily refactoring the code. Right now the bots can pathfind around the level, attack each other, and the player. There are some bugs, which you can see in the video. Sometimes the bots get into a bad state, or change states way too slowly. 

 

Source Code:

https://github.com/jmarshall23/Quake3AI


Video:

 

Technical Bits:

The Quake 3 Arena bot code is separated into 4 layers(more on that here: http://www.kbs.twi.tudelft.nl/docs/MSc/2001/Waveren_Jean-Paul_van/thesis.pdf). Layer 1 and Layer 2, which include pathfinding, fuzzy logic, goal stack, etc were in the Botlib library. Those bits of code have been cleaned up and moved to https://github.com/jmarshall23/Quake3AI/tree/master/code/game under bot_*.c. Level 3 and 4, have been heavily butchered, and are the reason why things are quite working right, but those bits are in https://github.com/jmarshall23/Quake3AI/tree/master/code/game/BotAI under BotAI_*.c

 

I've only tested q3dm7, but you can build a navmesh for any Quake 3 BSP maps, using the bspnav tool https://github.com/jmarshall23/Quake3AI/tree/master/code/bspnav.

 

I'll let you guys know when its more in a state were players can jump in and use it, it does provide a fun experience as is, but it does need work. I'm hoping in its current state it might benefit people working on custom idTech 3 projects.

 

-Justin

 

 

 

 

Share this post


Link to post

That is no small feat!

 

A side project of mine is a custom fork of the BSPC tool which generates the AAS files for Q3, and just separating the code into a stand-along codebase and incorporating fixes from Spearmint's bspc (plus a few features of my own) has been a lot of work.  I can't imagine implementing all the stuff that bspc handles for a completely different system, in BOTH the build tool and for the engine / game-code.  Crikey!

Share this post


Link to post
3 hours ago, andrewj said:

That is no small feat!

Indeed it isn't!

The bigger question however should be: ''Will it be finished?'' Because this is an IceColdDuke project. If there is anything i know from IceCold, its:

  • Has amazing ideas that he puts into practice (Megatexture stuff, EDuke32 RTX)
  • Hardly ever finishes any of these amazing ideas

If you repeat this cycle often enough, eventually you are going to carry a stigma that puts it analogus to an Ideas Guy. This is nothing against IceCold's ideas in general (As they are awesome!) but the chances of it seeing completion are not high. This is not to be meant as demotivating to Ice, its just how he works.

 

As such, whenever a new IceColdDuke project is announced, my first thought is:

  • ''That's an amazing idea!''

And my second thought instantly thereafter would be:

  • ''But will this be finished?''

Sometimes the second thought comes from the first, depends on the time of day.

Share this post


Link to post
3 hours ago, Redneckerz said:

''But will this be finished?''

That's valid. However I'm more then a ideas guy,because I always get my projects to tech complete level :).

 

I'm making a new game using idTech. I always flush out new tech in a blank project before merging it over to my private main branch. MegaTexture i found out is useless in practice, so it never got merged over, but instead of letting the code go to waste, I release it. Might help someone else, and its good for me to archive work if I need it later.

 

With replacing AAS, I again started in a blank project. This works well to ensure theres less outside variables if things go wrong, I dont have to worry about bugs being cause by other code I wrote. For my new game, I dont want to use AAS, so replacing AAS makes sense in a fresh Quake 3 project, get the bots to shippable level using recast navmesh, then merge the code over to.my branch and continue working on my game. Then if I have bugs there, it's not because the code foundation has bugs.

 

This is a solid workflow even if it seems like I'm jumping around :).

Edited by icecoldduke

Share this post


Link to post
6 hours ago, andrewj said:

That is no small feat!

 

A side project of mine is a custom fork of the BSPC tool which generates the AAS files for Q3, and just separating the code into a stand-along codebase and incorporating fixes from Spearmint's bspc (plus a few features of my own) has been a lot of work.  I can't imagine implementing all the stuff that bspc handles for a completely different system, in BOTH the build tool and for the engine / game-code.  Crikey!

 

BSPC in my branch has become deprecated. Instead NavMesh is created through bspnav, a new tool I made to generate NavMesh from Quake 3 BSP. 

 

Again Quake 3 BSPC is gone. Botlib has been refactored like I mentioned in the OP.

 

Share this post


Link to post
28 minutes ago, icecoldduke said:

That's valid. However I'm more then a ideas guy,because I always get my projects to tech complete level :).

True, but then you lose motivation, or another idea pops up that carries more of your interest - In terms of Source ports, you would be a Limit removing Ideas Guy. :P

 

Though i am presenting my critique in jest, it has a serious undertone though - I much rather see a project actually being released and finished than that it remains tech-complete.

 

This is how i view the rest of your post aswell: New and excitement take leads, but i have no indicators that this is going to be actually different than the last few times. Ofcourse, you never saw my name over at Duke4 (because i am not there) but i am well accquainted with your works.

 

And that's why im saying what im saying. I am always excited about your ideas - but as time passed, i have gotten far less excited over them because of how the story nearly always seems to end.

 

Edited by Redneckerz

Share this post


Link to post

Wait until those knuckleheads at Q3W see this! Too bad they stopped allowing new member registration to prevent spambots from posting...

Share this post


Link to post
8 minutes ago, HavoX said:

Wait until those knuckleheads at Q3W see this! Too bad they stopped allowing new member registration to prevent spambots from posting...

Let me know if they would be down to let me register over there, I'd love to post this in a active Quake 3 forum. 

Share this post


Link to post
7 hours ago, andrewj said:

That is no small feat!

 

A side project of mine is a custom fork of the BSPC tool which generates the AAS files for Q3, and just separating the code into a stand-along codebase and incorporating fixes from Spearmint's bspc (plus a few features of my own) has been a lot of work.  I can't imagine implementing all the stuff that bspc handles for a completely different system, in BOTH the build tool and for the engine / game-code.  Crikey!

 

It's such a shame that ditching bspc seems like the correct approach. The AAS system in both idtech 3 and idtech 4 was overly complicated, had edge case bugs that always came up during production of a game, and if you wanted to fix a bug in AAS, the code was too complicated to follow.

 

So that was my motivation for replacing AAS with NavMesh. It was just faster to use a industry standard path finding solution, then fix up the old system. 

Share this post


Link to post
1 hour ago, HavoX said:

Wait until those knuckleheads at Q3W see this! Too bad they stopped allowing new member registration to prevent spambots from posting...

I sent a e-mail to forums@quake3world.com, requesting if I could register, hopefully someone is still monitoring that e-mail. 

Share this post


Link to post
10 hours ago, icecoldduke said:

So that was my motivation for replacing AAS with NavMesh. It was just faster to use a industry standard path finding solution, then fix up the old system.

 

Yeah I hear that.  Personally I find the concept of nav meshes easier to understand and visualize, whereas AAS is volumetric and hence a bit harder to visualize (I haven't really done a deep dive into the AAS structures and how they work, just got a rough idea by virtue of working with the BSPC codebase).  For any new project, nav meshes are definitely the way to go.

Share this post


Link to post

fun thing: AAS is mostly what Doom BSP is. it describes map empty areas instead of map solids. that is, in Doom you have free AAS already built for you! ;-)

Share this post


Link to post
On 2/18/2020 at 6:20 AM, HavoX said:

Wait until those knuckleheads at Q3W see this! Too bad they stopped allowing new member registration to prevent spambots from posting...

It looks like my email bounced, :(.

 

@ketmar I never thought of AAS in that way it makes total sense. AAS was a great concept for the time, but issues with that approach arise when you have more complex levels. 

 

The big issue I have at the moment with navmesh is edges. The only solution I can think of at the moment is navlinks, which have to be manually placed. 

 

Were the Quake 3 original maps ever open sourced?

 

 

Edited by icecoldduke

Share this post


Link to post
On 2/18/2020 at 5:35 AM, Redneckerz said:

If you repeat this cycle often enough, eventually you are going to carry a stigma that puts it analogus to an Ideas Guy.

I don't agree with that. 

Share this post


Link to post
5 hours ago, icecoldduke said:

Were the Quake 3 original maps ever open sourced?

No.

 

Of the Quake franchise, only Quake 1 maps were open sourced (both single player and deathmatch maps).

Share this post


Link to post

Some maps did get their sources released as sample maps included with some of the map editors.

Share this post


Link to post
3 hours ago, Avoozl said:

Some maps did get their sources released as sample maps included with some of the map editors.

Hmmm I vaguely recall that, but don't they have some obnoxious non-commercial licensing terms?

 

EDIT: there are three sample maps from Quake3, one place to get them is the GtkRadiant 1.6 packages.  The maps are Q3DM1, Q3DM7 and Q3DM17.  I cannot find what their license is though.

Edited by andrewj

Share this post


Link to post
49 minutes ago, andrewj said:

Hmmm I vaguely recall that, but don't they have some obnoxious non-commercial licensing terms?

 

I cannot find what their license is though.

 

Has anyone ever released modified versions of those maps? I uploaded the map files to the github, I'm going to have to make modifications to those maps  for things like nav links, nav blockers, etc. I might reach out to Bethesda after Doom eternal is released, get clarification on the license and see if theres a possibility of the map files getting released. Doesn't hurt to ask.

Share this post


Link to post

Some comments on the OpenArena forum (about Q3DM17) say they are not GPL compatible, but I have searched around and could find any official statement about them.

 

I think that unless you are making a commercial product with those maps, you would probably be OK making something with them, just make it clear that their license may be not GPL or open source.

 

 

Share this post


Link to post
2 hours ago, icecoldduke said:

'm going to have to make modifications to those maps  for things like nav links, nav blockers, etc.

so it will require manual work in the end? don't get me wrong, plz, i simply interested.

Share this post


Link to post
7 hours ago, ketmar said:

so it will require manual work in the end? don't get me wrong, plz, i simply interested.

Its optional, but manually modifying the maps will provide a better user experience.

 

Manually placing nav links allow the bots to pathfind off ledges for example. 

 

I'm also toying around with the idea of multiple navmeshes. So take q3dm1, the entrance from the interior had three door ways to the courtyard. If I want the bot to go through each doorway, I can place navblockers in a doorway, for each navmesh, then randomly choose a navmesh to query when the bot is looking for a LTG. 

 

In the end that means the bot will randomly go through one of the door ways when it wants to go from the interior to exterior or vice versa.

 

Also placing invisible nav blockers around would make it seem to player that the bot is doing more complex movement, when in reality there simply avoiding invisible boxes.

Share this post


Link to post
12 hours ago, icecoldduke said:

I'm also toying around with the idea of multiple navmeshes. So take q3dm1, the entrance from the interior had three door ways to the courtyard. If I want the bot to go through each doorway, I can place navblockers in a doorway, for each navmesh, then randomly choose a navmesh to query when the bot is looking for a LTG

That seems like overkill.  Couldn't you just temporarily mark certain nav polygons as do-not-enter?

 

Plus I'm surprised you need manual links for falling off ledges, isn't that something the nav mesh building library (Recast or whatever) automatically handles?

Share this post


Link to post
22 minutes ago, andrewj said:

That seems like overkill.  Couldn't you just temporarily mark certain nav polygons as do-not-enter?

 

Plus I'm surprised you need manual links for falling off ledges, isn't that something the nav mesh building library (Recast or whatever) automatically handles?

I don't think it's overkill. The way your suggesting requires recomputing a segment of the navmesh every time I want to change the path. This makes sense in games were the environment isn't always deterministic. However in Quake 3, the enviro doesn't change, so precomputing a set of navmesh permutations for the bot makes sense because the runtime cost of it is zero :), and the result is always deterministic. 

 

I'm not sure of any other way then to use navlinks. This ensure's bot's fall of ledges properly, and for example, not into lava. Do you have a better suggestion?

 

 

Share this post


Link to post
4 hours ago, icecoldduke said:

I don't think it's overkill. The way your suggesting requires recomputing a segment of the navmesh every time I want to change the path.

No, hardly that.

 

I'm suggesting that the polygons making up the nav mesh could have properties that could change at run-time, like a boolean value called "can-enter" which could be easily toggled between on and off, and the navigation logic could test that property when finding a route.

 

Just an thought.

Share this post


Link to post
10 hours ago, andrewj said:

No, hardly that.

 

I'm suggesting that the polygons making up the nav mesh could have properties that could change at run-time, like a boolean value called "can-enter" which could be easily toggled between on and off, and the navigation logic could test that property when finding a route.

 

Just an thought.

That assumes the navmesh polys are granular enough. If say you had a football field, were the ground is a single plane, that wouldn't work. Were as if designers manually placed nav blockers, the resulting navmesh would provide the correct results. 

Share this post


Link to post

Committed quite a few fixes:

  • BspNav now processes patch surface types. Which fixes pathfinding bugs in q3dm1 were the bots couldn't walk into the serpent thing.
  •  Fixed quite a few state issues were the bots would stop moving due to legacy, stale data(trying to immediate path to a node across the map from a previous nav query).
  •  Increased agent radius to prevent bots from getting stuck. 
  •  Also added widescreen support(not really a project goal, just was tired in playing 4:3). 

navmesh.png

Edited by icecoldduke

Share this post


Link to post

I've fixed bot aiming and added some extra logic to the retreat state so they are harder to hit. I've uploaded progress video 4, source code is on my GitHub see the OP.

 

 

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×