Optimize pathfinding #4637

NRH-AA · 2024-03-23T08:27:08Z

Pull Request Prelude

I have followed proper The Forgotten Server code styling.
I have read and understood the contribution guidelines before making this PR.
I am aware that this PR may be closed if the above-mentioned criteria are not fulfilled.

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 · 2024-03-24T17:05:32Z

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.

src/map.cpp

Codinablack

Overall, I didn't see anything sticking out to me that looked like an obvious reason to hold back this PR... bearing that in mind, I also have not personally tested this code and various situations / scenarios either.

I have marked some areas I feel could use further optimization (if it would indeed provide such) by making some small easy changes. I also think some of the methods that were created during this PR could benefit from more passing by reference rather than by value or by pointer, but these are trivial things that are most likely optimized away anyways.

I give this a Passing Review because I see no validation in not approving this PR.

I am still curious about the suggestions I made during this review though :)

src/creature.cpp

src/creature.h

src/map.cpp

src/map.h

src/map.cpp

src/creature.h

NRH-AA · 2024-09-16T14:47:41Z

LGTM

ramon-bernardo · 2024-10-17T03:55:42Z

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 · 2024-10-18T21:15:27Z

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 · 2024-10-23T21:58:04Z

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 · 2024-11-17T00:22:35Z

Rebase? @NRH-AA

NRH-AA added 8 commits March 23, 2024 01:00

Optimize pathfinding

990ba89

Minor fleeing monsters fix

00951d2

Fix whitespace and else brackets

89be1ad

More cleanup

82ad8c9

Cleanup

632d202

Remove uneeded variable name change

e7b5725

Cleanup

bc36d30

Move neighbor arrays back to map.cpp to fix unused variable failure

68841aa

EPuncker requested review from marksamman, kornholi, DSpeichert, ranisalt, djarek, nekiro and MillhioreBT March 23, 2024 15:49

Fix some compiling warnings

edc1746

Fix incorrect method call in game.cpp

2476334

This comment was marked as outdated.

Sign in to view

NRH-AA added 7 commits March 24, 2024 23:18

Update to new creature isDead method

aa4153a

Update to clang format

9f882ca

Update to clang format

8d50780

Fix maxSearchDist=0 searches and delayed reaction to onFollowCreature

b89076b

Fix fleeing monster randomly turning

f4163e5

Reduce memory consumption and update pathmatching algorithm

cab2968

Clang formatting

3834fd5

github-advanced-security bot found potential problems Mar 30, 2024

View reviewed changes

src/map.cpp Fixed Show fixed Hide fixed

NRH-AA added 3 commits March 30, 2024 13:32

Clang formatting

3009b52

Remove uneeded check on new nodes

57ce003

Normalize pathfinding algorithm

a68e1f5

Codinablack approved these changes Sep 12, 2024

View reviewed changes

NRH-AA added 2 commits September 12, 2024 16:31

Replace std::list for vector and modify datatypes

591b5f4

Replace push_back for emplace_back and revert calculateHeuristic

089df96

ranisalt reviewed Sep 12, 2024

View reviewed changes

src/map.cpp Outdated Show resolved Hide resolved

ranisalt reviewed Sep 12, 2024

View reviewed changes

src/creature.h Outdated Show resolved Hide resolved

NRH-AA added 3 commits September 12, 2024 16:51

Replace followedByCreature for followers and update std::array

0d53483

Change addFollowedByCreature to addFollower

b3698e4

Update method calls

de8be87

NRH-AA requested review from ranisalt and Codinablack September 13, 2024 03:19

NRH-AA added 4 commits September 12, 2024 20:30

Add additional checks for redundant pathfinding calls

523821a

Remove redundant check

7a07da2

Clang Format

fac752f

Change updateFollowingCreaturePaths to updateFollowersPaths

27a16c7

Codinablack approved these changes Sep 14, 2024

View reviewed changes

ranisalt requested review from EPuncker and removed request for floki21uu September 14, 2024 08:35

Fix a problem in most recent path conditional

76241a5

NRH-AA added 6 commits September 17, 2024 08:19

Fix bug in pre path conditional check

ef92d7a

Fix logic in last commit

2abf230

Add required nullptr check to stop crashes on creature death

6bf2b1f

Revert crash unrelated

3fdb59f

Merge branch 'master' into Optimize_Pathfinding

b46ae89

Add updateCreaturesPath

743b703

ramon-bernardo mentioned this pull request Nov 5, 2024

monsters bug when running #1650

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Optimize pathfinding #4637

Optimize pathfinding #4637

NRH-AA commented Mar 23, 2024 •

edited

Loading

MillhioreBT commented Mar 24, 2024

This comment was marked as outdated.

Codinablack left a comment

NRH-AA commented Sep 16, 2024

ramon-bernardo commented Oct 17, 2024 •

edited

Loading

Codinablack commented Oct 18, 2024

ramon-bernardo commented Oct 23, 2024

ramon-bernardo commented Nov 17, 2024

Optimize pathfinding #4637

Are you sure you want to change the base?

Optimize pathfinding #4637

Conversation

NRH-AA commented Mar 23, 2024 • edited Loading

Pull Request Prelude

Changes Proposed

MillhioreBT commented Mar 24, 2024

This comment was marked as outdated.

Codinablack left a comment

Choose a reason for hiding this comment

NRH-AA commented Sep 16, 2024

ramon-bernardo commented Oct 17, 2024 • edited Loading

Codinablack commented Oct 18, 2024

ramon-bernardo commented Oct 23, 2024

ramon-bernardo commented Nov 17, 2024

NRH-AA commented Mar 23, 2024 •

edited

Loading

ramon-bernardo commented Oct 17, 2024 •

edited

Loading