[Coding #1147] Moving the party around

[Andrea B Previtera]

Here we go with another question.
How do you exactly move the party?

Let's suppose there is a "central party point", which is the middle of the screen. Currently the party is at (X,Y) You decide to move the whole party to (X+1, Y+1).

What happens? Let's take the easiest case, a party of a single one, whose position falls exactly on the "central party point". He will try to move to (X+n,Y+n).
If the movement isn't blocked (i.e. - the party member does not collide with anything), then it's all ok.
But what if it collides? What he's gonna do?
Perhaps pathfinding to the first non-blocked point in the same direction?
I've tried a few different solutions and each one seem to have a logical hole.
What's yours?


Second part of the question:
In a party with more than one member, each one will have a dx,dy position relative to the aforementioned "central party point".

Then, the party moves through a tunnel which is too narrow to contain the various dx,dy positions around the "central party point". What happens? Are the relative positions temporarily squeezed to fit the non-blocked area around that point?


Thanks again

a.

[SB-X]

Then I'd make sure there is a line of site to the "leader" by moving into a location closer to them. If it is the leader that is blocked, the party can't move.

The relative x,y position should just be a suggestion. If it can't be maintained in the case of a small tunnel, the party members should take turns falling into line behind the leader. Starting with the person behind the leader, he's blocked going straight forward, and going around the tunnel or back would put him further from the leader, so all he can do is get closer to keep the line of site. Some of the party members further back won't move in some turns while getting into the tunnel. (because the rest of the party blocks them and has already taken their turn)

The central party point is the leader. I havn't had experience with a leaderless party style yet.
But this is all for a "formation" style movement which I think Exult uses now. You could do what it used to do and just have the party members continuously pathfind to a certain distance near the leader (again preferring a line-of-site to him), and they don't have any relative x,y position. It looks more natural but is probably slower.

[drcode]

Yes, Exult currently uses a 'flocking' algorithm, where each party member tries to follow the person in front. The code is in 'party.cc'. We used to have everyone aim roughly for the same spot, using pathfinding when blocked, but nobody liked that:-)

[Andrea B Previtera]

Well a leaderless party style should work exactly like the party style /with/ a leader: just imagine that the avatar is invisibile
I will try to have a look at party.cc

Two more questions:

1) what changed exactly (in terms of algorithm) between the old party style which noone liked and the current one (original party formation)?

2) how do you avoid situations like this:



(one of the members tries to pathfind in formation near the leader - it's destination falls into a house and he can correctly pathfind there)

[drcode]

1. In the old-style, the Avatar headed towards the mouse location, and all the other party members headed toward spots randomly chosen a few tiles away. Whenever someone got blocked, the pathfinder was called (which could result in really bad slowdowns). The new style uses a 'flocking' algorithm, where each party member follows a 'leader'. Each time the Avatar takes a step, each of his followers in the row behind tries to take a step to maintain their formation, as do the followers behind them. If a step is blocked, the NPC tries to step around the blocked tile. This makes it possible for the party to fit through tight spots without using pathfinding. The pathfinder is only called as a last resort, if a party member gets too far behind the group.

2. It's something like this: When the Avatar walks past the entrance, let's say that the NPC following one tile to the left gets blocked in the doorway, and has to step to the left or right to keep going. If he steps to the left, then the wall will be between him and the Avatar. The 'flocking' code detects this, and decides that he should avoid that step and move to the right instead. There are still situations where this can lead to an NPC being trapped, and that's when the pathfinder is called.

[Andrea B Previtera]

A last thing: ok, everyone follows the avatar in the way you described. But how does the avatar move? (in my case, it would be an invisible point which everyone will follow)

I noticed that even if you collide with something, the Avatar will manage to move a little to avoid it, except for cases when even by moving a few steps in one or the dX,dy direction will still see him colliding. Am I right?

[SB-X]

Pentagram/U8 does this doesn't it? If you're blocked you will move a certain distance around obstacles automatically.

[drcode]

The Avatar will follow the mouse, but will be diverted by blocked tiles. For example, if the mouse is to the NW, and there's a wall directly to the north, he'll take a step to the west. If the mouse is to the north, he just won't move.