My Quake engine enhancements

Discuss Artificial Intelligence and Bot programming.
TheHyperborian
Posts: 10
Joined: Sat Jul 23, 2011 12:35 am

My Quake engine enhancements

Post by TheHyperborian »

Hello,
I am posting here if people are interested. I have been adding alot to the Quake engine to improve AI, navigation. My goal is to have robust and rich navigation in Quake and expand the Quake engine further.

What I am doing right now is generating automatic waypoints and navigation meshes from the map geometry. This is not so hard to do really, as most quake maps don't have very complex geometry and finding the walkable areas is pretty easy. I had been planning to use recastnavigation but it appears it needs the data in triangle and Quake uses various polygons in the world brushes, and while I have some of it working there are some issues I have with some triangulation.

So as of now I have path finding using waypoints and navigation meshes. I may ultimately move this code into the map compiler, as it is time consuming to determine all the connectivity graphs. I will post some videos showing the automatic waypoint algorithm and the AI path finding along it. I am also working on much better navigation and sterring, as the MoveToGoal is very primitive.

Also I am going to replace QuakeC with Lua unless you can give me a good reason to keep QuakeC. QuakeC is pretty limited and in order to do the things I'd like, I would need to basically rewrite the compiler to support things like structures, and arrays, and things that would be very useful. It will not be impossible to write tools to convert quakec to lua so, if for some reason you think it is a terrible idea to ditch QuakeC, speak up and I will rewrite the compiler because right now it is not very friendly to modify it at all.

Ok thanks for checking this post I will be back later with a little video.Also, if anyone knows how to compile Dark Places with mingw, I can not get the code in SVN to compile because of the software renderer. It seems it only compiles with Intel C++ and I haven't bothered to see if I can just set a define or something to ignore it.
Electro
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia
Contact:

Post by Electro »

Awesome, I can't wait to see some vids. I was curious how recast would go with Quake.

What kind of ai did you have in mind? I'm yet to find a decent solution for automatically generating data for bots (and no, I don't count gladiator/q3 bots AAS as a solution... as they only handle the most basic simple cases).
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by revelator »

software renderer in darkplaces ? :?

must be something new i havent checked in a while, but i may be able to help with the mingw stuff.

first of to save a lot of trouble go get the codeblocks ide (comes with mingw in the full package, but you might want to use the mingw64 compiler since its directx api is somewhat more complete).

oh and mingw64 also provide 32 bit compilers ;)

the reason why you should get codeblocks is mostly because it can import both msvc and dev-c++ projects so porting gets a whole lot easier. if you prefer the msvc compiler it can also use the free one from microsoft.

if you run into any problems let me know :)
TheHyperborian
Posts: 10
Joined: Sat Jul 23, 2011 12:35 am

Post by TheHyperborian »

Recast navigation required the mesh to be in triangles but Quake stores the brushes in various sided polygons. The documentation for recast sucks (there isn't any), and I found it wasn't hard to find them myself.

I just wanted a navigation system for my own projects. I took the Quake engine because it is pretty simple to understand, not hard to modify, has plenty of tools and stuff available for it. I had originally been doing waypoints manually by walking around the map and placing them. Then I was putting them in the map in Worldcraft, and then I figured out how to put them automatically on most maps. The tradeoff is it takes some time and alot of memory but it will work on most maps.

Then I decided I wanted a navigation mesh, which meant ripping the BSP apart to find navigatable polygons, walking edges to find the connections. But then that means that AI can move robustly because you know exactly where it can navigate on the map, and finding paths isn't very hard with them. But it takes some time and a lot of memory to do this.


I use CodeBlocks actually, I didn't know it could load a MSVC project I will try to load one with it and see if it works.
Electro
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia
Contact:

Post by Electro »

Yeah that's all good and well for general navigation, but when it comes time to doing more complex things like jumps that require a run-up, circle jumps, ramp jumps etc. then it kind of falls apart and needs another method.

Yes the walkable surfaces in Quake are stored as n-gons, and the reason that recast requires triangles, is that you can always reach any point within a triangle. That is absolutely guaranteed, whereas with n-gons, there needs to be additional checks to see if they're convex.

I would investigate triangulating the Quake data so you can feed it to recast.
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
TheHyperborian
Posts: 10
Joined: Sat Jul 23, 2011 12:35 am

Post by TheHyperborian »

Well recast also is just a navigation mesh library, it uses a more advanced algorithm to find the walkable areas, and it comes with an library called Detour that does steering and AStar path finding. You can query the geometry of the mesh for the AI to do spatial reasoning but it isn't going to automatically going to do those things for you.
Electro
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia
Contact:

Post by Electro »

Yeah I was looking into seeing how practical it'd be for my Quake bot a while ago. It uses voxels at first, but then throws that data away in favour of storing a single series of surfaces for the ground to determine the walkable area. It'd be a lot nicer and more like AAS in ways, if it kept the 3D information for things like water, or flying AI etc.

For general monster AI I think it'd be great, but for my bots I just can't see how automatic generation methods would get the more complex jumps that rely on air control.

I also did experiments with automatically generating waypoints using flood fill methods, then testing paths between every item and angle checks etc. to cull the amount right down to an acceptable amount, this still was only enough for decent basic navigation at best (I'm VERY picky and was striving to get the AI to be most human-like I could). Not having them do complex jumps was a big downer, especially for how much time I'd already invested into automated methods, when I could have just placed the waypoints/nodes manually and had much more efficient and nice results.

I really am looking forward to what you can get going with it in Quake :)
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
TheHyperborian
Posts: 10
Joined: Sat Jul 23, 2011 12:35 am

Post by TheHyperborian »

Ahh, well I did triangulate the BSP using a delauney algorithm to cut the n-gons into triangles, but I think there was a floating point error somewhere because recast was giving me strange navigation meshes from that data. I will have to look because I'm sure I did something wrong in the triangulation code. You're free to use it for your bot, I'm not really working on bots tho. You will have to query the navigation mesh and reason with that data to figure out the slopes, and where you can jump to, and stuff like that. I have not figured out Detour yet tho, it might give some spatial reasoning information like area awareness for a bot.
Electro
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia
Contact:

Post by Electro »

What do you mean by reason with the navigation meshes? The whole point of a navigation mesh is to already have the connectivity data readily available and the actual areas that can be navigated (spatial reasoning). Detour is just pathfinding, at least the last time I looked that's all it did. It's basically just a working A* in the structure that Recast likes.
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
TheHyperborian
Posts: 10
Joined: Sat Jul 23, 2011 12:35 am

Post by TheHyperborian »

Electro wrote:What do you mean by reason with the navigation meshes? The whole point of a navigation mesh is to already have the connectivity data readily available and the actual areas that can be navigated (spatial reasoning). Detour is just pathfinding, at least the last time I looked that's all it did. It's basically just a working A* in the structure that Recast likes.
What I mean is using that information to make decisions. You could query the navigation mesh to see if there are any areas that the bot can jump to, if it's on a ramp, if there is a ledge above it that it can rocket jump to, that sort of thing. Recast gives you a navquery object that you can query the mesh for that kind of thing but it doesn't give you any kind of steering or functionality to actually move the AI around on it. It just builds a set of convex polygons you can work with to navigate.

Detour does more than just Astar but I don't know all that it can do yet.
Electro
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia
Contact:

Post by Electro »

Ah right sorry, yeah the wording just threw me off a bit :)
Where are those vids! hehe
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by revelator »

I use CodeBlocks actually, I didn't know it could load a MSVC project I will try to load one with it and see if it works.
latest svn can even load msvc2010 projects :) theres ofc a few things that will need attention. like quakes asm code (does not work with mingw, allthough it should since its old gnu assembler code) so you need to disable that by removing the define in quakedef.h that turns it on.

doesnt matter a lot with todays hardware so its relativly safe.

to import a project from another compiler open file.

import project is in the drop down menu :) if you allready use codeblocks make sure you have the latest version, many fixes
has made it in since the 8.05 release.

if you need a more up to date mingw than what comes with codeblocks by default let me know.

i maintain some mingw builds of the latest gcc compilers (both 32 and 64 bit).
TheHyperborian
Posts: 10
Joined: Sat Jul 23, 2011 12:35 am

Post by TheHyperborian »

Thanks reckless for the info.

I'll get around to this, and eventually find a place to put the code up to, but right now I am removing QuakeC and putting Lua into it. I know many people will think it is blasphemy, but QuakeC is really not a very good scripting language. With Lua I will be able to use it as a sandbox from the console in the game and do alot of things I'd like to do that QuakeC makes difficult because of the way it deals with structures in C.
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by revelator »

np m8 :)

i dunno about if people would call it blasphemy but i reckon some would argue that it needs to keep compatibility with standard quake.

maintaining the above can really be a pain but in a way understandable
in case the developer in question drops the project before any compatible game data has even been made it would have been a waste.

tenebrae2 could have been a new quake like that but the project maintainer got hired by the company that made enemy territory
and dropped the project, so the only game you can play on the beta
version of the engine is an alpha of industry heh.

but i understand the feeling :) in the end its up to you what you want to do with it.
TheHyperborian
Posts: 10
Joined: Sat Jul 23, 2011 12:35 am

Post by TheHyperborian »

reckless wrote:np m8 :)

i dunno about if people would call it blasphemy but i reckon some would argue that it needs to keep compatibility with standard quake.

maintaining the above can really be a pain but in a way understandable
in case the developer in question drops the project before any compatible game data has even been made it would have been a waste.

tenebrae2 could have been a new quake like that but the project maintainer got hired by the company that made enemy territory
and dropped the project, so the only game you can play on the beta
version of the engine is an alpha of industry heh.

but i understand the feeling :) in the end its up to you what you want to do with it.


Well it will be able to play Quake, I am converting the QC files to Lua that come with Quake. My goal though isn't to play Quake but to use the engine as a platform for new mods, a platform to experiment with, an build that will make it easy for someone to quickly pick up and prototype a new game design. While it will play Quake, it might not play it exactly like the original. It isn't my goal, but anyone can freely borrow what they like from my build and use it however they want. The reason I am using Quake is because 1) It's open source 2) there are tons of tools available for it 3) I want to expand it and make it available for anyone to use to develop new games with it, especially for newbies, who might have done a little dark basic, they can jump write in. That is why Lua is a much better alternative to QuakeC for what I want to do, it will allow beginners to get into learning how to do game programming and develop their own games with it without having to touch the C code.
Post Reply