Duke4.net Forums: (source code stuff) how did enemies navigate maps? - Duke4.net Forums

Jump to content

Page 1 of 1
  • You cannot start a new topic
  • You cannot reply to this topic

(source code stuff) how did enemies navigate maps?

User is offline   Marscaleb 

#1

I'm learning about how these older games designed their enemy AI. I've been studying how the monster AI in Doom works, so the next logical step is: how did the monster AI in Duke Nukem 3D work? And with that, what about Shadow Warrior? (if there are any notable differences.)

Mostly, I'm curious about how they worked for navigation. This has been something I've been curious about for a long time, because it seemed like a super-advanced concept back in the day, since these critters were walking around in 3D environments. (Later I realized it isn't that much more complicated than an overhead 2D game.) And while the AI never did anything incredibly advanced, I'm still curious about how it worked. How did they figure out where they could go? How did they find their way around a map?

The AI in Shadow Warrior felt a little more advanced because they seemed to walk around a bit more. Was it more advanced? Or did they just make them walk more and hope they found their way?
2

User is offline   Danukem 

  • Duke Plus Developer

#2

GAMEEXEC_STATIC void VM_AlterAng(int32_t const moveFlags)
{
    int const elapsedTics = (AC_COUNT(vm.pData))&31;

    if (EDUKE32_PREDICT_FALSE((unsigned)AC_MOVE_ID(vm.pData) >= (unsigned)g_scriptSize-1))

    {
        AC_MOVE_ID(vm.pData) = 0;
        OSD_Printf(OSD_ERROR "bad moveptr for actor %d (%d)!\n", vm.spriteNum, vm.pUSprite->picnum);
        return;
    }

    auto const moveptr = apScript + AC_MOVE_ID(vm.pData);
    auto &hvel    = moveptr[0];
    auto &vvel    = moveptr[1];

    vm.pSprite->xvel += (hvel - vm.pSprite->xvel)/5;
    if (vm.pSprite->zvel < 648)
        vm.pSprite->zvel += ((vvel<<4) - vm.pSprite->zvel)/5;

    if (A_CheckEnemySprite(vm.pSprite) && vm.pSprite->extra <= 0) // hack
        return;

    if (moveFlags&seekplayer)
    {
        int const spriteAngle    = vm.pSprite->ang;
        int const holoDukeSprite = vm.pPlayer->holoduke_on;

        // NOTE: looks like 'owner' is set to target sprite ID...

        vm.pSprite->owner = (holoDukeSprite >= 0
                             && cansee(sprite[holoDukeSprite].x, sprite[holoDukeSprite].y, sprite[holoDukeSprite].z, sprite[holoDukeSprite].sectnum,
                                       vm.pSprite->x, vm.pSprite->y, vm.pSprite->z, vm.pSprite->sectnum))
          ? holoDukeSprite
          : vm.pPlayer->i;

        int const goalAng = (sprite[vm.pSprite->owner].picnum == APLAYER)
                  ? getangle(vm.pActor->lastv.x - vm.pSprite->x, vm.pActor->lastv.y - vm.pSprite->y)
                  : getangle(sprite[vm.pSprite->owner].x - vm.pSprite->x, sprite[vm.pSprite->owner].y - vm.pSprite->y);

        if (vm.pSprite->xvel && vm.pSprite->picnum != DRONE)
        {
            int const angDiff = G_GetAngleDelta(spriteAngle, goalAng);

            if (elapsedTics < 2)
            {
                if (klabs(angDiff) < 256)
                {
                    int const angInc = 128-(krand()&256);
                    vm.pSprite->ang += angInc;
                    if (A_GetHitscanRange(vm.spriteNum) < 844)
                        vm.pSprite->ang -= angInc;
                }
            }
            else if (elapsedTics > 18 && elapsedTics < GAMETICSPERSEC) // choose
            {
                if (klabs(angDiff >> 2) < 128)
                    vm.pSprite->ang = goalAng;
                else
                    vm.pSprite->ang += angDiff >> 2;
            }
        }
        else
            vm.pSprite->ang = goalAng;
    }

    if (elapsedTics < 1)
    {
        if (moveFlags&furthestdir)
        {
            vm.pSprite->ang = A_GetFurthestAngle(vm.spriteNum, 2);
            vm.pSprite->owner = vm.pPlayer->i;
        }

        if (moveFlags&fleeenemy)
            vm.pSprite->ang = A_GetFurthestAngle(vm.spriteNum, 2);
    }
}


Basically the vanilla Duke 3D monster seeking player routine is trash, but it's good enough given the level design of the base game and didn't use a lot of cpu. The source above has been modified a little from the original, at least insofar as it includes additional comments and I suspect in some minor functional ways. What happening here is the enemy is setting a goal angle for itself based on the last player sighting (generated when it uses the scripted ifcansee command). It generally heads in that direction if using the seekplayer flag on its movement, but it will randomly wiggle its angle around based on distance to goal and how long it has been since a sighting. The wigglin is not enough to avoid getting stuck on walls in any complex environment, though. Individual actors have script where 90% of the functional ai can be found, and those script commands can override what is being done in the source above. However, for vanilla Duke, that script didn't amount to much for most enemies when it came to navigation at least. Some of them were scripted to jump when bumping into stuff (e.g. protector drones, enforcers) and some had some other semi-useful navigational behaviors. But they were all still essentially blind to the environment.
4

User is offline   Marscaleb 

#3

View PostDanukem, on 26 June 2021 - 04:19 PM, said:

But they were all still essentially blind to the environment.

That's half the reason why I'm so interested in these behaviors. There was no nav mesh or even path nodes; nothing to work with specific situations, all running on a first-gen Pentium or even a 486. How do you get them to operate in such conditions? I find that fascinating to learn.
Plus I keep finding bits that are useful to use with my own projects.


View PostDanukem, on 26 June 2021 - 04:19 PM, said:

Individual actors have script where 90% of the functional ai can be found, and those script commands can override what is being done in the source above.

Those scripts mystified me back in 1998. They didn't provide much documentation, and I didn't understand much code at the time. (Not that I understand that much more...) I remember trying to make a new enemy following the example MyEnemy but the thing borked up and didn't work right; it sort of spun in circles and displayed the wrong sprites, and I think the player was randomly instantly killed if within 1024 units of the thing. Eventually I misplaced a bracket with no clue where so the whole game.con wouldn't load and I just scrapped the whole thing. (Then I noticed Redneck Rampage loads a separate file for each enemy type and I'm like "Why didn't I think of that?!")
Ah, memories.

View PostDanukem, on 26 June 2021 - 04:19 PM, said:

What happening here is the enemy is setting a goal angle for itself based on the last player sighting (generated when it uses the scripted ifcansee command). It generally heads in that direction if using the seekplayer flag on its movement,

One, I am intriguiged that it would head to where it last saw the player instead of the player's current position. Doom just chased where the player currently was, and I was kind of wondering what the behavior would be like if they just tracked the last known indication of the player instead. But then that becomes much more taxing, because now each individual monster needs a variable to store a separate the location they are shambling to, plus the processing to update that value each time they hear a noise or see something. And all of that for behavior that doesn't *really* make a difference without advanced navigation functionality that didn't exist yet. So of course they didn't do that, and just react to the player's current position.
So I'm intrigued that Apogee decided to have them go after the last known position instead.
Two, you say they just pursue a direction, not a position on the map? That seems kinda... broken. If they lose sight of the player they could just keep walking past where the player was, forever. I would expect them to try to move to a position and then shamble around there.

View PostDanukem, on 26 June 2021 - 04:19 PM, said:

but it will randomly wiggle its angle around based on distance to goal and how long it has been since a sighting. The wigglin is not enough to avoid getting stuck on walls in any complex environment, though.

I think I can remember a time or two where I stumbled on a liz trooper perpetually trying to jump into a wall in a cave or something... Yeah the maps in Duke offered some challenges to enemy AI.
What kind of "wiggling" are they doing? Is it just adding a growing random value to the angle they are moving in? Do they actually react to hitting walls? Do they try at all to walk around obstacles?
In Doom the monsters can effectively walk around long obstacles, effectively navigating simple maps, just because of a simple design to make them keep walking in their current direction. I was kinda hoping to find some logic that helps them get past obstacles.

This post has been edited by Marscaleb: 26 June 2021 - 07:29 PM

0

User is online   Ninety-Six 

#4

View PostMarscaleb, on 26 June 2021 - 07:20 PM, said:

I was kinda hoping to find some logic that helps them get past obstacles.


I think that even if there were, it would probably end up being rendered moot. Unlike in Doom, the monsters in Duke have code that puts them back to sleep if they can't find the player.
1

User is offline   Danukem 

  • Duke Plus Developer

#5

View PostMarscaleb, on 26 June 2021 - 07:20 PM, said:

Two, you say they just pursue a direction, not a position on the map? That seems kinda... broken. If they lose sight of the player they could just keep walking past where the player was, forever. I would expect them to try to move to a position and then shamble around there.


At any given moment they have an angle/direction, but it is frequently updated and when seeking the player is based on the last known coords, so if they were to walk past the coords then they would turn around and walk back, not keep going.

View PostMarscaleb, on 26 June 2021 - 07:20 PM, said:

What kind of "wiggling" are they doing? Is it just adding a growing random value to the angle they are moving in? Do they actually react to hitting walls? Do they try at all to walk around obstacles?


I was just referring to the angle changes in the code I pasted above.

View PostMarscaleb, on 26 June 2021 - 07:20 PM, said:

In Doom the monsters can effectively walk around long obstacles, effectively navigating simple maps, just because of a simple design to make them keep walking in their current direction. I was kinda hoping to find some logic that helps them get past obstacles.


I think you must be omitting some important details, because literally walking in the same direction would make them get stuck on the first wall they encountered. Maybe you mean they always turn to follow the wall? (i.e. if the wall turns left 90 degrees they turn left 90 degrees) I'm not familiar with Doom AI so I'm just guessing.
0

User is offline   Marscaleb 

#6

View PostDanukem, on 26 June 2021 - 09:30 PM, said:

I think you must be omitting some important details, because literally walking in the same direction would make them get stuck on the first wall they encountered. Maybe you mean they always turn to follow the wall? (i.e. if the wall turns left 90 degrees they turn left 90 degrees) I'm not familiar with Doom AI so I'm just guessing.


It has the effect of following walls, but it can execute without walls, if the player is positioned properly and doesn't move.
This is the thread I made where I had this explained to me, if you were curious. But the try-this-at-home piece is to load up the first level of Doom 2, view the map and type iddt twice (to show monsters on the map) and then watch their behavior. If you can alert some monsters in the big room and get back to the starting room, the monsters can actually navigate their way through the entire horseshoe shape. It's basically just an effect of them "following the wall," but I put that in quotes because there is no code for them to actually track the wall, just code that keeps them from turning around.

Still, it's a rather incredible feat for running on such a small bit of code.

This post has been edited by Marscaleb: 27 June 2021 - 06:32 PM

0

User is offline   Danukem 

  • Duke Plus Developer

#7

View PostMarscaleb, on 27 June 2021 - 06:30 PM, said:

Still, it's a rather incredible feat for running on such a small bit of code.


I can see just from skimming ketmar's reply to you that it is better than Duke 3D. I wonder why it wasn't allowed for the monsters to turn around if the player is in line of sight and within a certain distance, though. Maybe they can but the distance has to be very short?

One issue we have in Duke is monsters will walk off ledge or into pits (same thing) unless they are tagged to be fixed in their starting sector. I wonder how that works in Doom because drop avoidance presents its own issues.
0

#8

View PostDanukem, on 27 June 2021 - 07:57 PM, said:

One issue we have in Duke is monsters will walk off ledge or into pits (same thing) unless they are tagged to be fixed in their starting sector. I wonder how that works in Doom because drop avoidance presents its own issues.

In Doom, monsters can never walk off steep ledges unless they fly. They can walk up and down stairs, limited by a certain z-height difference. Custom GZDoom monsters may differ in this regard.

There's also specific lines to block monsters from crossing.
0

User is online   Rellik 

#9




We need decino-type videos for Duke3d
0

Share this topic:


Page 1 of 1
  • You cannot start a new topic
  • You cannot reply to this topic


All copyrights and trademarks not owned by Voidpoint, LLC are the sole property of their respective owners. Play Ion Fury! ;) © Voidpoint, LLC

Enter your sign in name and password


Sign in options