That are set up with proper pathing? Like in unreal? 

you'd need to write an a-star algorithm in QC and lay down a veritable shitbiscuit of triggers to acts as nodes.

It's not a great language to do that in tbh but i think it's been done in the past. 

Wouldn't that work? 

 

you need to write the underlying system that dynamically creates the sequence of path-corners the monster needs to follow to get from where he is to his goal. 

when i said "trigger" i meant whatever entity you create to represent your a-star node. 

It's not a great language to do that in tbh but i think it's been done in the past.
Did you play my ITS mod? I wrote an Article on what AI system I wrote in QC and how it works, ingame/editor shots as well! 

I was talking more about this stuff: http://en.wikipedia.org/wiki/A*_search_algorithm

Your system looks pretty hand-placed but if it works for basic quakery, then it's all good :} 

Necros did a similar system with nodes, generating best paths from node networks and then setting the AI on that path. The problem with that system is, it can be CPU intense to generate the path every time (especially vertical complex levels) and if anything changes (player / environment) it becomes out of date quickly.

I personally elected for a dynamic system, the AI knows where it wants to go (final objective) but trusts the node network to reach there. The AI find the nearest node, finds the best direction and then starts following the network.

As the final destination (player) keeps moving the AI keeps adapting using the node network. The minor navigation (around rooms) is left to the node network while the high level signposts stuff is done via volume brushes.

Its not perfect but it does cope with fairly well with moving objectives (player) and even gets the AI back to what they were doing before.

The downside is the node network has to be hand placed and the network has to be validated / connected together when the map loads. 

This is an interesting read on making a dynamic system that follows simple empirical rules.

https://www.quaddicted.com/webarchive/minion.planetquake.gamespy.com/tutorial/main.htm 

A word about A* pathfinding being cpu-intensive... I've coded a couple of A* systems for games in the past, and if you can create a sort of heirarchical A*, it's incredibly fast (basically you do pathfinding on a heirarchy of graphs, starting from the coarsest and working down - e.g. "region nodes", then "room nodes", then "nav-tri nodes")

e.g. once you get down to the point where you need a path between individual navtris, you only have to find a navtri path between nodes on the next graph up (e.g. just between adjacent room nodes)

This already makes it blazingly fast, but you can still get spikes if you need lots of paths all at once (e.g. lots of monsters all going at it) - I handle this by amortising the algorithm over several frames and also queueing up requests, so they are processed for each monster in a linear fashion. The upshot of it all is basically no performance impact whatsoever.

The creatures have simple fallback behaviours that they can do whilst waiting for their paths to be processed, but I find the delay is so small it's never noticeable.

But, yeah I wouldn't wanna do it in QC... 

Navmesh. I haven't personally implemented this before, but have worked with it quite a bit.

As I've seen it throws voxels at a map and creates polys where possible. The quake equivalent tech is probably the vis process, with leafs instead of polys.

Ai navigates between the polys, path finding to their ideal destination.

Incredibly slick system, works amazingly well. They used a terribly shitty version of this in L4D... We analyzed it and it was puzzling why it was so bad, when we stole ours from an online tutorial and it worked like a charm.

I suppose they were worried about more important things though, like not making a game that sucked. Our game sucked, but I'm not going to say which it was since it got universally panned.

All this makes me wonder if a similar approach could be applied to the vis data though, using ray casts or something to construct chains. Wouldn't work for areas that monsters can't navigate though, like vertical drops and the like.

Detail brushes would also cause problems. 

Also you make an interesting point with vis connectivity.

One thing I've been meaning to do is dig around to see how the doom3 AAS is generated - that's another system where the graph is created procedurally with almost no work from the designer required... 

I handle this by amortising the algorithm over several frames and also queueing up requests, so they are processed for each monster in a linear fashion. The upshot of it all is basically no performance impact whatsoever.

I've had to do this as well; ne_ruins didn't have it though.

Deferring the path solution over multiple frames works very well and I remember testing giant horde maps with a hundred monsters all able to path without any slowdown at all. The only downside is that the more monsters there are, the longer it can take for each AI to have it's turn at getting a path generated for it.

The last optimization that I have yet to implement is having a monster save a generated path.
As it is now, I regen a path every time an AI hits the node it was heading towards. This is pretty expensive, especially in node-dense areas. If an AI could get a path generated and remember not just the next node, but all the nodes that make up that path, it could treat it's A* path like a series of path_corners and be very cheap to run. 

But, yeah I wouldn't wanna do it in QC...

In hindsight it was a crazy idea, but I did learn a load of things about AI. When I finally got the Quake monsters to path around a map avoiding obstacles and hunting the player it was an awesome feeling of accomplishment.

I did look at necros QC but soon realized I was going to struggle with the idea, I am designer not a coder. In the end I decided to go with a simple path node system (like in heretic2) with some extra helper options (jump, shoot, path choice) so that the AI can look intelligent when the player is around. I even wrote a ton of debug modes for tracking down errors in the pathing routines so it was easy to find out where things were going wrong. 

I assumed you'd used the frikbot code, since the behavior was so similar in many respects.

One rainy day I'll dive into that and see how to link it into the monster ai.

It almost never rains in Chile. There are more earthquakes than storms. 

I assumed you'd used the frikbot code
A couple of people said this to me, but I did not look at the Frikbot code, because I assumed it was a new engine. The problem I found with implementing AI changes is you can end up replacing so much of the underlying QC that it is often difficult to integrate into existing progs. 

This is what happens when you first attempt it. Once you've got a handle on things you start to make ai changes that work in tandem with what's in the original game.

One of my favourite bits of code is the additions to trigger_monsterjump; only enraged and only melee. Basically an idea stolen from the Quoth drolejump, that have proved incredibly useful.

I've been throwing around ideas for trigger_alarm and trigger_guard, also for a special type of path corner that would override the monster's move goal during combat. Basically conditional things that you place when mapping to provoke behaviour that fits your level.

Crude stuff compared to a node system, but I've seen promising results from some of these ideas so far, just because they're level customized rather than 100% generalized. 

The last optimization that I have yet to implement is having a monster save a generated path.
As it is now, I regen a path every time an AI hits the node it was heading towards. This is pretty expensive, especially in node-dense areas. If an AI could get a path generated and remember not just the next node, but all the nodes that make up that path, it could treat it's A* path like a series of path_corners and be very cheap to run.

This is probably the main reason I wouldn't wanna do it in QC. In QC each generated path would be a linked list of entities I imagine - and there'd be huge amount of them if each monster had his own set.

Could be worth looking at heirarchical pathfinding, where you have seperate graphs at different scales. e.g. let's say your map is divided into 5 broad regions. These are your highest level nodes, and you start by creating a path through these region nodes. Now, starting from the region the monster is in, you know which adjacent region you need to head towards, but to get from region to region you need to navigate a more detailed graph, made of say "room nodes", but because at any one time, you are only ever concerned with navigating into an adjacent region node, you only need to consider the room nodes in your current region, which clamps the max. number of room nodes in this next path to a pretty manageable number. Then once you need to navigate from room-room, you might still need a more detailed graph using another type of sub-node (each room would have several of these), but again you only need to consider just those sub-nodes in the room you are in to lead to the next room....

I hope that makes sense.

The upshot of it all is that it massively, massively reduces the number of pathnodes you'll need to process and store at any one time. 

Could be worth looking at heirarchical pathfinding, where you have seperate graphs at different scales.

This is essentially what I am doing with my node network except I am using a terminology which is probably misleading. I essentially create a series of large brush entities and when the client starts, I store their volume bounds, reduce them down to a point entity and make sure they are non interactive with the world.

I generally create a loop of nodes in a room linking all the doorways. I then place special volume test entities on top of the nodes and link them together. When an AI arrives at a node it does a simple bounds/volume test on the final destination and if correct goes through the doorway on to the next set of nodes.

It is really easy to cut up a level into 5-10 volumes and being as they are visual in the editor it is easy to place them as a LD. I even added and/or/not logic to the volumes so AI can test several volumes together for a much better test of destination.

Once you've got a handle on things you start to make ai changes that work in tandem with what's in the original game.

The problem is the original game AI design is terrible, they essential run in a straight line bouncing off architecture in order to find their way. It is extremely easy to create architecture that breaks this and essentially the player is just shooting fish in a barrel as the AI run endlessly trapped on ledges or round in circles in lower areas of rooms.

Most Level Designers for Quake compensate for this AI flaw by using range/flying units which evens out the playing field for the monsters. 

I did some last-ditch bodges in my (released) quake maps where I identified some areas in the game where monsters got stuck, like in spiral stairwells and stuff, and added some path corners leading out of there and logic that said things like "if player is above you follow path forwards, else follow path backwards".

Stepping back for a bit, my opinions on pathfinding in Quake have been a bit back and forth over the years. I've always leaned towards just leaving the AI alone. I think one of the things with Quake is that monsters are so aggressive that it actually works to the game's advantage that they are a bit shit at chasing the player. Typically when you have an encounter, you want the option to back out of it and not have the monster chomping at your heels the whole time. Sometimes they chase you, sometimes they don't, and I like that. 

I've always leaned towards just leaving the AI alone. I think one of the things with Quake is that monsters are so aggressive that it actually works to the game's advantage that they are a bit shit at chasing the player

My mod needed the AI to hunt the player down, it would have been a very poor stealth game if the AI could not even exit a room or get back to what they were doing before. I can see the attraction of Quake AI being left alone, they are easy to break, but when a monster does something (eg monster_jump) surprising like hunting you down, then it gets more exciting! (well for me) 

I like them to do cleverer stuff, although it's tricky to do it without also giving them super powers.

Like the aiming ogres that added speed to their grenades in order to hit the player. 

The problem I found with implementing AI changes is you can end up replacing so much of the underlying QC that it is often difficult to integrate into existing progs.

Yes, this is the really unfortunate part. I've been trying to write a simple tutorial where I could provide the main A* component and then someone could just go in and hook it into their mod, but there are so many little bits that have to be added and so much that is flat out replaced that it's not simple at all to write the tutorial. :\

Sock: Your method is very cool, but I find it is really fiddly with adding in the nodes because you have to tweak it for each area. The results are better but it's more work and I am super lazy: I prefer just throwing down nodes and letting the code sort itself out!

Kinn: I have considered doing the coarse graph -> fine graph approach. For some reason, using a large brush and auto-linking them the way Sock is doing never occurred to me and I always assumed I'd have to do a lot of manual linking which is why I never bothered... This is worth some more thought, I think.
Also, yes I have some utility functions that make linked lists, queues and stacks out of entities. There is a queue of entities that tracks which monster is next to get a path generated, for example.
If you're using fitzquake or a variant, it's less of a problem since you have up to 32000(?) entities to play with and since they have no models attached to them, they don't actually cause overflows or anything. 

Also, yes I have some utility functions that make linked lists, queues and stacks out of entities.

This is something I was also considering for a series of tutorials - I have a nice way to make generic "container" functions using a trick with field pointers. Maybe I'll start on that next...