Roamers, Roaming, and the like

[Malevolent]

I believe I've a simple way to achieve the roaming effect in a zone. I haven't sat down to actually hack this in, so I'm not sure what the produced behavior will look like, but the theory I have in the back of my head seems to suggest to me that it will work. I know this topic has been discussed before, so take this as one other viewpoint.

First, a NPC will need to have two flags. One to indicate whether or not it can roam, and then two what kind of roaming pattern it uses. Then, in Process, after the mob has returned to their homepoint and is not attacking we need to add something of this flavor:

where CanRoam() is boolean property get from the header and GetRoamType is a series of #defs that I'll mention here in a sec.

If (this->CanRoam())
RoamType(this->CastToMob());

Each mob also has the following exclusive properties:

Get/Set:
* roam_x
* roam_y
* roam_z

These are passed into the RoamType validator.

A mob can only be doing one Roaming pattern at a time. Here are the basic starter set of patterns that I think would be useful to prove the utility of this theory:

#define ELIPSE 0
#define SQUARE 1
#define CIRCLE 2
#define LINE 3

The RoamType validator itself need not be complex.

if (mob == 0) return;

switch(this->GetRoamType) {
case ELIPSE: //dostuff break;
case SQUARE: //dostuff break;
case CIRCLE: //dostuff break;
case LINE: //dostuff default: break;
}

Then each case structure evaluates the next position x,y,z that the mob should move to given their ultimate destination, and their current destination.

The update for the mob will be processed each time ::Process() is invoked and previous steps (attacking, walking home) evaluate properly. The advantages to this approach versus the pathpoint setup I've discussed on here already is that one only needs to load one end destination point and not a series of way points. The disadvantage is lack of precision, but, this limitation could be overcome by having more complicated roam patterns defined.

--MV

[Hmm]

that combined with pathways could be a way to very complex path decided by npc itself. if point a to point b has a wall across it it would find best way around it.

if i recall there IS program that has path and diffulties AI.

it has 5 levels of terrain slowness from road ( fast ) to mountain ( inpassable )

if we use special modified code for flat zones that code will rock indeed.. but in dungeons etc i dont know if iut can be modified for that.

[theCoder]

I agree with Hmm that a combination would be best.

It would also be neat to be able to specify an area that an NPC can wander in. It would pick a random point in that area, walk to it, and then pick another random point in that area and walk to it. I think that would give the game a little more realism, espcially for animals that don't really have a set patrol path.

[Malevolent]

Random goal determination within a zone, but set within allowable bounds. Damn, I have to give it to you, that seems like a kickass idea.

When a new goal is selected, it would need to be achievable by the mob, and that bounds determination could be tricky. You don't really want a hundred random timers firing off for each step. The poor thing will look confused.

So the trick is to know if the mob /can/ move to its destination. Which I assume will only work if there exists some sort of zone evaluator -- which will likely have to work with the existing map files. Anything else just seems so tedious. Is there some clever way to avoid this cost?

[Hmm]

http://www.riversoftavg.com/downloads.htm

finally found it...

about converting this to eq map zone data useage. some is possible but multifloor ie: dungeons i dunno how it will be possible. im sure it IS possible however.

[Hmm]

ohhh

http://www.riversoftavg.com/flocking.htm

it can be great for gnolls groups in sk for example.

[theCoder]

I only anticipated the NPC choosing a new goal point whenever it reached it's current goal point, and that it would walk in a straight line there. Of course, pretty soon, we're going to get into the famous pathing problems that Verant spent about 5 years (ok, maybe it only _seemed_ like that long :)) figuring out. I've noticed that right now mobs just appear by your side (walls and other obstacles like distance be damned) to beat on you, and running away really doesn't help all that much. Kind of makes it hard to run to the guards (not that they help that much either).

Perhaps we need some sort of unified movement code. The NPC can wander (patroll, random, stand still, whatever) when it's not aggro'ed on something, but aggro'ing it causes your position to be it's new goal destination. At all times, it's trying to reach it's goal. That way, we have all the movement code in one place (easy modifcations to work with walls, etc).

Also, that flocking demo is really cool. That would be another really neat feature to put into the emulator (though, I'm not sure I really want to see a flock of split paw gnolls bearing down on me :))

[Malevolent]

I implemented Reynold's Boid Algorithm. The problem is one of speed. I put the flocking code in a flock timer set to 1500. So it doesn't even occur that often, and when it does, it brings my 1.2ghz nearly to its knees.

The Algorithm in a Nutshell:



1. Attempt to move to the center of the mobs in the neighborhood.
2. Attempt to match speed with other mobs in the neighborhood.
3. Attempt to maintain a minimum distance from all other mobs and objects on the screen.



Consider the first rule. Each mob needs to "know" where the perceived center within her flock is. To get this, you have two options. One, is to sum the current vector position of each mob and then divide by the number of mobs. This works, but the problem is one of performance.

Consider now the way the server is setup:

ZoneLoop
MobLoop
For A Mob in MobLoop
Compare Mob A to All OtherMobs in MobLoop

Keep in mind that you have all the other checks going on. I smell my processor cooking, how about you? In actuality, the zoneserver lags so bad that it just isn't viable.

Option two is to calculate a running vector average as we step into the process for each mob. IN THEORY, you would keep a global vector total, in addition to a global mob count. When its the mobs turn, you do the math on the totals, and presto, no more lookup problems. To find the perceived center, just take the global vector and global total, divide, and boom you're done.

That would work well enough for rule one. But what about rules two and three?

Getting the nearest mob without causing a massive dent in performance is a strategic problem looking for an answer. You have to lookup who is your nearest neighbor for each mob in the zone for every tick.

I considered having a quicklookup matrix that had all the vectors of the mob in the zone in it. But then I realized that there is a fundamental underlying challenge here:

What is an effective way to compare one mob to all the other mobs in a zone without it being costly?

[theCoder]

I think the flocking code, while neat, may be a little too much for the EMU. I know I run my server on a 133 MHz, so it definitely won't have the power if it's unusable on a 1.2 GHz. I think the best way to do this would be to fake it somehow.

One way I think to optimize everything is to reduced the number of mobs in a flock. Don't flock the entire zone, just groups of 5-10 mobs. Though that may still be too much.

Another way may be to make a fake mob of some sort that the other mobs in the flock tend to stay close to. The fake mob wanders around and the real mobs wander in the same direction.

[Hmm]

hmm set code in spawn groups not entire zone? humans dont flock around after all.

wolves do since they hunt in packs. im sure gnolls do bec theyre based on wolves.

eleplants do flock but with numbers it wont go too well.

or just set it by model numbers. all gnolls and wolves flock ( but not together ) and no humans for example.

if i remember theres other flocking type. you set random one or few to leader and rest of em try to follow em. whatever closest leader follow can see it turns to that leader and follows em.

[Malevolent]

Actually, that gives me an idea. Up to now I've been filtering the entity list for certain qualities. I haven't, however, tried making a new entity list altogether that has references to the mobs I want to mess with. A good question would be /when/ exactly to make the list, how to update it without writing a bunch of mind numbing code, and manageing two lists with mob info and hoping to keep both in relative sync (make sure global list contains mobs in child list).

That would cut down the number of mobs to cycle through. But, I'm not sure if it'd actually eliminate enough of the problem to make it worthwhile (such as you can flock only 4 mobs before performance goes out the window...).

But, it still hits the fundamental problem of comparing self to others within a subnode. Maybe more complicated searching algorthims (e.g., A* -- it seems pretty popular for strategy games) might be a better approach to searching the list.

There's something on the tip of my tongue ... it's eluding me tonight.

[Lurker_005]

Can you somehow tie into the /follow code for flocking? With some modifications to keep them from single file.

Just a thought.

Ok not exactly what you were talking about, but I wanted to try and stir up ideas :)

[Malevolent]

I'm trying mixing conway's game of life with the other stuff I've added (servants and masters, half-pet army, spawn origin replacement, hunger code, and now procreation). I think this will create an interesting effect. I'll find out soon :-)

I'm thinking flocking isn't the way to go to achieve EB.

Putting mobs on /follow may not do much more than what half-pet army code does. I feel like there's this golden other solution just out there beyond the reach of my arm, and that it has a connection to ants, parking in a parking lot, and a highway.

[stormgod]

I know that some mobs in some zones are using way points or at least a system of waypoint with a distance allowed ( i.e. it does not follow a strict path from way point to way point )

a good exemple of that are mams in everfrost or even the dark assassin in the same zone ( I know it cause I've played like 40 lvls in this zone lol )

and I'm sure its not the only zone like that ,

so when they are roaming they generaly are following a path or they are restricted in a certain area , but I think that a waypoint system is the most easy system to make with the little drawback that it would require a pathing table for every mob using this specificity

[Hmm]

storm this is mostly experent on making eq zones more real.

heh maybe there'll be banding of wolves and gnolls in sk for example lol.

[Malevolent]

My Theory seems to work (http://eqemu.net/forums/showthread.php?s=&postid=6714#post6714)

=)