Possible solution to JA's terrible NPC way-pointing?

[Dusty]

I found an interesting snippet of code in JASP:

void NPC_AvoidWallsAndCliffs (void)
{ /*
	vec3_t	forward, right, testPos, angles, mins;
	trace_t	trace;
	float	fwdDist, rtDist;
	//FIXME: set things like this forward dir once at the beginning
	//of a frame instead of over and over again
	if ( NPCInfo->aiFlags & NPCAI_NO_COLL_AVOID )
	{
		return;
	}

	if ( ucmd.upmove > 0 || NPC->client->ps.groundEntityNum == ENTITYNUM_NONE )
	{//Going to jump or in the air
		return;
	}

	if ( !ucmd.forwardmove && !ucmd.rightmove )
	{
		return;
	}

	if ( fabs( AngleDelta( NPC->currentAngles[YAW], NPCInfo->desiredYaw ) ) < 5.0 )//!ucmd.angles[YAW] )
	{//Not turning much, don't do this
		//NOTE: Should this not happen only if you're not turning AT ALL?
		//	You could be turning slowly but moving fast, so that would
		//	still let you walk right off a cliff...
		//NOTE: Or maybe it is a good idea to ALWAYS do this, regardless
		//	of whether ot not we're turning?  But why would we be walking
		//  straight into a wall or off	a cliff unless we really wanted to?
		return;
	}
	
	VectorCopy( NPC->mins, mins );
	mins[2] += STEPSIZE;
	angles[YAW] = NPC->client->ps.viewangles[YAW];//Add ucmd.angles[YAW]?
	AngleVectors( angles, forward, right, NULL );
	fwdDist = ((float)ucmd.forwardmove)/16.0f;
	rtDist = ((float)ucmd.rightmove)/16.0f;
	VectorMA( NPC->currentOrigin, fwdDist, forward, testPos );
	VectorMA( testPos, rtDist, right, testPos );
	gi.trace( &trace, NPC->currentOrigin, mins, NPC->maxs, testPos, NPC->s.number, NPC->clipmask );
	if ( trace.allsolid || trace.startsolid || trace.fraction < 1.0 )
	{//Going to bump into something, don't move, just turn
		ucmd.forwardmove = 0;
		ucmd.rightmove = 0;
		return;
	}
	

	VectorCopy(trace.endpos, testPos);
	testPos[2] -= 128;

	gi.trace( &trace, trace.endpos, mins, NPC->maxs, testPos, NPC->s.number, NPC->clipmask );
	if ( trace.allsolid || trace.startsolid || trace.fraction < 1.0 )
	{//Not going off a cliff
		return;
	}

	//going to fall at least 128, don't move, just turn... is this bad, though?  What if we want them to drop off?
	ucmd.forwardmove = 0;
	ucmd.rightmove = 0;
	return;*/
}

It's declared in NPC.cpp and it's called by NPC_ExecuteBState later on in the file. It wouldn't be so bad for NPCs to be able to run around outside the waypoint system here and there if we knew that they would stop before a drop or not try to run through walls. 

 

[mrwonko]

I wouldn't call the waypointing terrible; it's just the map creator's responsibility to include a proper waypoint network.

[eezstreet]

Thread moved to Coding and Scripts

[ensiform]

The solution is navigation meshes instead of waypoints. With areas for combat/camp instead of points.

 

The bots are tbh worse than NPCs.

[Cerez]

Personally I would love if we implemented a simpler (and more intelligent AI) system for NPC movement. Collision and terrain-based danger avoidance, and automatic free movement (without waypoints) AI would be fantastic, and would allow us to do such much more with bringing levels to life with civilian NPCs, etc., now that we have computers with way higher processing powers than the specs the game was initially designed for.

 

It would allow for an RPG game-like environment within JKA's action-based levels, and add spontaneity and a deeper level of immersion into the game's world.

 

Manually having to script/graph pathways is good for defining specific movement for a particular NPC, but it shouldn't be the de-facto standard for all NPCs to move by. The NPCs should be loaded with automatic movement/behaviour AI by default, and fall back to it when something goes wrong with the waypoints.

[mrwonko]

Manually graphing pathways is the de-facto standard for all NPCs to move by in all games. There's often some degree of automatic graph generation involved, but it pretty much always still has to be hand tweaked for good results.

 

But you're welcome to write something better, of course.

[Cerez]

If I get some time, I might try something. I feel that this method is outdated. Why should we *have to* graph pathways. A specific AI could be implemented to handle random walking behaviour for an NPC, for example. Or a method of avoiding collisions while heading towards a distant waypoint.

 

Having to graph every single NPC's walking pathway is a tedious and unnecessary de-facto standard in my opinion. I would call it old-school. It may be good for optimisation purposes, but it's not something that really helps world design and development -- unless there is a very specific or challenging movement you need the given NPC to execute.

[ensiform]

Recast, detours and a*

[Xycaleth]

Having to graph every single NPC's walking pathway is a tedious and unnecessary de-facto standard in my opinion. I would call it old-school. It may be good for optimisation purposes, but it's not something that really helps world design and development -- unless there is a very specific or challenging movement you need the given NPC to execute.

The alternative which games use is to create navigation meshes, which basically describe the walkable areas of a map. These are usually automatically generated, but some older games like Left 4 Dead 2 still require manual creation of these. I experimented with adding navigation meshes to JKA but didn't get as far as integrating it into the NPC's AI:

 

 

The blue overlay you see there are the areas which NPCs can walk on. I had a version where stairs were covered too but I can't find that screenshot anymore.

 

Anyway, this would give the NPCs a lot more freedom as to where it can travel on the map, and with very little input needed by the artist.

[Asgarath83]

I Agree with @@Cerez

maybe is possible to make a custom system/ shader navigation mesh that work like the cushion.

cushion avoid NPC to take damage if they fall by high cliffs. a nav mesh shader maybe can be placed like a cushion, or a fog into the floor of the map and NPC that touch the box can be drived with a system of auto walking \ running \ patrolling \ autoavoiding walls system in the designed area. That's wold be greate.

On the edited map for SP adaption for my mod i ever created a waypoint grid for allow  npcs movement. it's not  a long work if you use copy paste function for clone waypoint and connect it with control+k, but it can take some hours with larger maps.

the waypoing connection grid however need the waypoints are ever connected and relatively closer. and it get some really trouble with func brushes. npc have some serious problem to walk over a door if is not good wayponted.

[mrwonko]

Why should we *have to* graph pathways.

Because otherwise the problem space is too large to calculate in real time.

[Dusty]

The way I see it, waypoints would still be necessary for navigating from Point A to Point B in any intelligent sort of way. But right now they are also pretty necessary to keep NPCs from doing silly things like running off drops. There are also lots of areas in maps where it wouldn't make sense to add NPCs because there are no NPC-no enter areas to keep Jedi from running off edges. Heck even in some SP maps in areas where Jedi are supposed to be like t3_hevil there are not properly placed barriers = reborn running off edges trying to get to you. I also feel uncomfortable letting a stormtrooper run away from you if he's not using waypoints because he might just do the same thing.

 

You can say "it's the mappers responsibility" and maybe it is, but it's a little difficult to fix/expand the waypointing of a map in JA considering we have non of the original map files. 

 

This idea Raven has seems pretty simple to me. Check if there's a large height difference in the vertical direction in my current path of travel, if so, cease any movement in that direction and turn a little bit until it's no longer true.

[ensiform]

Waypoints aren't necessary.  The path solver determines the path to take (IE A*)

[Xycaleth]

The path solver uses the waypoints to find a path...

[ensiform]

It can be used to find a path in nav meshes too.

[Dusty]

What are nav meshes exactly? Is it something a mapper must place -- is it a similar concept to an NPC-no-enter area except expanded? Or is it some kind purely AI calculated type thing? Is it what Xycaleth shows in his picture? If so, it seems kind of unnecessary to me, at least purely for solving cliff-avoidance issues, unless if you want to get more in-depth than that (walls, obstacles etc.) or more intelligent about the avoidance. I would be satisfied with just stopping at a cliff even if it leaves the NPC stuck temporarily. 

 

If you guys want to talk about nav-meshing and waypointing that's fine, but when I made the topic, I guess one thing I was wondering, was does it look like Raven's solution was going to work? It was hard for me to decipher exactly, because I'm not sure how all of their vector and trace things work...

[ensiform]

Navigation mesh is what xycaleth showed yes. I would say it's more optimal than waypoints because it's not as rigid. Plus if you think it's unnecessary why it basically the standard of most major engines? Ue3 and 4 use a form of navigation meshes. As does newer versions of source for l4d, cs bots and tf2 bots. Other engines use it too I'm sure. The point is, you can have it be done in a simple command and it wouldn't necessarily be manually placed. Fine tuning will always be something you may have to do it just depends.

The A* path system can be used with waypoints and navigation meshes. It's just an algorithm to find the fastest route.

[Dusty]

So usually nav mesh doesn't need to be explicitly set up by the mapper? In that case that sounds really cool. My apologies for not understanding sooner.

[ensiform]

Well it depends on the implementation. It would have to be set up by the mapper in some form. It just depends on which process is used to generate it.

[Asgarath83]

mmm i think that need 3 fix:

1: a little code fix for implementing nav mesh function into the code of the engine of MP - SP .

 

two way of insert it:

A: via gtk radiant with some custom version of gtk radiant program with a new function that create automatically a nav mesh inside the map structure, based to the map geometry itself. (like the generation of .PRT files when the map is builded into BSP. maybe can create a file BSP and a file .NAV with the navmesh settings? )

B: a Brush navmesh shader, that works like the trigger shader... basically, the brush with "nav mesh shader" shoul be place on the area when NPC moving, walking and running, and it enable the advanced AI navigation system of their intelligence for avoid walls or cliffs or not be stucked in a place in absence of waypoint nearest (shooter NPC need waypoints for move, or they never walk or run. saberist, instead, can walk and chase enemy also without waypoint. enabling the chasing, running for shooter with a nav mesh shader, , should be really cool)..

the nav meshes, maybe can be created like the fogs? a simple square brosh textured with system/navmesh shader that activate the engine features?

so, this need to be placed by the mapper, in this case, but it can be done very quickly.

[NumberWan]

Waypoint work very strange sometimes, well, for me it was a problem when I had a location, which can be achieved by wypoints through 2 identical areas. When NPC would pursue a Player, he would use path A or B in order to get the Player in the final point. However strangely, if the Player moved slightly closer to path B, when NPC was n Path A, he would start running back to use path B, while in real life it was more logical and faster to complete Path A and kill the Player like that.

 

The problem with the walkable areas instead of waypoints could also be in cases, if the floors are different in one room. Like in the Bespin level above. It would be logical, if some NPC (which isn't a Force User for isntance) in order to get from upper area, would use stairs first and then get down. In other cases NPCs would ignore some parts and jump, where normally a living person wouldn't do that.

 

In any case waypoints seem to be of better use in a Map, because if it's large, you would have to do a lot of work placing special brushes everywhere. The process should be automatic then, otherwise it's time-consuming.

[ensiform]

It wouldn't be integrated as brush work at all. It would have a process to read the bsp to generate the mesh. There might need to be some work in cases of jumping and such for connections to areas for force jumping.

[dark soul]

@@Cerez i guess im working at something like what you want, I mean the RPG thingie.

 

I'm with a mod and I intend to recreate "life" so that it's not a dead city, with cantinas etc... if you are interested hit me up and I'll send you a vid or something when I get the poc ready

[eezstreet]

The solution to fix JA's terrible waypointing is to...fix JA's terrible waypointing. The problem (and I've always asserted this, over and over) is the terrible waypointing that is done in the maps. Do you want an example of AI that is perfectly waypointed? Try looking at what JK2 did with their maps. A lot of this can be fixed with map modding. Granted, the code in JKA is a bit different, getting it to be at JK2-level isn't hard.

[Futuza]

I like the idea of having modern nav meshes integrated into gtk/q3map...especially since it sounds like Xycaleth already has something started. Has ioquake done anything similar already?