Going to open a door with the full party make it drop fps considerably

[rsantellan]

Bug description

On the bridge district (Where I notice) trying to open a door brings down the fps. It's only when the full party is selected.
I believe this is related to #1441

Steps to reproduce

1. Go to Bridge District
2. Click on a door with the full party
3. Move to the other side and click again
4. See error

Expected behavior

It not should drop the fps like that

Screenshots

frame-drops.mp4

GemRB version (check as many as you know apply)

• master as of this issue
• 0.9.1
• 0.9.0
• 0.8.8

Video Driver (check as many as you know apply)

• SDL1.2
• SDL2 built with USE_OPENGL_BACKEND
• SDL2 without USE_OPENGL_BACKEND

[lynxlynxlynx]

Probably just the general performance problem / trade-off, unless you can demonstrate this worked better in 0.8.8 or some later version.

We'll probably need to add new threads to speed the search (eg. the direction loop in FindPath looks parallelizable), but that wouldn't help on all hardware. And since pathing is critical, we can't just wait until it's done, doing other stuff like processing mouse movement in the meanwhile.

[rsantellan]

@lynxlynxlynx I tried on all the tags beginning on the v0.8.8 and in all of them happen the same. Depending where you are the impact is more notable

[bradallred]

the profiler shows we are spending quite a bit of time in Actor::NewPath and half of that time is spent in Map::NormalizeDeltas.

[bradallred]

Things still hitch, but those optimizations gave me ~10% improvement (hitches are 10% shorter). We could squeeze another ~14% if we could eliminate ConvertCoordToTile from the pathfinding by having a flavor of GetBlocked that takes a tile coord. we'd probably have to cache the tile coord for each actor pos too.

Any better fix is going to have to actually change some logic (or offloading to another thread as mentioned)

[bradallred]

I'm not sure it is related, but this looks like a bug to me:

gemrb/gemrb/core/Map.cpp

Lines 2575 to 2594 in ab71947

	// Args are in navmap coordinates
	PathMapFlags Map::GetBlockedInRadius(const Point &p, unsigned int size, bool stopOnImpassable) const
	{
	// We check a circle of radius size-2 around (px,py)
	// Note that this does not exactly match BG2. BG2's approximations of
	// these circles are slightly different for sizes 7 and up.
	if (size > MAX_CIRCLESIZE) size = MAX_CIRCLESIZE;
	if (size < 2) size = 2;
	PathMapFlags ret = PathMapFlags::IMPASSABLE;
	unsigned int r = (size - 2) * (size - 2) + 1;
	if (size == 2) r = 0;
	for (unsigned int i = 0; i < size - 1; i++) {
	for (unsigned int j = 0; j < size - 1; j++) {
	if (i * i + j * j <= r) {
	PathMapFlags retBotRight = GetBlocked(Point(p.x + i * 16, p.y + j * 12));
	PathMapFlags retTopRight = GetBlocked(Point(p.x + i * 16, p.y - j * 12));
	PathMapFlags retBotLeft = GetBlocked(Point(p.x - i * 16, p.y + j * 12));
	PathMapFlags retTopLeft = GetBlocked(Point(p.x - i * 16, p.y - j * 12));

the Point passed into GetBlockedInRadius is already a "navmap" coordinate, but these multiplies are treating it like we are converting it from tile space.

gemrb/gemrb/core/Map.cpp

Lines 394 to 397 in ab71947

	Point Map::ConvertCoordFromTile(const Point& p)
	{
	return Point(p.x * 16, p.y * 12);
	}

Am I missing something?

[lynxlynxlynx]

Which multiplies? Anyway, either we have an issue open (or it was just chat with kmfrick) about subclassing a BasePoint, so we can have Point always be a NavMapPoint and then a separate class be the TileMapPoint to be able to canonically avoid double conversions etc.

[bradallred]

the * 16 and * 12:

PathMapFlags retBotRight = GetBlocked(Point(p.x + i * 16, p.y + j * 12)); 
PathMapFlags retTopRight = GetBlocked(Point(p.x + i * 16, p.y - j * 12)); 
PathMapFlags retBotLeft = GetBlocked(Point(p.x - i * 16, p.y + j * 12)); 
PathMapFlags retTopLeft = GetBlocked(Point(p.x - i * 16, p.y - j * 12));

Yeah, distinct types would be nice to avoid bugs and for clarity

[lynxlynxlynx]

I don't see a problem there, it's iterating over the vertices of what would be the tilemap, but still in normal space.

[bradallred]

Ah, so the multiples are converting i into normal space to add to a normal space coord. gotcha.

[bradallred]

ok, things seem much better to me. We can go a bit further without changing the algorithm in a couple of areas too.

[rsantellan]

ok, things seem much better to me. We can go a bit further without changing the algorithm in a couple of areas too.

Is a lot better for me, the only place is when is a narrow place that drops to <3fps.

[bradallred]

It looks like our "bumping" implementation forces the bumped actor to recalculate a path. I imagine this happens quite a bit in narrow corridors.

I may be being naïve, but it seems like we could instead find the bumped position, then calculate a path from that position to the current position in the path and then prepend that path segment, which would be much better than completely recalculating a path.

[lynxlynxlynx]

Hard to say how much that would help or if it'd look good, as in tight spaces the new segment might cause bumping again or repathing.

[bradallred]

Repeated bumping and complete repathing is what appears to be happening currently. The difference is calculating a few nodes of a a new path and prepending it instead of completely recalculating the entire path as is happening now. The problem is exacerbated greatly if the whole party is pathing though a corridor with the destination being far away.

I dont know anything about how bumping is implemented, but I would hope it is at least deterministic. It's probably too much to hope that it is physics approximate such that collisions between actors behave like like products of force vectors tho :)

[MarcelHB]

Yes, the more XYZ re-pathing ignoring actors in the log appears, the longer to wait. Bumping-check is implemented by this:

gemrb/gemrb/core/PathFinder.cpp

Lines 374 to 375 in 71bb2f8

	bool childIsUnbumpable = childActor && childActor != caller && (flags & PF_ACTORS_ARE_BLOCKING || !childActor->ValidTarget(GA_ONLY_BUMPABLE));
	if (childIsUnbumpable) continue;

Hm, maybe we can exempt party members from this check? Especially when they gathered in front of a door already that isn't blocked by anyone else (Rylock comes to my mind, although I haven't checked whether that's the mechanism here), is there any obvious reason for discard this iteration over this bumping check?

[lynxlynxlynx]

Wouldn't exempting pcs just drop them on the next check? If that was not a problem it could easily lead to them walking through each other.

[MarcelHB]

That's just the path planning here, the actual can-bump-on-step test is in DoStep. If re-pathing is about to be done, this particular actor check goes away anyway, unless there is a reason to deny GA_ONLY_BUMPABLE for an actor. What came to my mind: Why repeat this whole calculation without considering actors blocking, if the reason that's preventing the first run to succeed is just the party itself, in the case of standing too close to a door?

Also, as I read the next check, it means it's blocked unless it's passable, travellable (performable) or an actor (potentially bumpable).

[lynxlynxlynx]

Try it then. 🤷🏾

[MarcelHB]

The bad news: When exhausting on a big map, the algorithm is simply expensive, all the observed frame drops are a result of unfortunate geometry/searchmap blocking. It is especially bad when the ignore-actors flag fails the second time with a full group, because there is actually just no path, see BG2 slums:

Yet there is a way (I can submit a PR if interested) to reuse a little bit of information to halve the penalty by skipping the ignore-actors run if there wasn't any actor to potentially bump into.

The T* stuff doesn't hurt r/n on small maps but on larger ones, we get what we see if there is no path to find. Not sure what to do about this at the moment.

[lynxlynxlynx]

It's the worst case scenario, so not as bad as it may seem, but optimizations are always welcome.

I'm sceptical we could find a faster overall algorithm that would still satisfy all our needs. T* is already an optimization over the A*-like pathfinder we had before, which didn't even support all orientations, let alone bumping.

[MarcelHB]

The algorithm is fine. I'm thinking about some pre-processing, like: Test whether and what party members are close together (by radius) and whether they have a passable, straight line of sight to each other. Then just pick one PC to do the expensive algorithm, and copy the result (if any) by extending one path element for the rest towards that selected PC's position.

This can maybe reduce the calculcation for all these edge-cases even more.

[MarcelHB]

I've been playing around with other approaches of path finding without calculating so much. One of the attempts looks like this:

1. Try to find groups of PCs that are sufficiently close to each other (r/n radius 150) and have a passable LoS and make them have a common path. But only by one calulation pass with one attempt of grouping. Here its 1+2, 3, 4.
2. One PC of a group is a leader (the one with the shortest line to the target point) and will have the path calculated by Theta*. Here it is PC 1.
3. All the other PCs of the group add one path element to the leader (2 -> 1), so closely follow the exact path for the time of movement, and leave upon getting close to the leader's final waypoint, with their formation point as the last element of the path.

This has greatly reduced all these expensive edge cases and frame drops with a mix of reusing path data and relying on a bit of heuristics. So far, the only ugly thing preventing this from testing and judging is that PCs spend a little too much time finding their final spot in the formation.

If I come with some idea, I'll be opening a PR.

[bradallred]

I feel like we are possibly putting the cart before the horse. There are a ton of considerations to make when changing path finding.

I think we need to figure out exactly what is happening to know the best path forward (pun possibly intended).

It seems like the main issue is that we completely recalculate paths at times when we could simply recalculate a portion. Is this not the case? I haven't thoroughly studied the code, but I don't recall seeing any attempts to modify existing paths.

Lynx also hinted that there are possibly issues when reaching the end of a path.

I think there are big improvements that could be made without having to do anything special.

[MarcelHB]

I see these main issues:

• The path calculation may be exhausted in some cases. This is fine, but is a real performance pain on large maps with a full group. So if we can maybe test that if one PC can't reach the destination, other PCs that are similar/close don't even need to run that futile calculation again, and the drop is much mure sufferable.
• The path calculation may be exhausted in a 1st attempt, like the door issue we see above. If geometry is bad, and this currently also means that all actors are considered blocking, this was costly and there is a re-pathing. This, of course, may fail a 2nd time in rare cases.

I'm fully open to ideas. It's just that grouping people by some cheap principles generally turns out to be bearable idea, not perfect in this way of course, and it does not touch the T* code, just a bit of DoStep.

Recalculation of portions of a path sounds good, I just don't have any idea r/n how this is supposed to work like.

[burner1024]

Maybe fixing #1785 would make a difference.

[MarcelHB]

This problem is even more extreme when playing on higher FPS.

I propose another idea: We apply some kind of flood algorithm in a way that two legally adjacent, non-blocking search map cells will be assigned the same number, as their neighbour, starting from top-left. If there is no such neighbour, they will be assigned a different number, so you end up with some kind of map of islands. This map is updated whenever there is a area load, or something mildly permanent changes (like a door). This is linear to the number of search map cells, executed rarely.

So if start end destination are on different search map islands, there is no need to initiate path-finding (save 6 times for a full party).

[lynxlynxlynx]

That wouldn't change anything for door approaches though. But it appears this issue is now hosting several issues and should be split into individual reports / discussions.

[MarcelHB]

That wouldn't change anything for door approaches though. But it appears this issue is now hosting several issues and should be split into individual reports / discussions.

Is it? Aside from the link to #1785, the underlying problem are cases that exhaust the algorithm with a full party on big maps, isn't it? Regardless why. Sure, this won't fix the doors or blocking actors but do we see some generic solution?

[lynxlynxlynx]

The title and first post are about "same island" problems, while the stuff about the sphere is not. With all the work that has already been done, the first part may be just a duplicate of #1785 now. Worst case scenarios like the separate slums area will require a different approach.

[MarcelHB]

Then, on the other hand, we could use this to distinguish the problems. One case: skipping pathfinding completely, or otherweise trying something with actor bumping, moving, ordering instead, since we know it's a same-island problem.

[lynxlynxlynx]

It's just unfortunate that github doesn't allow splitting issues, you can only do one comment and then manually edit in all the rest.

[rsantellan]

Hello,
One thing that has changed is that now I have this on the console:

[PathFinderWIP/DEBUG]: Abandoning because I'm close to the goal
[WalkTo/DEBUG]: Aerie: Path was just abandoned
[PathFinderWIP/DEBUG]: Abandoning because I'm close to the goal
[WalkTo/DEBUG]: Aerie: Path was just abandoned
[GameScript/ERROR]: Invalid scripting action: 'runtopoint([1164.1059])'
[GameScript/ERROR]: Invalid scripting action: 'runtopoint([1164.1107])'
[GameScript/ERROR]: Invalid scripting action: 'runtopoint([1164.1011])'
[GameScript/ERROR]: Invalid scripting action: 'runtopoint([1100.1059])'
[GameScript/ERROR]: Invalid scripting action: 'runtopoint([1052.1059])'
[GameScript/ERROR]: Invalid scripting action: 'runtopoint([1004.1059])'
[KeyMap]: Looking up key: 137(�) 
[KeyMap]: Looking up key: 137(�) 
[KeyMap]: Looking up key: 137(�) 

The [GameScript/ERROR]: Invalid scripting action: 'runtopoint([1052.1059])' is new, didn't happen before, and I now I can't get out of places without a lot of work.

[lynxlynxlynx]

That's a pst-only action, other games don't support running. Harmless error, you just doubleclicked.

[lynxlynxlynx]

Opened a separate #2079 and closing this — the OP bug is fixed.