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... 

If you want to do routing properly, you really ought to do it on another thread - that means some engine extension to do it.
That said, doing it in the engine has certain issues, including not knowing what a teleporter is. 

Teleporters aren't too bad. If your system allows for manual linking, you simply link nodes between both sides and sit them inside the teleport trigger.

Doing it in the engine though, that'd be pretty nice, but if you're going that far, you may as well get compiler support and make AAS files. I was really impressed with the D3 AAS generation. 

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!

Yeah that is the downside to manual node layouts, but it is not really that much work because you can added/updated the nodes using -onlyent compiles. I also found that less nodes often produces better results than trying to saturate an area with complex setups.

Here is the numbers for my two test maps:

S1M1 - 123 Nodes, 61 Vol Nodes, 23 Volumes
S1M2 - 129 Nodes, 67 Vol Nodes, 15 Volumes

The volume nodes are linked to the nodes, they are the high pass route choices. The volumes are brushes defining zones to the map for nodes.

I am still a firm believer that manually designed routes produce more robust results and with the right debug options you can easily find problems and fix them. Which is why I spent so long creating them. You can drop down start and destination markers, work out which nodes to go to first (pretend you are the AI) and then follow the path through the node network visually.

If you want to do routing properly, you really ought to do it on another thread - that means some engine extension to do it.
That said, doing it in the engine has certain issues, including not knowing what a teleporter is.

That would indeed be awesome but based on my experience of Quake engine devs there would probably be 3 different formats not compatible with each other and LDs wondering which format to work with! ;)

The hardest part of node networks for me is lift/platforms because the AI has to wait for platforms, get on them correctly, wait on the platform and then get off. Pausing AI and switching them between stationary and mobile is awkward with the current QC structure. 

"I am still a firm believer that manually designed routes produce more robust results"

Coming from a UT mapping background originally I can honestly say once you got a nice path network going and you followed a bot that could navigate your map properly it was a great feeling of satisfaction.

I envy what Polge did for UT, it's a shame that he didn't flesh out his Reaper Bots for quake a little more. :) 

A maximum number of entities that can be searched through with the find function?

I'm using it to search through randomiser entities and it seems to be provoking a crash now, as the map and number of entities has grown in size. 

it's possibly you're hitting the 100,000(?) operations per frame limit.

In a given frame, you can do 100000 operations before the engine thinks you're stuck in an infinite loop. This includes all operations done before you hit your loop and all the operations done after your loop, so you can get through your loop fine only to crash on subsequent operations done after.

the solution to this is to defer the search after n loops to the next frame by saving the last entity and starting from there instead of world. 

Just talking with Sock about it.

I threw in some delays and it certainly seems to be the case. The size of the map is basically breaking this limit.

What I'm doing is randomising monster position, and the code I'm using is searching the entire entity list to do so.

If I chained the entities it'd work much better, but that's a massive amount of work.

Not using randomisation would have the benefit of more precise monster placement and not having to rewrite the code and map.

Just delete a load of entities from the map.

Thanks, seems like the way ahead is clear!

I could rewrite, but it'd take a lot of time. In future projects I can take this limitation into mind and use stuff which has nextthink = time + random(); or similar. 

I'm removing all the randomiser entities and replacing the monsters traditionally.

This'll give me a playable level.

I've got in mind a randomiser system that would be supported by the single thread engines that Quake uses.

Basically it flagging monsters as RANDOMISED (additional to the SPAWN_SILENT, SPAWNED and SPAWN_ANGRY flags).

Each monster would have keys to denote their randomiser grouping. These keys would be rname, rnext and pool.

rname and rnext would copy the door code to produce chain grouping. This would make things much lighter when using the find function. Erroneously configured chains would have a failsafe to make sure they'd always be a loop.

All monsters in the same group would randomise their positions between the others in the group, any monster ending up in another position would also inherit the target of that position (to point at the relevant path_corner or trigger_counter) if a monster didn't have a target then this would clean any target held by the arriving monster. The difficulty flags and targetnames would remain unchanged.

Monsters with pool set to 1 would never add the position etc. to the randomisation group, but could take the place of other monsters. Possibly there'd be other functionality for pool, which is why it should be a key and not a flag.

Basically this means that the monsters not set to pool 1 define the positions used for spawning and how many monsters will be spawned.

Monsters would only be randomised when spawned, so quick loading after dying would re-randomise the monster positions as they would be retriggered.

This would produce a system optimal for the engine and simple for the mapper, even though it involves a flag and three separate keys.

Probably won't do it in this project though. Maybe next time. 

This would make a monster not spawn. The utility would be placing three shamblers for example, but only one appears. 

I mean, pool 2 would make a monster part of the group, but not increase the amount of spawns for that group. 

So apparently you can use "Code::Blocks" as an IDE for QuakeC, with autocomplete and all that shizzle.

Anyone use this? I followed the instructions here: http://ouns.nexuizninjaz.com/dev:programming_introduction#working_with_the_code

But I can't get the pissing thing to work properly - my symbols tab is empty and it can't find any of my functions or do autocomplete or any of the things which would make it better than, you know, notepad.

Has anyone else got it working for QuakeC? 

Gave it a try, but I don't know the first thing to do with codeblocks, so didn't get very far.

Did notice that the lexer_qc.xml file has a bunch of typos in the keywords though, so it's not going to be highlighting .vector, continue or default any time soon... 

I noticed all those typos too. Doesn't fill me with much confidence to be honest. 

more like lol 

Coming from Java, this C++ stuff is confusing to me...

I have this class which is meant to be an Interface:
class PhysObject
{
public:
virtual void evaluatePhysics() = 0;
protected:
Vec2 velocity; //physicalized objects have velocity
PhysObject() :
velocity(Vec2())
{}
};


Then I have this other class that implements PhysObject:

class Particle : public PhysObject
{
public:
Particle(Vec2 pos) :
position(pos),
size(Vec2(4, 4)),
releaseTime(Game::Time() + 1),
PhysObject()
{}

void evaluatePhysics()
{
this->position = this->position + (this->velocity * Game::FrameTime());
}
...
};

But when I call this->evaluatePhysics() on the Particle object, it crashes with access violation 0xCDCDCDCD which the internet tells me is caused by dereferencing a null pointer. So it looks like my evaluatePhysics() implementation in Particle never actually took, and it's still trying to call the Interface's evaluatePhysics() = 0 pointer.

Any hints? 

I think you just need to add 'virtual' before 'void evaluatePhysics()' in Particle.

Also, sounds like there's a new c++11 feature where you can stick the "override" keyword after the function args in Particle, like this:

virtual void evaluatePhysics() override
{

which will make the compiler check that this evaluatePhysics() is actually overriding something from the parent class. 

no dice, neither from adding virtual or override. :(

From what I've read, once you put virtual on a method, everything from that point forward will always be virtual, ie: behave as expected of a polymorphic object and properly call child class methods if held in a base class container.