Pathfinding error - imps get stuck in narrow treasury

[mefistotelis]

Originally reported on Google Code with ID 355

Load the attached save from r1333, and notice a handful of imps stuck in a narrow treasury
next to lava.

A little while before the save, I had almost all imps stuck there and set them free.
So if you wait long enough, more will get stuck there.

Reported by Loobinex on 2014-08-16 19:14:41

---

- _Attachment: [fx1g0006.zip](https://storage.googleapis.com/google-code-attachments/keeperfx/issue-355/comment-0/fx1g0006.zip)_

[mefistotelis]

This is interesting.

I made a simple map which recreates the issue.
Using it I've noticed that the bug already exists in r1213.

Could you use this map to check when this problem started (assuming it wasn't there
in original DK)?

Reported by mefistotelis on 2014-08-16 23:18:15

---

- _Attachment: [test_level.zip](https://storage.googleapis.com/google-code-attachments/keeperfx/issue-355/comment-1/test_level.zip)_

[mefistotelis]

I'll see what I can do, I don't have very good internet access anymore, so downloading
full versions takes ages.

I've tested r976 and it already has the issue.

Reported by Loobinex on 2014-08-16 23:26:26

[mefistotelis]

I installed the Original DK from my CD, got that to sort of work, and managed to use
your map to reproduce the issue in vanilla.

Reported by Loobinex on 2014-08-17 00:10:20

[mefistotelis]

We will have to wait until the whole pathfinding is rewritten before we can fix this.

One problem is that it's not rewritten, another is that we don't have any means of
debugging pathfinding. I think we need some kind of visualization of creature walk
paths.

For now, I will focus on making pathfinding as good as in original DK; improvements
go later.

Reported by mefistotelis on 2014-08-18 09:40:58

[benlp91]

We will have to wait until the whole pathfinding is rewritten before we can fix this.

One problem is that it's not rewritten, another is that we don't have any means of
debugging pathfinding. I think we need some kind of visualization of creature walk
paths.

For now, I will focus on making pathfinding as good as in original DK; improvements
go later.

Reported by mefistotelis on 2014-08-18 09:40:58

@mefistotelis Hello Mefistoltelis, This problem is still active, and no one really knows where to look. Everything has been rewritten meanwhile. You can even show the path where the creature is moving. But we still can't find the error. We now have several test maps and scenarios where it happens repeatedly. Unfortunately, it sometimes breaks enemy keepers because their imps are moving around pillars and stop doing other tasks. Since this part of the code is very complicated, I'd like to ask if you might have the time and inclination to help us with it some day.

[mefistotelis]

The problem is hard to solve because there is no environment where it could be analyzed.

What is need, before such bugs can be worked on:

• Unit tests. Tests which only use the pathfinding module, and ask it to create/follow paths in various situations.
• And to make separate unit tests possible, pathfinding needs to be separated from the rest of the code. Separating a module is often made using static libraries - that helps in keeping the separation, ie. if someone tries to call non-pathfinding functions from pathfinding, the build of the test binary would fail - so the library enforces not breaking the separation.

Some tests could use triangluation data from real levels with real issues, others could generate random layouts. Triangulation and pathfinding should also have functions to visualize what's going on, ie. here's a triangulation image for SW Port debug:

The SW Port pathfinding seem to be a simpler version of what is used in DK, so some solutions could be shared between the projects. (SW version is far worse in regards to real-time update of the triangulation map).

For an example of separation, look at what I did with bullfrog library in SW Port: https://github.com/swfans/swars/tree/master/bflibrary

• is in separate folder
• builds as static library
• there are tests which can be compiled without dependency on the game, only the bullfrog library is needed to compile the tests
• within the library code, there are no references to any module outside of the library

Unfortunately I didn't created such separation in KeeperFX, and that slowly pushes it toward spaghetti code - a situation where everything depends on everything else.

Without proper unit tests, any modification to pathfinding has a considerable chance of introducing more problems while trying to fix one.