Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize pathfinding #4637

Open
wants to merge 80 commits into
base: master
Choose a base branch
from
Open

Conversation

NRH-AA
Copy link
Contributor

@NRH-AA NRH-AA commented Mar 23, 2024

Pull Request Prelude

Changes Proposed

This is a overhaul of when and how pathfinding is done. I did attempt this before but I closed the pull request due to congestion. I believe all problems from the original pull request have been fixed.

This will change the pathfinding to work as A* algorithm rather than djikstra's.
It will also add more pathfinding calls as needed fixing monster moving around slowly due to 1 second pathfinding interval.
This PR also includes separation of when creatures will update their path from creatures onThink.
Lastly it includes some fixes for bugs which were not detectable until pathfinding was able to be called more often.

Issues addressed:
Might fix: #4617

@MillhioreBT
Copy link
Contributor

I did a quick test but this PR doesn't work, the monsters walk randomly and move away from the target slowly until they disappear from sight, and the summons don't have any type of movement.

@NRH-AA

This comment was marked as outdated.

src/map.cpp Fixed Show fixed Hide fixed
@ranisalt ranisalt requested review from yoo-ship-it and removed request for floki21uu September 14, 2024 08:35
@NRH-AA
Copy link
Contributor Author

NRH-AA commented Sep 16, 2024

LGTM

@ramon-bernardo
Copy link
Contributor

ramon-bernardo commented Oct 17, 2024

I am analyzing the pathfinding code flow to understand its operation and direction. I realized that it would be more appropriate to force the inheriting classes to implement the goToFollowCreature method, instead of keeping this logic in the base class.

This not only improves code readability but also avoids responsibility inversion. The getMonster() method should be encapsulated within the Monster class, where decisions about monster behavior should be made, rather than in the base Creature class.

My suggestion is to ensure that goToFollowCreature is implemented in each derived class, respecting the principle that monster-specific logic should remain inside Monster, not in Creature. This eliminates the inversion of control flow and keeps responsibilities within the correct classes.

Check my fully review of goToFollowCreature, no more:

// Creature.h
Monster* monster = getMonster();
if (monster && !monster->getMaster() && (monster->isFleeing() || fpp.maxTargetDist > 1)) { ... }

Note: that I have also implemented this in Npc and Player.

Overview:

// Creature.h
virtual void goToFollowCreature();
// changed to
virtual void goToFollowCreature() = 0;

// removed, moved to goToFollowCreature in Monster.h
virtual void onFollowCreatureComplete(const Creature*) {}
void Npc::goToFollowCreature()
{
	if (followCreature) {
		FindPathParams fpp;
		getPathSearchParams(followCreature, fpp);
		listWalkDir.clear();
		if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
			hasFollowPath = true;
			startAutoWalk();
		} else {
			hasFollowPath = false;
		}
	}
}

void goToFollowCreature() override;
void Player::goToFollowCreature()
{
	// before
	Creature::goToFollowCreature();
	// after
	if (followCreature) {
		FindPathParams fpp;
		getPathSearchParams(followCreature, fpp);

		listWalkDir.clear();
		if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
			hasFollowPath = true;
			startAutoWalk();
		} else {
			hasFollowPath = false;
		}
	}
}

If the duplicated code is bothersome, feel free to move it to a new function in Creature, and call it in the Monster, Player and Npc class.

@Codinablack
Copy link
Contributor

I am analyzing the pathfinding code flow to understand its operation and direction. I realized that it would be more appropriate to force the inheriting classes to implement the goToFollowCreature method, instead of keeping this logic in the base class.

This not only improves code readability but also avoids responsibility inversion. The getMonster() method should be encapsulated within the Monster class, where decisions about monster behavior should be made, rather than in the base Creature class.

My suggestion is to ensure that goToFollowCreature is implemented in each derived class, respecting the principle that monster-specific logic should remain inside Monster, not in Creature. This eliminates the inversion of control flow and keeps responsibilities within the correct classes.

Check my fully review of goToFollowCreature, no more:

// Creature.h
Monster* monster = getMonster();
if (monster && !monster->getMaster() && (monster->isFleeing() || fpp.maxTargetDist > 1)) { ... }

Note: that I have also implemented this in Npc and Player.

Overview:

// Creature.h
virtual void goToFollowCreature();
// changed to
virtual void goToFollowCreature() = 0;

// removed, moved to goToFollowCreature in Monster.h
virtual void onFollowCreatureComplete(const Creature*) {}
void Npc::goToFollowCreature()
{
	if (followCreature) {
		FindPathParams fpp;
		getPathSearchParams(followCreature, fpp);
		listWalkDir.clear();
		if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
			hasFollowPath = true;
			startAutoWalk();
		} else {
			hasFollowPath = false;
		}
	}
}

void goToFollowCreature() override;
void Player::goToFollowCreature()
{
	// before
	Creature::goToFollowCreature();
	// after
	if (followCreature) {
		FindPathParams fpp;
		getPathSearchParams(followCreature, fpp);

		listWalkDir.clear();
		if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
			hasFollowPath = true;
			startAutoWalk();
		} else {
			hasFollowPath = false;
		}
	}
}

If the duplicated code is bothersome, feel free to move it to a new function in Creature, and call it in the Monster, Player and Npc class.

I mean, this PR has been sitting here for ages, undergone MANY code reviews. I believe the issue you are raising, is one that is already currently present in the source code. I understand that this PR deals with that code, but can't your preferences on the control flow be set aside for the sake of merging this PR? You could easily take 10 minutes or less and make those changes to the codebase after this is merged. I mean, how long does it have to sit, how many revisions does it have to undergo before its finally merged?

@ramon-bernardo
Copy link
Contributor

I am analyzing the pathfinding code flow to understand its operation and direction. I realized that it would be more appropriate to force the inheriting classes to implement the goToFollowCreature method, instead of keeping this logic in the base class.
This not only improves code readability but also avoids responsibility inversion. The getMonster() method should be encapsulated within the Monster class, where decisions about monster behavior should be made, rather than in the base Creature class.
My suggestion is to ensure that goToFollowCreature is implemented in each derived class, respecting the principle that monster-specific logic should remain inside Monster, not in Creature. This eliminates the inversion of control flow and keeps responsibilities within the correct classes.
Check my fully review of goToFollowCreature, no more:

// Creature.h
Monster* monster = getMonster();
if (monster && !monster->getMaster() && (monster->isFleeing() || fpp.maxTargetDist > 1)) { ... }

Note: that I have also implemented this in Npc and Player.
Overview:

// Creature.h
virtual void goToFollowCreature();
// changed to
virtual void goToFollowCreature() = 0;

// removed, moved to goToFollowCreature in Monster.h
virtual void onFollowCreatureComplete(const Creature*) {}
void Npc::goToFollowCreature()
{
	if (followCreature) {
		FindPathParams fpp;
		getPathSearchParams(followCreature, fpp);
		listWalkDir.clear();
		if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
			hasFollowPath = true;
			startAutoWalk();
		} else {
			hasFollowPath = false;
		}
	}
}

void goToFollowCreature() override;
void Player::goToFollowCreature()
{
	// before
	Creature::goToFollowCreature();
	// after
	if (followCreature) {
		FindPathParams fpp;
		getPathSearchParams(followCreature, fpp);

		listWalkDir.clear();
		if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
			hasFollowPath = true;
			startAutoWalk();
		} else {
			hasFollowPath = false;
		}
	}
}

If the duplicated code is bothersome, feel free to move it to a new function in Creature, and call it in the Monster, Player and Npc class.

I mean, this PR has been sitting here for ages, undergone MANY code reviews. I believe the issue you are raising, is one that is already currently present in the source code. I understand that this PR deals with that code, but can't your preferences on the control flow be set aside for the sake of merging this PR? You could easily take 10 minutes or less and make those changes to the codebase after this is merged. I mean, how long does it have to sit, how many revisions does it have to undergo before its finally merged?

Right, I send the #4811 with these improvements

@ramon-bernardo
Copy link
Contributor

Rebase? @NRH-AA

@Codinablack
Copy link
Contributor

Codinablack commented Nov 30, 2024

Rebase? @NRH-AA

You are funny. You go and do things that you know will force the need for a rebase, which just further hold back this PR, and you do it knowing full well what you are doing, and that it will make "rebasing" impossible without ALOT of conflict's being created that need resolved... and then you have the nerve to come back here and say... Rebase?

These kinds of things are the reason why people don't want to spend time contributing PR's to this project.

Even after I made it a point that what you were talking about would just hold this PR back, YOU STILL GO AND DO IT ANYWAY!

Don't be surprised if this never gets merged now

@ramon-bernardo
Copy link
Contributor

Why all this anger, @Codinablack, seek help.

If I had the permission, I would have done the rebase myself... in projects with multiple people working, rebasing is normal, my friend. I ran tests on this PR and LGTM anyway.

@Codinablack
Copy link
Contributor

Codinablack commented Dec 1, 2024

Why all this anger, @Codinablack, seek help.

If I had the permission, I would have done the rebase myself... in projects with multiple people working, rebasing is normal, my friend. I ran tests on this PR and LGTM anyway.

Just because I typed something in all caps to accentuate its importance, doesn't mean I need help.
I would appreciate it if you kept the conversation and responses either about the PR or the context of the message you are responding to, and leave your feelings about my personal mental health out of it.

It might be true that a project with multiple maintainers and contributors will need PR's to be rebased often... but it is also true that when a person knowingly throws roadblocks onto someone else's PR just for the sake of "moving some logic from one class to another" because you prefer it that way, is discouraging.

To constantly fix everything in a review over and over again, just to have someone else say.. hmm I wanna move a big chunk of that code you were working on NOW rather than after you have gotten your PR merged, is quite discouraging indeed... and to be completely fair, it was selfish of you to proceed to do it anyway after I clearly already raised the issue of this PR...

But I guess my breath and energy is wasted in trying to get you to see it this way, instead this comment and the previous one will just be taken as "hostility" apparently, since that is the way weaker minds always twist things they can't argue against.

@Sajgon
Copy link

Sajgon commented Dec 1, 2024

I just tested this commit, and overtime with 100 players online the memory goes to the roof, takes about 30 minutes and I can see it steadily growing to max and crashes my host.

It could be I've done something else wrong, but reverting this PR on my branch doesnt have memory issues anymore.

@ranisalt
Copy link
Member

ranisalt commented Dec 1, 2024

I just tested this commit, and overtime with 100 players online the memory goes to the roof, takes about 30 minutes and I can see it steadily growing to max and crashes my host.

Smells like memory leak. If that happens within 30 minutes I wouldn't merge, but definitely we can look into that.

@Codinablack
Copy link
Contributor

Codinablack commented Dec 2, 2024

I just tested this commit, and overtime with 100 players online the memory goes to the roof, takes about 30 minutes and I can see it steadily growing to max and crashes my host.

Smells like memory leak. If that happens within 30 minutes I wouldn't merge, but definitely we can look into that.

I didn't read over all the code, I just started from top down looking for any instances that could cause a leak. What I found was the method "addFollowers" stores raw creature pointers in a vector but I never saw those raw pointers being cleaned... also its worth mentioning they weren't used along with "incrementReferenceCount()" and "decrementReferenceCount()" so that is likely the cause of the big leak... there might be other reasons, I just did a quick glance... and maybe I missed where he was cleaning that vector, but it doesn't change the fact that the manual ref counting system in place in TFS is not being used.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement Increase or improvement in quality, value, or extent needs-triage Needs testing with screenshot/video confirmation priority: high
Projects
Status: In review
Development

Successfully merging this pull request may close these issues.

Wrong interactions of monsters with pathfinding.
10 participants