[Mark]

I noticed something in that video that I would like to have in my projects. The actor moving forward without the side to side jitters or turning. But unfortunately that is built into the default AI commands. It was annoying to watch zombie models doing that in the Decay and Graveyard TCs rather than do a straight shuffle towards the player.

[MetHy]

This looks very promising. Applying this to Duke enemies JUST so they know to walk along walls rather than bumping against them indefinitely would go a long way to make them as effective as Blood's cultists and zombies.

[Sangman]

Does the pathfinding account for (destructible) spritebridges and sloped floors?

Reaper_Man, on 11 December 2020 - 09:58 AM, said:

https://gfycat.com/h...ecommabutterfly

Checking over the obstacle avoidance penalties. AIs can be told to avoid terrain hazards (things like damaging floors) or placed objects, like explosive barrels. Or this system can generally be used to make AI prefer certain paths over others, IE walking through a jungle and following a trail, rather than going in a straight line. Hint actors can be written to influence the penalty on map load as well, so mappers can place actors to finely tune how the navigation is handled on their map.

Not sure if I get it, in the gif you can literally see the actor walk over slime where he probably shouldn't

[Reaper_Man]

I've been working through some performance bottlenecks. On the upside, I've reduced the number of distance checks in my test environment from 258,000+ per each call, down to around 4,000. I can reduce this even further when I implement a different heuristic that doesn't require calling the square root function.

The bad news is that there are a minimum of 1,157 iterations through the various for and while loops, with a total of 572,000+ in my test environment. I'm not sure if I can simplify this further, since this number is determined by how large the map itself is - my test map creates 1,156 node points and it's relatively small. Increasing the node density causes an (expected) exponential performance loss.

The simple solution is to have node placement be determined by map makers, which I'm getting closer and closer to the point where that may be the only viable solution. I'd really like this to be a drag-and-drop solution, but that may be asking too much from the engine.

Mark, on 11 December 2020 - 10:06 AM, said:

I noticed something in that video that I would like to have in my projects. The actor moving forward without the side to side jitters or turning. But unfortunately that is built into the default AI commands. It was annoying to watch zombie models doing that in the Decay and Graveyard TCs rather than do a straight shuffle towards the player.

MetHy, on 11 December 2020 - 10:56 AM, said:

This looks very promising. Applying this to Duke enemies JUST so they know to walk along walls rather than bumping against them indefinitely would go a long way to make them as effective as Blood's cultists and zombies.

I agree, I've always disliked seekplayer and friend's weird behavior and wish I knew enough about the core engine to improve the AI at the source.

The reason they walk in straight lines here is because I set the actor's angle to face the nearest path node. Making one actor face another is the easy part, in theory you could do it with any enemy to replace a faceplayer call. I'm pretty sure there's an example code on the wiki too.

I'm not familiar with how Blood's enemy AI works, so I can't make any direct comparisons myself!

Sangman, on 11 December 2020 - 01:23 PM, said:

Does the pathfinding account for (destructible) spritebridges and sloped floors?

For sprite bridges, I'm not sure honestly. The answer is probably "poorly". They should handle TROR without issue because it uses line of sight checks for 2 points in space, and that should work for sprite bridges as well. But they won't necessarily understand how to navigate these sort of environments extremely well. As for slopes, they won't have any issues with them at all.

If you have a simple map with sprite bridges and/or TROR I can try that in testing.

[Reaper_Man]

Sangman, on 11 December 2020 - 01:23 PM, said:

Not sure if I get it, in the gif you can literally see the actor walk over slime where he probably shouldn't

The shortest path to the goal is a straight line (obviously), so the actor worked to avoid walking over the slime. It can walk over hazards if it finds that to be the best path. In this case he also had an issue of the navigation grid being too coarse, and so he cuts over the corner to from one point to another. This can be solved by making "slime" be more hazardous in the scoring system (this would be set in code), using a more fine navigation grid size, building maps with grid based movement in mind, or a combination of all these factors.

If the slime pool spanned the entire area, he would just walk straight through it to get to the goal. You could set some floor textures to be omitted from the navigation entirely, which in this scenario would cause the actor to return a "no path available" state.

[Jaap]

Reaper_Man, on 11 December 2020 - 01:51 PM, said:

The bad news is that there are a minimum of 1,157 iterations through the various for and while loops, with a total of 572,000+ in my test environment. I'm not sure if I can simplify this further, since this number is determined by how large the map itself is - my test map creates 1,156 node points and it's relatively small. Increasing the node density causes an (expected) exponential performance loss.

How about using sectors as rough navigation mesh to build a rough path and using navigation nodes to refine that path? My mod uses sectors to find paths, the performance is on the whole npc's navigate fairly okay (I do have a bit of a square mapping style tho).

Also, does this mean you are working on a mod again?

[pavigna]

Jaap, on 11 December 2020 - 11:33 PM, said:

How about using sectors as rough navigation mesh to build a rough path and using navigation nodes to refine that path? My mod uses sectors to find paths, the performance is on the whole npc's navigate fairly okay (I do have a bit of a square mapping style tho).

Also, does this mean you are working on a mod again?

This wouldn't really work well for maps that have lots of effects and such. just imagine a truck that moves, parks, and enemies come out of it. I'd build something like this and if you consider slopes, sprites and many other things guiding npc's with sectors becomes really tough. So, as a mapper, the best way for the enemies to work is just follow pointers set by the mapper himself.

[Reaper_Man]

Jaap, on 11 December 2020 - 11:33 PM, said:

How about using sectors as rough navigation mesh to build a rough path and using navigation nodes to refine that path? My mod uses sectors to find paths, the performance is on the whole npc's navigate fairly okay (I do have a bit of a square mapping style tho).

How well does your system handle areas with large sectors, or lots of "nested" sectors"?

I was actually looking into a system sort of like this, essentially performing 2 different searches from 2 separate sources. The first would keep track of sectors only (using their midpoints, and possibly wall or verticies) and this first iteration would build a list of valid sectors through which to build a path. Then the 2nd search would use A* and only search for points within those sectors.

However this presented some problems, since for example my test map uses a single giant sector, and so the initial search wouldn't improve the performance. There are real world examples of this as well, things like the city streets in many of the E1 and E3 levels come to mind. The slime avoidance example would also work the same way but for the wrong reasons - the AI would avoid the slime sector because that sector wouldn't be found in the initial search. Or worse, it would only find the slime sector and so the AI would never try to avoid it, again defeating the purpose of this sort of pathfinding.

Then I tried to build the node graph by looking at each sector, drawing a line from it's midpoint to every adjacent sector midpoint, and only generating nodes along those lines. Best case this only reduced my node counts 10% or so, but worst case, again using my test environment, it only created a handful of nodes in the middle of the slime pool because all of the sectors' midpoints are at roughly the same X/Y coordinates.

What I might wind up doing is doing a sector only search and pathfind via that, unless the target is within a certain distance to try and keep the overhead of the pathfinding low. I had the node grid size at 512 units and the paths it built are great, but there's noticeable hiccups every time it does a search unless the target is within 10,000 units or so, because the code runs through, literally, hundreds of thousands of loop iterations at that distance. It's a lot better when the grid size is around 800 or even 1000, but at that coarseness you start running in to navigation problems with tight geometry.

I also was attempting to build "modular" grid sizes, and I'm going to explore that more, but I then run back into a problem of performance due to some approximations that the algorithm is making. In order to reduce the number of distance checks (specifically calling sqrt) tens of thousands of times, I use a square root approximation. But this assumes that all points are equidistant on a grid, and variable grid densities breaks that. I really wish I could get an answer on how bad sqrt is to be calling, and if I'm chasing a ghost by trying to cut out as many of those calls as I can.

In the meantime, the easy solution is: just don't build your maps with areas smaller than 800 units that you want AIs to navigate through.

Jaap, on 11 December 2020 - 11:33 PM, said:

Also, does this mean you are working on a mod again?

I'm putting together a little something that I hope to be able to show off in the next few weeks.

[Danukem]

The nextsector member of the wall struct can be used to build a path. Basically you start from a target sector, write a recursive function that looks at sector walls and works its way back to the sector that your questing bot is in. If you have been saving a list of walls in an array, you will have a nice path saved, just have your bot traverse it in reverse order. If you want to find all the paths, do that and use the one with the smallest array at the end (although that will be the smallest number of sectors traversed, not necessarily shortest physical distance). I had some success with this several years back when I was working on a player bot that would directly input on the actual player and play the game by itself. It worked pretty well in my simple test maps. I did get it to finish E1L1 unassisted a couple of times, but it was rough going with pretty much any real map out in the wild. Nested sectors were a problem, so were oddly shaped sectors with narrow paths. And then there are just so many situations that come up that are hard to account for with code, like path that appears traversible but it is blocked by blocking sprites. Error recovery code was a major headache. I tabled it after a few months and haven't come back to it yet, but I still think the approach is promising.

[Reaper_Man]

Danukem, on 12 December 2020 - 01:01 PM, said:

The nextsector member of the wall struct can be used to build a path. Basically you start from a target sector, write a recursive function that looks at sector walls and works its way back to the sector that your questing bot is in. If you have been saving a list of walls in an array, you will have a nice path saved, just have your bot traverse it in reverse order. If you want to find all the paths, do that and use the one with the smallest array at the end (although that will be the smallest number of sectors traversed, not necessarily shortest physical distance). I had some success with this several years back when I was working on a player bot that would directly input on the actual player and play the game by itself. It worked pretty well in my simple test maps. I did get it to finish E1L1 unassisted a couple of times, but it was rough going with pretty much any real map out in the wild. Nested sectors were a problem, so were oddly shaped sectors with narrow paths. And then there are just so many situations that come up that are hard to account for with code, like path that appears traversible but it is blocked by blocking sprites. Error recovery code was a major headache. I tabled it after a few months and haven't come back to it yet, but I still think the approach is promising.

How did this system handle the teleporter drop right at the start of E1M1? Did you ever test this system in something like E2M1? Specifically the teleporter to the ship right at the beginning?

I'm not 100% certain that this method will work for me in terms of pathfinding from point A to B, but I can see this method used to validate if the target point is physically impossible to reach, such as through a teleporter or under/above water sectors, before wasting CPU time trying to pathfind to a physically impossible to reach goal. Basically a pseudo-flood fill as an early check before running through A*.

[Danukem]

Reaper_Man, on 12 December 2020 - 04:22 PM, said:

How did this system handle the teleporter drop right at the start of E1M1? Did you ever test this system in something like E2M1? Specifically the teleporter to the ship right at the beginning?

It wasn't smart to enough to actually look into where the SE7 takes you. The way it worked was, if you (the bot) didn't have a goal, then you start from your current position and find stuff you can get to that is either useful or looks interesting. So for example, if you are low on health then a nearby SIXPAK would be given a high value and would probably end up as the target sprite (which means the sector it is in would be the target sector, then you go to the sprite once in the sector). For the teleporters, I just hacked it so that they would be set as temporary goals if you hadn't been to them yet. I didn't mind this kind of stupidity since it sort of emulated what a player would do if they hadn't played a map before.

Here's what the beginning of the goal setting loop looks like and as you can see there is a special case early on for teleporters.

Spoiler

state goalsearchloop

	set NEXTSECT -1
	set passes 0
		
	set mypasses sectpasses[CURSECT]
	ife mypasses -1 { al mypasses al CURSECT break }
	ife mypasses 0 add NUMSECTSCANNED 1

	setarray sectstack[recursion] CURSECT

	add mypasses 1
	setarray sectpasses[CURSECT] mypasses
	ife mypasses 1
	{
		set tempgoalsprite -1
		headspritesect sprsect CURSECT
		whilevarn sprsect -1
		{
			ifn actorvar[sprsect].botneed -9999
			{
				switch sprite[sprsect].picnum
				case FAKEGOAL
					set tempgoalsprite sprsect
				break
				case SECTOREFFECTOR
				ife botvisited[CURSECT] 0
				ife sprite[sprsect].lotag 7
					{
						setarray botvisited[CURSECT] 1
						espawn FAKEGOAL
						setsprite RETURN sprite[sprsect].x sprite[sprsect].y sprite[sprsect].z
						setav[RETURN].ispawnedit sprsect
						set tempgoalsprite RETURN
					}
				
				break

[Reaper_Man]

Another progress update:

As mentioned in another thread, I've solved an enormous amount of performance issues using some math tricks and overall smarter code. Jaap gave me an idea and I've reworked some code, so that the pathfinding now performs 2 separate searches - A coarse search for the target, and then a "local" search using a very fine grid to the nearest node from the coarse search. I've created a visualization here in 2 of my test maps, the first where the AI agent avoids the slime hazard, and a second where it navigates a fairly complex maze.

https://gfycat.com/e...urebergerpicard

You'll notice that he gets stuck on some geometry at the end there in the maze. This is, technically, not a bug, but rather an issue with the coarse grid size used to do the 1st pass of pathfinding on this map.

To solve that problem, I've also been reworking the nodegraph building code as well. There are several "control" actors that mappers can place in their maps to fine tune how the nodegraph is built in their map. There's no magic number here, every map will be different (and to some extent, maps will need to be built with this kind of pathfinding in mind), but this will allow some amount of control on a per-map basis. Changing the nodegraph grid size, the AI agent can now navigate the entire maze.

https://gfycat.com/s...exdwarfmongoose

That being said, while A* can certainly navigate giant mazes like this, this is kind of a worst case scenario, and I would not expect great performance if you built a massive maze in a real world application.

There's several other control actors I've added, to give more fine control to mappers - node removal and node penalty, in per-sector and radius varieties. Node removal controls will make an entire sector and/or a radius around the actor never appear in pathfinding (good for making them avoid pits or other ridiculous geometry). Node penalty controls will make an entire sector and/or radius around the actor to have a movement penalty to it, just like how FLOORSLIME in the example map is penalized. The scores are additive, so you could theoretically stack a floor texture, plus a per-sector penalty score, plus a radius penalty in that sector. It's hard to really show this off in practice, it's already applied in the slime hazard example (using the texture and a per-sector penalty), but I'll make a demo map showing this off more in depth.

Danukem, on 30 November 2015 - 11:07 AM, said:

OK this is almost certainly not good enough, but it gave me a chuckle. Here is the source code for the "ifawayfromwall" CON command:

Spoiler

case CON_IFAWAYFROMWALL:
        {
            int16_t s1 = vm.g_sp->sectnum;
            tw = 0;
#define IFAWAYDIST 108

            updatesector(vm.g_sp->x + IFAWAYDIST, vm.g_sp->y + IFAWAYDIST, &s1);
            if (s1 == vm.g_sp->sectnum)
            {
                updatesector(vm.g_sp->x - IFAWAYDIST, vm.g_sp->y - IFAWAYDIST, &s1);
                if (s1 == vm.g_sp->sectnum)
                {
                    updatesector(vm.g_sp->x + IFAWAYDIST, vm.g_sp->y - IFAWAYDIST, &s1);
                    if (s1 == vm.g_sp->sectnum)
                    {
                        updatesector(vm.g_sp->x - IFAWAYDIST, vm.g_sp->y + IFAWAYDIST, &s1);
                        if (s1 == vm.g_sp->sectnum)
                            tw = 1;
                    }
                }
            }
            VM_CONDITIONAL(tw);
        }
        continue;

So all it's doing is checking whether the sector changes if you move the x and y values by 108 plus or minus. Of course that will count any wall, including red walls, whereas you are probably more interested in white walls (although red walls matter too if the floor or ceiling height is different). By reducing it to a much smaller distance (e.g. 32 instead of 108), you could get a more accurate version, but it will still kind of suck.

I attempted to implement a CON version of this, searching for the void using sector ID -1, and it... kinda works? The code is real garbage tho. It does at least find and drop node points that sit on void walls, but I think it's slower than I want it to be. I'll be revisiting this.